Page 1

• RSA Algorithm introduced in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman

• Motivated by the works of Diffie and Hellman

• Implements public-key encryption and digital signatures

Public-key encryption

• Encryption keys are public, decryption keys are not

• Allows for secure transmission of messages without the need for a secure channel

• Each person has their own encryption and decryption keys

• Decryption key cannot be easily deduced from the public encryption key

Digital signatures

• Used for verifying the origin of a transmitted message

• Done using the sender's decryption key

• Signatures cannot be forged and the signer cannot deny having signed the message

• Useful for electronic mail, fund transfers, and other electronic transactions

Security of the RSA algorithm

• No known successful attempts to break it

• Difficulty of factoring large numbers is a key factor in its security

Public-key cryptosystems

• Each user has their own encryption and decryption procedures

• Encryption procedure is public, decryption procedure is kept secret

• Procedures are related to the keys, which are sets of two special numbers

• Deciphering an enciphered message gives the original message

Page 2

• Reversing the procedures still returns M: E(D(M)) = M

• E and D are easy to compute

• The publicity of E does not compromise the secrecy of D

• An E that satisfies (a), (c), and (d) is called a "trap-door one-way function" and is also a "trap-door one-way permutation"

• Statement (b) is needed to provide "signatures"

Privacy

• Encryption assures a message is delivered privately

• Without property (d), encryption process is not public-key

• NBS standard requires keys to be delivered privately through another secure "courier"

• RSA is a great answer to this problem

• An efficient computing method of D must be found to make RSA stand-alone and reliable

• Bob wants to send a private message to Alice

• Alice decodes the message with her own DA

• No beforehand communication is needed

• No eavesdropper can deduce D from listening in on E

Page 3

• Signatures

  • Digital signature needed to ensure message originated from sender

  • Bob wants to send private message to Alice

  • Decrypt message with Bob's key and encrypt with Alice's key

  • Alice can decrypt the document and verify the signature

  • Message need not be sent separately, can be deduced from signature

  • Assures message cannot be modified or forged

  • Signatures used to assure message came from public file

  • Every user gets a copy of the most recently updated public file

  • Anyone pretending to be in the public file without appropriate signature is identified as an "intruder"

• Applications, predictions, hardware implementation

  • Electronic fund transmissions

  • Financial information security

  • Checks can be electronically signed with RSA

  • Additional measures needed for secure check transmission

Page 4

• RSA can be applied to any electronic system that needs a cryptosystem implemented

• RSA predicted a secure email world and encryption of live telephone conversations

• The encryption device should be a hardware subroutine, not a direct buffer between a terminal and communications channel

• E and D should be easy to compute through simple arithmetic

• The message must be represented numerically to perform arithmetic algorithms on it

• M is represented by an integer between 0 and n-1

• If the message is too long, it is split up and encrypted separately

• Encryption key: (e, n)

• Decryption key: (d, n)

• Encryption algorithm: C ≡ E(M) ≡ Me (mod n)

• Decryption algorithm: M ≡ D(C) ≡ Cd (mod n)

• Encryption and decryption keys are pairs of integers

• Choosing two "random" large primes p and q to obtain n = pq

• d must be coprime to (p-1) · (q-1)

Page 5

• The reason for choosing d to be coprime to (p-1) · (q-1) is not explained

Page 5:

• Introduction of Euler totient function φ(n)

  • Output is the number of positive integers less than n which are coprime to n

  • For primes p, φ(p) = p − 1

  • For n, φ(n) = φ(p) · φ(q) = (p − 1) · (q − 1) = n − (p + q) + 1

• Substituting φ(n) into equation (7) to obtain e · d ≡ 1 (mod φ(n))

  • e · d = k · φ(n) + 1 for some integer k

  • Multiplicative inverse of d modulo φ(n) exists since d and φ(n) are coprime

• Equations for encryption and decryption

  • D(E(M)) ≡ (E(M))d ≡ (Me)d (mod n) = Me·d (mod n)

  • E(D(M)) ≡ (D(M))e ≡ (Md)e (mod n) = Me·d (mod n)

• Using Euler and Fermat's identity: Mφ(n) ≡ 1 (mod n)

  • If M is coprime to n, Mφ(n) = 1

  • M would not be coprime to n if M was either p or q

Page 6

• M is relatively prime to n

  • Equation (9) holds

  • Evaluation: Me·d ≡ Mk·φ(n)+1 ≡ (Mφ(n))kM ≡ 1kM (mod n) = M

• E and D are inverse permutations

Algorithms

Efficient encryption and decryption operations

• Computing Me (mod n) requires at most 2 · log2(e) multiplications and 2 · log2(e) divisions

