Applied Cryptography

Chapter 3
Public Key Cryptography
Public Cryptography
Contents
• Public Key Cryptosystems
• Number Theory - Modular Arithmetic
• RSA
Private-Key Cryptography
• Private/secret/single key cryptography uses one key
• Shared by both sender and receiver
• If this key is disclosed, communications are
compromised
• Also, it is symmetric, parties are equal
• Hence, does not protect the sender from the receiver
forging a message & claiming it was sent by the sender
Public-Key Cryptography
• Probably the most significant advance in the 3000-year
history of cryptography
• Uses two keys – a public & a private key
• Asymmetric since parties are not equal
• Uses clever application of number theoretic concepts to
function
• Complements rather than replaces private key crypto
 Public-Key Cryptography
• Public-key/two-key/asymmetric cryptography involves the
use of two keys:
• a public key, which may be known by anybody, and can be
used to encrypt messages, and verify signatures
• a private key, known only to the recipient, used to decrypt
messages, and sign (create) signatures
• Asymmetric because
• Those who encrypt messages or verify signatures cannot
decrypt messages or create signatures
Public-Key Cryptography
 Public-Key Characteristics
• Public-Key algorithms rely on two keys with the
characteristics that it is:
• Computationally infeasible to find the decryption key knowing
only the algorithm & encryption key
• Computationally easy to encryption/decrypt messages when
the relevant (encrypt /decrypt) key is known
• Either of the two related keys can be used for encryption, with
the other used for decryption (in some schemes)
• Analogy to delivery with a padlocked box
 Public-Key Cryptosystems

• Two major applications:

– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
Number Theory
Modular Arithmetic
• Number theory
• Public key algorithms are based on modular
arithmetic.
• Modular addition.
• Modular multiplication.
• Modular exponentiation.
Introduction to Number Theory
• will now introduce finite fields
• of increasing importance in cryptography
o AES, Elliptic Curve, IDEA, Public Key
• concern operations on “numbers.”
• where what constitutes a “number” and the type of operations varies
considerably
• Start with basic number theory concepts
Prime Numbers
• Prime numbers only have divisors of 1 and self
• they cannot be written as a product of other numbers
• note: 1 is prime, but is generally not of interest
• eg. 2,3,5,7 are prime, 4,6,8,9,10 are not
• prime numbers are central to number theory
• list of prime number less than 200 is:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79
83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199
Divisors
• Say a non-zero number b divides a if for some m have a=mb(a, b,
m all integers)
• That is b divides into a with no remainder
• denote this b|a
• and say that b is a divisor of a
• eg. all of 1,2,3,4,6,8,12,24 divide 24
• eg. 13 | 182; –5 | 30; 17 | 289; –3 | 33; 17 | 0
Properties of Divisibility
• If a|1, then a = ±1.
• If a|b and b|a, then a = ±b.
• Any b /= 0 divides 0.
• If a | b and b | c, then a | c
–e.g. 11 | 66 and 66 | 198 x 11 | 198
• If b|g and b|h, then b|(mg + nh)
• for arbitrary integers m and n
e.g. b = 7; g = 14; h = 63; m = 3; n = 2
hence 7|14 and 7|63
Division Algorithm
• If you divide a by n and get an integer quotient q and integer
remainder r such that:
–a = qn + r where 0 <= r < n; q = floor(a/n)
• The remainder r is often referred to as a residue
Prime Factorisation
• to factor a number n is to write it as a product of other numbers:
n=a x b x c
• note that factoring a number is relatively hard compared to
multiplying the factors together to generate the number
• the prime factorisation of a number n is when its written as a
product of primes
• eg. 91=7x13 ; 3600=24x32x52
Relatively Prime Numbers & GCD
• Two numbers a, b are relatively prime if they have no common
divisors apart from 1
• eg, 8 & 15 are relatively prime since factors of 8 are 1,2,4,8, and of 15 are
1,3,5,15, and 1 is the only common factor
• Conversely can determine the greatest common divisor by comparing
their prime factorizations and using the least powers
• eg. 300=21x31x52 18=21x32 hence GCD(18,300)=21x31x50=6
Greatest Common Divisor (GCD)
• a common problem in number theory
• GCD (a, b) of a and b is the largest integer that divides evenly into
both a and b
• eg GCD(60,24) = 12
• define GCD(0, 0) = 0
• often want no common factors(except 1) define such numbers as
relatively prime
• eg GCD(8,15) = 1
• Hence, 8 & 15 are relatively prime
Example GCD(1970,1066)
• 1970 = 1 x 1066 + 904 gcd(1066, 904)
• 1066 = 1 x 904 + 162 gcd(904, 162)
• 904 = 5 x 162 + 94 gcd(162, 94)
• 162 = 1 x 94 + 68 gcd(94, 68)
• 94 = 1 x 68 + 26 gcd(68, 26)
• 68 = 2 x 26 + 16 gcd(26, 16)
• 26 = 1 x 16 + 10 gcd(16, 10)
• 16 = 1 x 10 + 6 gcd(10, 6)
• 10 = 1 x 6 + 4 gcd(6, 4)
• 6 = 1 x 4 + 2 gcd(4, 2)
• 4 = 2 x 2 + 0 gcd(2, 0)
GCD(1160718174, 316258250)
Dividend Divisor Quotient Remainder
a = 1160718174 b = 316258250 q1 = 3 r1 = 211943424
b = 316258250 r1 = 211943424 q2 = 1 r2 = 104314826
r1 = 211943424 r2 = 104314826 q3 = 2 r3 = 3313772
r2 = 104314826 r3 = 3313772 q4 = 31 r4 = 1587894
r3 = 3313772 r4 = 1587894 q5 = 2 r5 = 137984
r4 = 1587894 r5 = 137984 q6 = 11 r6 = 70070
r5 = 137984 r6 = 70070 q7 = 1 r7 = 67914
r6 = 70070 r7 = 67914 q8 = 1 r8 = 2516
r7 = 67914 r8 = 2516 q9 = 31 r9 = 1078
r8 = 2516 r9 = 1078 q10 = 2 r10 = 0
Modular Arithmetic
• Define the modulo operator “a mod n” to be the remainder when a is
divided by n
–where integer n is called the modulus
• b is called a residue of a mod n
–since with integers can always write: a = qn + b
–usually chose the smallest positive remainder as the residue
ie. 0 <= b <= n-1
–The process is known as modulo reduction
eg. -12 mod 7 =-5 mod 7 =2 mod 7 =9 mod 7
• a & bare congruent if: a mod n = b mod n
–When divided by n, a & b have the same remainder
–eg. 100 = 34 mod 11
Modular Arithmetic Operations
• can perform arithmetic with residues
• uses a finite number of values, and loops back from either end
Zn= {0, 1, . . . , (n –1)}
• Modular arithmetic is when we do addition & multiplication and
modulo reduce the answer
• can do reduction at any point, i.e.
–a+b mod n = [a mod n + b mod n] mod n
Modular Arithmetic Operations
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) –(b mod n)] mod n = (a –b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n
e.g.
• [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15)
mod 8 = 26 mod 8 = 2
• [(11 mod 8) –(15 mod 8)] mod 8 = –4 mod 8 = 4 (11 –15) mod
8 = –4 mod 8 = 4
• [(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 x 15)
mod 8 = 165 mod 8 = 5
Modular Arithmetic
• Modular addition.
• Modular multiplication.
• Modular exponentiation.
 Modular Addition
• Addition modulo (mod) K
• Poor cipher with (dk + dm ) mod K, e.g., if K=10 and dk is the key.

+ 0 1 2 3 4 5 6 7 8 9
0 0 1 2 3 4 5 6 7 8 9

1 1 2 3 4 5 6 7 8 9 0
2 2 3 4 5 6 7 8 9 0 1
3 3 4 5 6 7 8 9 0 1 2

• Additive inverse: addition mod K yields 0.

• “Decrypt” by adding inverse.
Modular Multiplication
• Multiplication modulo K

* 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9
2 0 2 4 6 8 0 2 4 6 8
3 0 3 6 9 2 5 8 1 4 7

• Multiplicative inverse: multiplication mod K yields 1

• Only some numbers have inverse
 Modular Multiplication
•Only the numbers relatively prime to n will have
mod n multiplicative inverse
•x, m relative prime: no other common factor
than 1
• Eg. 8 & 15 are relatively prime - factors of 8 are
1,2,4,8, and of 15 are 1,3,5,15, and 1 is
the only common factor
Modular Arithmetic Properties
Euclidean Algorithm Divisors
12
1, 2, 3, 4, 6, 12
33
1, 3, 11, 33
Common 1, 3
Divisors
• an efficient way to find the GCD(a, b) Greatest 3
• uses the theorem that: Common
Divisor
–GCD(a,b) = GCD(b, a mod b)
GCD (12,33) = 3
• Euclidean Algorithm to compute GCD(a,b) is:
Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);
Extended Euclidean Algorithm
• calculates not only GCD but x & y:
ax + by = d = gcd(a, b)
• useful for later crypto computations
• follow the sequence of divisions for GCD, but assume at each step i,
you can find x &y:
r = ax + by
• At the end, find the GCD value and also x & y
• if GCD(a,b)=1 these values are inverses
Extended Euclidean Algorithm
• T1 = 0 and T2 = 1 for the first raw
• T = T1 – T2 * Q
• Example: Wha tis the multiplicative inverse of 3 and 5
Q A B R T1 T2 T
1 5 3 2 0 1 -1
1 3 2 1 1 -1 2
2 2 1 0 -1 2 -5
x 1 0 X 2 -5 x

2 is the multiplicative Inverse of 3 mod 5.

Finding Inverses
EXTENDED EUCLID(m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1mod m
4. Q = A3 div B3
5. T1, T2, T3)=(A1 –Q B1, A2 –Q B2, A3 –Q B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
Multiplicative Inverse
• Under mod n
• A X A-1 = 1 mod n
• 3 x ? = 1 mod 5 à 3*2 = 6 mod 5 = 1
• >> 3 x 2 = 1 mod 5
• 2 x ? = 1 mod 11 à 2*6 = 12 mod 11 =1
• >> 2 x 6 = 1 mod 11
• 4 x ? = 1 mod 5 à 4*4= 16 mod 5 = 1
• >> 4 x 4 = 1 mod 5

• 5 x ? 1 mod 10
• >>>>> doesn’t exist, as 5 and 10 are not relatively prime to each other
 Inverse of 550 in GF(1759)

Q A1(A) A2(B) A3(Q) B1(T1) B2(T2) B3(T)

— 1 0 1759 0 1 550
3 0 1 550 1 –3 109
5 1 –3 109 –5 16 5
21 –5 16 5 106 –339 4
1 106 –339 4 –111 355 1
Group, Ring, Field
Group
• a set of elements or “numbers.”
–may be finite or infinite
• with some operation whose result is also in the set (closure)
• obeys:
–associative law: (a.b).c = a.(b.c)
–has identity e: e.a = a.e = a
–has inverses a-1: a.a-1= e
• if commutative a.b = b.a
–then forms an abelian group
Cyclic Group
• define exponentiation as repeated application of the operator
–example: a-3= a.a.a
• and let identity be: e=a0
• a group is cyclic if every element is a power of some fixed element
–ie b =ak for some a and every b in the group
• a is said to be a generator of the group
Ring
• A ring R denoted by {R, +, *}, is a set of elements with two binary
operations called addition and multiplication, such that for all a, b, c ∈ S.
• It is a set of “numbers.”
• with two operations (addition and multiplication) which form:
• An abelian group with an addition operation
• and multiplication:
–has closure
–is associative
–distributive over addition: a(b+c) = ab + ac
• If the multiplication operation is commutative, it forms a commutative ring
• If a multiplication operation has an identity and no zero divisors, it forms
an integral domain
Field
• a set of numbers
• with two operations which form:
• abelian group for addition
• abelian group for multiplication (ignoring 0)
• ring
• have hierarchy with more axioms/laws
• group -> ring -> field
Finite (Galois) Fields
• Finite fields play a key role in cryptography
• can show the number of elements in a finite field must be a power of
a prime pn
• known as Galois fields
• denoted GF(pn)
• In particular often use the fields:
–GF(p)
–GF(2n)
Galois Fields GF(p)
• GF(p) is the set of integers {0,1, … , p-1} with arithmetic operations
modulo prime p
• These form a finite field
–since have multiplicative inverses
–find inverse with the Extended Euclidean algorithm
• hence arithmetic is “well-behaved” and can do addition, subtraction,
multiplication, and division without leaving the field GF(p)
GF(7) Addition Example
+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5
GF(7) Multiplication Example
´ 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
Additive and Multiplicative Inverse
a -a a-1
0 0 - Additive inverse
1 7 1 a + (-a) = 0
2 6 -
3 5 3
4 4 - Multiplicative inverse
(a ) * (1/a) = 1
5 3 5
6 2 -
7 1 7
 Polynomial Arithmetic
• can compute using polynomials
f(x) = anxn+ an-1xn-1+ … + a1x + a0= ∑ 𝑎! 𝑥 !
nb. not interested in any specific value of x
which is known as the indeterminate
• several alternatives available
–ordinary polynomial arithmetic
–polynomial arithmetic with coords mod p
–polynomial arithmetic with coords mod p and polynomials
mod m(x)
Ordinary Polynomial Arithmetic
• add or subtract corresponding coefficients
• Multiply all terms by each other
• Eg,
let f(x) = x3+ x2+ 2 and g(x) = x2–x + 1
f(x) + g(x) = x3+ 2x2–x + 3
f(x) –g(x) = x3+ x + 1
f(x) x g(x) = x5+ 3x2–2x + 2
Polynomial Arithmetic with Modulo
Coefficients
• When computing the value of each coefficient, do the calculation
modulo some value
• forms a polynomial ring
• could be modulo any prime
• But we are most interested in mod 2
ie, all coefficients are 0 or 1
eg. let f(x) = x3+ x2 and g(x) = x2+ x + 1
f(x) + g(x) = x3+ x + 1
f(x) x g(x) = x5+ x2
Polynomial Division
• can write any polynomial in the form:
–f(x) = q(x) g(x) + r(x)
–can interpret r(x) as being a remainder
–r(x) = f(x) mod g(x)
• if have no remainder say g(x) divides f(x)
• if g(x) has no divisors other than itself & 1 say it is irreducible (or
prime) polynomial
• Arithmetic modulo an irreducible polynomial forms a field
Polynomial GCD
• can find the greatest common divisor for polys
– c(x) = GCD(a(x), b(x)) if c(x) is the poly of
greatest degree which divides both a(x), b(x)
• can adapt Euclid’s Algorithm to find it:
Euclid(a(x), b(x))
if (b(x)=0) then return a(x);
else return
Euclid(b(x), a(x)mod b(x));
• all the foundations for polynomial fields as seen next
Modular Polynomial Arithmetic
• can compute in the field GF(2n)
–polynomials with coefficients modulo 2
–whose degree is less than n
–hence must reduce modulo an irreducible poly of degree n
(for multiplication only)
• form a finite field
• can always find an inverse
–can extend Euclid’s Inverse algorithm to find
Example GF(23)
Computational Considerations
• Since coefficients are 0 or 1, they can represent any such
polynomial as a bit string
• addition becomes the XOR of these bit strings
• Multiplication is shift & XOR
–cf long-hand multiplication
• modulo reduction done by repeatedly substituting the highest power
with the remainder of the irreducible poly (also shift & XOR)
Computational Example
• in GF(23) have (x2+1) is 1012 & (x2+x+1) is 1112
• So, addition is
– (x2+1) + (x2+x+1) = x
– 101 XOR 111 = 0102
• And multiplication is
– (x+1).(x2+1) = x.(x2+1) + 1.(x2+1)
= x3+x+x2+1 = x3+x2+x+1
– 011.101 = (101)<<1 XOR (101)<<0 =
1010 XOR 101 = 11112
• polynomial modulo reduction (get q(x) & r(x)) is
– (x3+x2+x+1 ) mod (x3+x+1) = 1.(x3+x+1) + (x2) = x2
– 1111 mod 1011 = 1111 XOR 1011 = 01002
Using a Generator
• equivalent definition of a finite field
• A generator is an element whose powers generate all non-zero
elements
–in F have 0, g0, g1, …, gq-2
• can create a generator from the root of the irreducible polynomial
• Then, implement multiplication by adding exponents of the generator
 Totient Function
• Totient function ø(n): number of integers less than n
relatively prime to n
• if n is prime,
• ø(n)=n-1
• if n=p*q, and p,q are primes, p != q
• ø(n)=(p-1)(q-1)
• E.g.,
• ø(37) = 36
• ø(21) = (3–1)×(7–1) = 2×6 = 12
Modular Exponentiation
xy 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 1 2 4 8 6 2 4 8 6 2
3 1 3 9 7 1 3 9 7 1 3
4 1 4 6 4 6 4 6 4 6 4
5 1 5 5 5 5 5 5 5 5 5
6 1 6 6 6 6 6 6 6 6 6
7 1 7 9 3 1 7 9 3 1 7
8 1 8 4 2 6 8 4 2 6 8
9 1 9 1 9 1 9 1 9 1 9
 Modular Exponentiation
• xy mod n = xy mod ø(n) mod n
• if y = 1 mod ø(n) then xy mod n = x mod n
RSA (Rivest, Shamir, Adleman) Algorithm
RSA (Rivest, Shamir, Adleman)
• The most popular, best-known, and most widely used public-key
scheme.
• Support both public key encryption and digital signatures.
• Assumption/theoretical basis:
• Factoring a big number is hard.
• Security is due to the cost of factoring large numbers
• factorization takes O(e log n log log n) operations (hard)
• Variable key length (usually 512 bits).
• Variable plaintext block size.
• Plaintext must be “smaller” than the key.
• Ciphertext block size is the same as the key length.
 What Is RSA?
• To generate a key pair:
• Pick large primes (>= 256 bits each) p and q
• Let n = p*q, keep your p and q to yourself!
• For public key, choose e that is relatively prime to
ø(n) =(p-1)(q-1), let pub = <e,n>
• For private key, find d that is the multiplicative inverse of e
mod ø(n), i.e., e*d = 1 mod ø(n), let priv =
<d,n>
RSA En/decryption
• To encrypt a message M, the sender:
• obtains public key of recipient PU={e,n}
• computes: C = Me mod n, where 0≤M<n
• To decrypt the ciphertext C, the owner:
• uses their private key PR={d,n}
• computes: M = Cdmod n
• Note that the message M must be smaller than the modulus
n (block if needed)
RSA
Algorithm
RSA Key Setup
• each user generates a public/private key pair by:
• selecting two large primes at random: p, q
• computing their system modulus n=p.q
• note ø(n)=(p-1)(q-1)
• selecting at random the encryption key e
• where 1<e<ø(n), gcd(e,ø(n))=1
• solve following equation to find decryption key d
• e.d=1 mod ø(n) and 0≤d≤n
• publish their public encryption key: PU={e,n}
• keep secret private decryption key: PR={d,n}
 Why RSA Works
• because of Euler's Theorem:
• aø(n)mod n = 1 where gcd(a,n)=1
• In RSA have:
• n=p.q
• ø(n)=(p-1)(q-1)
• carefully chose e& dto be inverses mod ø(n)
• hence e.d=1+k.ø(n)for some k
• hence :
Cd= Me.d = M1+k.ø(n)= M1.(Mø(n))k
= M1.(1)k= M1= M mod n
 RSA Example –Key Setup
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute ø(n)=(p–1)(q-1)=16×10=160
4. Select e : gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160 Value is d=23
since 23×7=161= 10×160+1
6. Publish public key KU={7,187}
7. Keep secret private key KR={23,17,11}
 Why Does RSA Work?
• Given pub = <e, n> and priv = <d, n>
• n =p*q, ø(n) =(p-1)(q-1)
• e*d = 1 mod ø(n)
• xe* d = x mod n
• encryption: c = me mod n
• decryption: m = cd mod n = me*d mod n = m
mod n = m (since m < n)
• digital signature (similar)
 How Does RSA Work?
• Given: pub = <e, n> and priv = <d, n>
• encryption: c = me mod n, m < n
• decryption: m = cd mod n
• signature: s = md mod n, m < n
• verification: m = se mod n
• given message M = 88 (nb. 88<187)
• encryption:
C = 887 mod 187 = 11
• decryption:
M = 1123 mod 187 = 88
Exponentiation
• can use the Square and Multiply Algorithm
• a fast, efficient algorithm for exponentiation
• The concept is based on repeatedly squaring the base
• and multiplying by the ones that are needed to compute the
result
• Look at the binary representation of the exponent
• only takes O(log2n) multiples for number n
• eg. 75= 74.71= 3.7 = 10 mod 11
• eg. 3129= 3128.31= 5.3 = 4 mod 11
Exponentiation
c = 0; f = 1
for i = k down to 0
do c = 2 x c
f = (f x f) mod n
if bi== 1 then
c = c + 1
f = (f x a) mod n
return f
Efficient Encryption
• Encryption uses exponentiation to power e
• Hence, if e is small, this will be faster
• Often choose e=65537 (216-1)
• Also see choices of e=3 or e=17
• But if e is too small (eg, e=3) can attack
• using Chinese remainder theorem & 3 messages with different
moduli
• if e fixed must ensure gcd(e,ø(n))=1
• ie reject any p or q not relatively prime to e
Efficient Decryption
• decryption uses exponentiation to power d
• This is likely large, insecure if not
• can use the Chinese Remainder Theorem (CRT) to
compute mod p & q separately. Then combine to get
the desired answer,
• approximately 4 times faster than doing it directly
• Only the owner of the private key who knows the values
of p & q can use this technique
RSA Key Generation
• Users of RSA must:
• determine two primes at random -p, q
• Select either e or d and compute the other
• Primes p, q must not be easily derived from the modulus
n=p.q
• means must be sufficiently large
• Typically, guess and use a probabilistic test
• exponents e, d are inverses, so use the Inverse algorithm
to compute the other
RSA Security
• Possible approaches to attacking RSA are:
▻Brute force key search -infeasible given the size of the
numbers
▻mathematical attacks -based on the difficulty of
computing ø(n), by factoring modulus n
▻timing attacks -on the running of decryption
▻chosen ciphertext attacks -given properties of RSA
 Is RSA Secure?
• Factoring a 512-bit number is very hard!
• But if you can factor a big number n, then given the public key
<e,n>, you can find d, hence the private key by:
• Knowing factors p, q, such that n = p*q
• Then ø(n) =(p-1)(q-1)
• Then d such that e*d = 1 mod ø(n)
• Threat
• Moore’s law
• Refinement of factorizing algorithms
• For the near future, a key of 1024 or 2048 bits is needed
 Symmetric (DES) vs. Public Key (RSA)
• Exponentiation of RSA is expensive !
• AES and DES are much faster
• 100 times faster in software
• 1,000 to 10,000 times faster in hardware
• RSA often used in combination in AES and DES
• Pass the session key with RSA
Factoring Problem
• The mathematical approach takes 3 forms:
• factor n=p.q, hence compute ø(n)and then d
• determine ø(n)directly and compute d
• find d directly
• Currently believe all equivalent to factoring
• have seen slow improvements over the years
• As of May-05 the best is 200 decimal digits (663) bits with LS (Lattice
Sieve)
• The biggest improvement comes from the improved algorithm
• cfQS(Quadratic Sieve)to GHFS(Generalized Number Field Sieve)to LS
• Currently assume 1024-2048-bit RSA is secure
• ensure p, q of similar size and matching other constraints
Progress in Factoring
Progress in
Factoring
Thank you!