Page 1:

• RSA cryptosystem has withstood attacks and is still considered secure

• Legitimate threat to RSA is the rise of quantum computers

• Hastad Broadcast Attack is one of the attacks that can be used against RSA

Introduction

• RSA was invented by Ronald Rivest, Adi Shamir, and Len Adleman in response to an open problem posed by Diffie and Helman

• Diffie and Helman hypothesized the concept of an asymmetric public-private key cryptosystem

• RSA-129, a large number with 129 digits, was generated to test the hypothesis

• It took 17 years to factorize RSA-129, leading to the need for bigger prime numbers

• Prime factorization is a hard problem in computer science

• RSA algorithm involves choosing large random prime numbers, calculating modulus and totient, and choosing public and private key exponents

Page 2

• Correctness of RSA

  • Public key consists of N and e

  • Encryption function: f(M) ≡ Me(modN)

  • Private key is a positive integer d

  • Decryption function: g(C) ≡ Cd(modN)

• Tools needed to prove the correctness of RSA

  • Fermat's Little Theorem

  • Euclid's Lemma

Page 2 (continued)

• Fermat's Little Theorem

  • If p is a prime number and a is an integer relatively prime to p, then ap-1 ≡ 1 (mod p)

• Euclid's Lemma

  • If d divides a * b, then either d divides a or d divides b

• Lemma 2

  • If a ≡ M (mod p) and a ≡ M (mod q), then a ≡ M (mod p * q)

• Proof that (Me)d ≡ M (mod N = p * q)

  • Show that (Me)d ≡ M (mod p)

  • Show that (Me)d ≡ M (mod q)

  • Use Lemma 2 to conclude that (Me)d ≡ M (mod N = p * q)

Page 2 (continued)

• Attacks on RSA

  • Exploits on RSA due to poor implementation

  • Low public key exponent

• Coppersmith Theorem

  • An algorithm to find all roots of a polynomial modulo N that are smaller than X = N1/d

• Chinese Remainder Theorem

  • Simultaneous congruences have a solution modulo m, where m = m1m2....mk

• Hastad Broadcast Attack

  • When the same message is encrypted with the same small public exponent e and different moduli (Ni, e)

  • If k ≥ 3 ciphertexts are known, the message M is no longer secure

Page 3

• Generalizations:

  • Hastad Broadcast attack

  • Linear-padding does not protect against the attack

  • System of univariate equations modulo relatively prime composites

  • Randomized padding should be used in RSA encryption

• Theorem 2 (Hastad):

  • Relatively prime integers N1...Nk

  • Polynomials gi(x) of maximum degree q

  • Unique M satisfying gi(M) ≡ 0modNi for all i

  • k > q

  • Efficient algorithm to compute M

• Proof:

  • Chinese Remainder Theorem to compute coefficients Ti

  • Setting g(x) = Pi · Ti · gi(x)

  • g(M) ≡ 0(mod Q Ni)

  • Compute integer roots x0 satisfying g(x0) ≡ 0(mod Q Ni) and |x0| < Q Ni) 1 q

  • M < Nmin < (Q N1) 1k < (Q N1) 1 q

• Practical Example:

  • Challenge from PlaidCTF

  • Public key exponent e=5

  • Prime numbers p and q are 1024 bits long

  • 5 encrypted messages of the same message M

  • Linear padding applied to M and raised to the power of e

  • Script called generate.sage

  • Four numbers ai, bi, ci, and ni written onto data.txt 5 times

• Using CRT to compute c* such that c∗ = ci(modni)

• Linear padding makes standard broadcast attack infeasible

• Using Theorem 2 to construct polynomial g(x)

• Coppersmith’s method to find m

• Solution code

Page 4:

• Code for RSA encryption

  • Defines a matrix and a list

  • Iterates through the matrix and performs calculations

  • Defines a polynomial ring and performs calculations

  • Prints the result

II. CONCLUSION

• Studied number theory and prime numbers

  • Discovered open problems like Goldbach conjecture and Twin Prime conjecture

• Importance of understanding RSA algorithm

  • Highlighted the need for strong encryption in online transactions

  • Proved the correctness of RSA

  • Factorizing large integers is computationally hard

  • Low public key exponents and linear padding are not secure

  • Randomized padding is recommended

• Acknowledgment

  • Thanked Prof. Koc for support and cooperation

• References

  • Boneh, Dan. "Twenty years of attacks on the RSA cryptosystem."

  • Durfee, Glenn. "Cryptanalysis of RSA using algebraic and lattice methods."

  • Wikipedia contributors. "Coppersmith's attack."

  • Ma, Dan. "Fermat's little theorem and RSA algorithm."