• Exponentiate by repeated squaring and multiplication

  1. Binary representation of e

  2. Set variable C to 1

  3. Repeat steps 3a and 3b for i = k, k − 1, ..., 0

     • Set C to the remainder of C2 when divided by n

     • If ei = 1 then set C to the remainder of C · M when divided by n

  4. Halt

• C is the encrypted form of M

• Encryption time per block increases no faster than the cube of the number of digits in n

Finding large prime numbers

• Finding n is the first step

• p and q are not explicitly shown

• Generate random odd 100-digit numbers until a prime is found

• Test each number

• Use Solovay and Strassen algorithm to test for primality

• Approximately (ln 10100)/2 = 115 numbers to test

Page 7

• Jacobi symbol and its representation

  • J(a, b) is the Jacobi symbol

  • J(a, b) can be represented as a b =  a p1α1 a p2α1 . . .  a pkαk

  • b = pα1 1 pα2 2 · · ·p αk k is the primal factorization of b

• Definition of Legendre symbol

  • a p = 0 if a ≡ 0 (mod p)

  • a p = +1 if a 6≡ 0 (mod p) and a ≡ x2 (mod p)

  • a p = -1 if there is no such a ≡ 0 (mod p)

  • a 1 ≡ 1

• Conditions for the Jacobi symbol

  • a must be an integer

  • b must be a positive odd integer

  • J(a, b) is 0 if gcd(a, b) 6= 1

  • J(a, b) is ±1 if gcd(a, b) = 1

• Equation (10) and its truth value

  • Equation (10) is always true if b is prime

  • If b is composite, Equation (10) will have a chance of being false of over 50%

  • If (10) is true 100 times for randomly chosen a’s, then b is almost certainly prime, with a chance of being composite of 1 in 2100

• Efficient program for computing J(a, b)

  • J(a, b) = if a = 1 then 1 else if is even then J(a ÷ 2, b) · (−1)(b2−1)÷8 else J(b (mod a), a) · (−1)(a−1)·(b−1)÷4

• Protecting against sophisticated factoring algorithms

  • p and q should differ in length by a few digits

  • gcd(p − 1, q − 1) should be small

  • (p − 1) and (q − 1) should contain large prime factors

  • Generating a large random prime number u and taking the first prime in the sequence i · u + 1, i = 2, 4, 6, ...

• Efficiency of prime number generation

  • Testing a 100-digit number for primality would take several seconds

  • Finding the next prime would take around a minute and a half

  • An average PC can do this much faster today

• Finding large primes using known factorization

  • Take a number whose factorization is known

  • Add 1 to it and test for primality

  • If the number is prime, it can potentially be proven using the factorization of (p − 1)

Page 6.3

• Finding d

  • Find a number d coprime to φ(n)

  • Any prime number greater than max(p, q) is fine

  • A cryptanalyst cannot find d by a direct search due to the large set of primes P

  • Any method of finding d that picks d out of a big set would do

Page 8: Finding e form d and φ(n)

• Use a variation of Euclid's algorithm to find the greatest common divisor of φ(n) and d

• Compute a series x0, x1, x2, ..., where x0 ≡ φ(n), x1 = d, ..., xi+1 ≡ xi−1 (mod xi), until an xk = 0 is found

• gcd(x0, x1) = xk−1

• Find numbers ai and bi such that xi = ai ·x0 +bi ·x1

• If xk−1 = 1, then bk−1 is the multiplicative inverse of x1 (mod n), and is precisely e

• If e < log2(n), find another e that's not too small so that the encrypted message undergoes reduction in modulo n ("wrap-around")

An example

• p = 37, q = 43, n = p · q = 1591, d = 71

• φ(1591) = 36 · 42 = 1512

• Compute e:

  • x0 = 1512, a0 = 1, b0 = 0

  • x1 = 71, a1 = 0, b1 = 1

  • x2 = 21, a2 = 1, b2 = −21

  • x3 = 8, a3 = −3, b3 = 64

  • x4 = 5, a4 = 7, b4 = −149

  • x5 = 3, a5 = −10, b5 = 213

  • x6 = 2, a6 = 17, b6 = −362

  • x7 = 1, a7 = −27, b7 = 575

• Thus e = 575 is the multiplicative inverse in modulo 1512 of d = 71

Encrypting the message

• Use a numerical representation of the English alphabet

• Each block of the message has to be less than n = 1591

• Break the message into two-letter blocks

• Encode the message using the algorithm in section 6.1

• Replace steps 3a and 3b with conditions based on ek

• After step 4, put C into modulo n

• Example: NO ODD is encoded as 1415 0015 0404 575

