πŸ–ŠοΈ
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page

Was this helpful?

  1. RSA
  2. Public Exponent Attacks

Multi-party RSA with Small e

PreviousSmall eNextWiener's Attack

Last updated 3 years ago

Was this helpful?

Assuming eee is constant between the messages and the message mmm is sent to at least eee people, we can use the Chinese Remainder Theorem to retrieve mmm.

In single-party RSA, we calculate c=memod  Nc = m^e \mod Nc=memodN. Let's pretend this is extrapolated to 3 people:

me=c1mod  N1me=c2mod  N2me=c3mod  N3m^e = c_1 \mod N_1 \\ m^e = c_2 \mod N_2 \\ m^e = c_3 \mod N_3 \\me=c1​modN1​me=c2​modN2​me=c3​modN3​

​The Chinese Remainder Theorem allows us to solve this congruence mod  N1N2N3\mod N_1N_2N_3modN1​N2​N3​. Since m<min⁑N1,N2,N3m < \min{N_1, N_2, N_3}m<minN1​,N2​,N3​, we know that me<N1N2N3m^e < N_1N_2N_3me<N1​N2​N3​. Once we use the Chinese Remainder Theorem to compute memod  N1N2N3m^e \mod N_1N_2N_3memodN1​N2​N3​, we just take the eeeth root to retrieve mmm.​