šŸ–Šļø
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
  1. RSA
  2. Choice of Primes

Fermat Factorisation

Used when p and q are numericaly close

PreviousP=QNextFactorisation Methods

Last updated 3 years ago

Was this helpful?

CtrlK

Was this helpful?

If ppp and qqq are numerically close, we can use Fermat Factorisation.

During Fermat Factorisation, we hope to find aaa and bbb such that

a2āˆ’b2=Na^2 - b^2 = Na2āˆ’b2=N

Because that then means we can factorise the left-hand expression into

(a+b)(aāˆ’b)=N(a+b)(a-b)=N(a+b)(aāˆ’b)=N

As thus we get the two factors of NNN as (a+b)(a+b)(a+b) and (aāˆ’b)(a-b)(aāˆ’b).

The reason we use this when ppp and $q$ are numerically close is because the closer they are to each other the closer they are to N\sqrt{N}N​. If we say a=Na=\sqrt{N}a=N​ rounded up to the nearest number, we can calculate b2=a2āˆ’Nb^2 = a^2-Nb2=a2āˆ’N (as rearranged from before) until bbb is a whole number, after which we've solved the equation.

An example of this attack can be found in this writeup, which may make it a bit clearer.