Decrypting the message

• Check if the message deciphers properly

• Example: 82471 ≡ 1415 (mod 1591)

Page 9: How secure is RSA?

• The RSA algorithm is considered one of the strongest encryption techniques.

• No encryption technique is perfectly secure from a realistic cryptanalyst.

• Brute-force methods may crack a message, but not likely an entire encryption scheme.

• Probabilistic approach - there's always a chance someone may break the code.

• NBS standard and RSA were certified based on attempts to break the algorithm.

• No one has been known to crack RSA despite years of attempts.

• Breaking RSA is at least as hard as factoring n.

• Factoring large numbers is not provably hard, but no algorithms exist to factor a 200-digit number quickly.

• Fermat and Legendre have contributed to factoring algorithms.

• RSA is considered secure because factoring is still a difficult math problem.

• Physical security methods are used to protect the decryption key.

• Encryption device generates encryption and decryption keys but does not print out the decryption key.

• The decryption key is erased if an attempted intrusion is detected.

8.1 Factoring n

• Knowing the factors of n would give away φ(n) and therefore d.

• Factoring numbers is far harder than determining primality or compositeness.

• Many factoring algorithms are available.

• Authors of RSA reference Knuth and Pollard as good sources for factoring algorithms.

• Authors present an unpublished algorithm by Richard Schroeppel.

• Schroeppel's algorithm factors n in approximately exp √ln n · ln ln n = n√ln ln n÷ln n = (ln n)√ln n÷ln ln n steps.

• Authors present a table with data for various lengths of n and the time it takes to factor:

  • 50 digits - 1.4 × 10^10 operations, 3.9 hours

  • 75 digits - 9.0 × 10^12 operations, 104 days

  • 100 digits - 2.3 × 10^15 operations, 74 years

  • 200 digits - 1.2 × 10^23 operations, 3.8 × 10^9 years

  • 300 digits - 1.5 × 10^29 operations, 4.9 × 10^15 years

  • 500 digits - 1.3 × 10^39 operations, 4.2 × 10^25 years

• Authors recommend n to be about 200 digits long for RSA.

• The length of n can be varied based on the importance of encryption speed versus security.

Page 10

• RSA encryption scheme allows the choice of key-length and level of security

• Computing φ(n) without factoring n

  • Computing φ(n) would break the system

  • Computing φ(n) is as difficult as factoring n

  • Factoring n using φ(n) involves obtaining (p + q) from n and φ(n) = n − (p + q) + 1

  • Obtaining q from half the difference of (p − q) and (p + q)

  • Obtaining p from either p = n ÷ q or from half the sum of (p − q) and (p + q)

  • If n is prime, φ(n) = n−1 would be easy to compute, thus n must be composite

• Determining d without factoring n or computing φ(n)

  • Computing d is no easier than factoring n

  • Knowing d allows us to calculate e · d − 1, which is a multiple of φ(n)

  • Miller [6] shows that n can be factored using any such multiple

  • All values d0 differ by the least common multiple (lcm) of (p − 1) and (q − 1)

  • Finding such a d0 is as hard as factoring n

• Other ways of computing d

  • Computing e-th roots modulo n without factoring n is practically impossible

  • Discovering a way to break the code without factoring n would yield an efficient factoring algorithm

  • No known record of anyone breaking RSA in the 31 years since it has been published

Page 11

• Avoiding "reblocking" for encryption of a signed message

  • Reblocking means breaking a signed message into smaller blocks

  • RSA provides a way to avoid reblocking by choosing a threshold value h

  • Every user maintains two public (e, n) pairs, one for enciphering and one for signature verification

  • Message blocking depends on the transmitter's signature n

• Conclusions about RSA

  • RSA is a strong encryption algorithm

  • RSA implements a public-key cryptosystem for secure communications and digital signatures

  • Security of RSA relies on the difficulty of factoring large numbers

  • No one has succeeded in breaking RSA to date

  • Other trap-door one-way permutations exist

  • The size of n must increase over time as factoring algorithms improve and computers get faster

  • RSA keys are typically between 1024 and 2048 bits long

  • Experts predict that these key lengths may be breakable in the near future

  • 4096-bit keys are not expected to be broken soon

  • RSA is slower than certain other symmetric cryptosystems

  • RSA is commonly used to transmit keys for faster algorithms

  • Timing attacks and key distribution problems can potentially damage RSA's security

  • Solutions exist for these issues, but require more hardware and software

  • The Riemann hypothesis poses a major threat to RSA

  • If a solution to the Riemann hypothesis is found, RSA would fall apart

  • More sophisticated algorithms will continue to be developed in number theory and cryptanalysis