RSA from ground up (1)

History and overview

RSA is one of public key cryptosystem used by many systems ( Though it's been gradually replaced by elliptic curve cryptography due to it's faster implementation). Public keys cryptography ( assymetric) uses different keys for encryption and decryption unlike symmetric cryptography.
The first publicly known public key cryptography was developed in 1976 - 1977 by three mathematicians / computer scientist working at MIT: Ronald Rivest , Adi Shamir and Leonard Adleman in their honour it's called RSA. However an ealier classified version of a similar cryptosystem was develop in the UK @ GCHR by Clifford Cocks

Overview of implementation

1) Choose two large primes p and q
2) Multiply them to get the RSA modulus \( N \), i.e. \( N = p \cdot q \)
3) Find the Euler's totient of the RSA modulus: \( \varphi(N) = (p - 1)(q - 1) \)
4) Find the number \( e \) that is co-prime to \( \varphi(N) \), i.e. \( \gcd(e, \varphi(N)) = 1 \)
5) Find the number \( d \) such that \( e \cdot d \equiv 1 \mod \varphi(N) \), i.e. \( d \equiv e^{-1} \mod \varphi(N) \)

Now your public key is ( N,e ) and your private key is ( N , d). With this you can see that RSA is a trapdoor function. It's based on the the number theoretic problem of factoring ( though RSA could be said to originally defined based on the difficulty of computing eth root. See the topic RSA @ malicious cryptography ( exposing cryptography) by Dr Adam L. Young and Dr Moti Yung)
As known computers because if their design and constraints can easily multiply large primes but find it difficult to factor them So RSA can be said to be a "hardware based hardware assumption", so one can assume/believe that no one currently has the hardware fast enough to factor big N

RSA process in details

1) prime number generation: The prime numbers are randomly generated with CSPRNG indepenent of other keys or previous values. The prime number must be large enough e.g 2048 bit prime. Then they are tested for primality using probabilistic prime testing algorithms. NB: use Miller-Rabin algorithm ( widely adopted in cryptography implementations) as their are constraints in using other in using some other algorithms which Miller-Rabin can help serve better. e.g Fermat's test based on Fermat's little theorem fails to identify Carmicheals numbers as composite as the suite into it's criteria where P is prime and A is a number co-prime to it then \( A^{P-1} \equiv 1 \mod P \) So one can ask is there a way to identify or test Carmicheals numbers? yes. it's based on Koselt's criterion on which Koselt's test is carried out Koselt's test: factor N, then check if the distinct factors ( if not disqualified) and the next step is to check if P-1 is divisble by N-1 ( if so then it's a Carmicheals number)
So with the above there is no need of thinking to combine Fermat's test and Koselt's test as Koselt's test is still based on the factoring problem. oooooh noooo factoring of large integers, lol.
2) Multiplication of the large primes : Multiply the large primes generated p and q. So computationally we know that this favours the defender over the attacker ( Multiplication over factoring)
3)Finding the euler's totient of the prime modulus : Before i step further, what is euler's totient ? euler's totient can be defined as numbers \( \leq N \) which are co-prime to it ( Two numbers a and b are said to be (co-prime if their greatest common multiple is 1 i.e \( \gcd(a, b) = 1 \) ))
You can check if a number is co-prime to another using extended euclidean algorithm There is a general formula for calculating euler's totient : \( \varphi(N) = N \cdot \prod \left(1 - \frac{1}{p} \right) \) where p is or are distinct prime(s)
Remember from what we know about prime numbers: if \( P \) is prime, it means all numbers less than \( P \) are co-prime to it. So, one can say \( \varphi(P) = P - 1 \).
Euler's totient function is multiplicative in nature: if \( a \) and \( b \) are co-prime, then \( \varphi(a \cdot b) = \varphi(a) \cdot \varphi(b) \). In particular, for primes: \( \varphi(p \cdot q) = \varphi(p) \cdot \varphi(q) \).
Though it might not be of much interest in RSA, you can look up the term co-totient, which is defined as \( N - \varphi(N) \).
4) Find the number \( e \) that is co-prime to \( \varphi(N) \) : since co-primality is ealier stated one could decide to swallow further definition, but i would love to state ways to know likely co-prime numbers

If they are prime numbers they are co-prime
No common prime factors
Different prime factors
consecutive numbers e.g 14 & 15 , 18 & 19 etc

NB: It's better to Choose large e to avoid certain attacks on RSA like low exponent attack ( see the paper @ RSA survey by Dan boneh) or maybe just use the common public modulus e = 65537
Why use e = 65537 ?
Exploring e = 65537 the most common public exponent used in RSA: e = 65537 is a fermats prime used since O(N) is always even its co-prime to e. it's efficient for encryption and signature verification due to it's binary representation ( Like kinda looking at the hamming weight) Hamming is the number of non-zero bits ( 1's in a binary representation of numbers)
Lower hamming = faster modular exponentiation and vice versa You can calculate hamming weight using algorithms like Brian Kerninghan's algorithm
5) Find a number \( d \) such that \( e \cdot d \equiv 1 \mod \varphi(N) \) : This is the same as saying find the inverse of e. what gives us the confidence that e has inverse? it has inverse if it satisfies the condition below :
=> For a number to A to have inverse modulo B, A and B must be co-prime. e and \( \varphi(N) \) are co-prime so there exist an inverse obviously.
We can find inverse using extended euclidean algorithm ( eea) via kinda linear combination of gcd(a,b) = 1
It satisfies Bezout's theorem this way ( trying to dipict it below):
Bezout's theorem (Bezout's identity) : states that for any two integer a and b not both zero there exist integers x and y such that ax + by = gcd(a,b). Now let's take gcd(a,b ) = d
ax + by = d, so if d = 1 that means ax + by = 1 By congruence, \( ax \equiv 1 \mod b \)
Now the public key becomes ( N , e) and the private key (N, d)
To encrypt and decrypt a message respectively (take note: for RSA to work properly, \( M < N \)):
\( C = M^e \mod N \)
\( M = C^d \mod N \)
Note: The reason why decryption wroks is due to the concequence of eulers theorem ( a generalized form of fermats little theorem)

Relating RSA to game theory

RSA can be seen as a game between two players

Players

Player 1(Defender): choose strategy e.g large enough primes, strong key size, padding.
Player 2(Attacker): choose strategy e.g hardware, Factoring algorithms, quantum approaches

Strategy

Defender picks p, q, key sizes and randomness
Attacker picks computation methods, hardware and attack models

Payoff function

Defender payoff is 1 if factoring fails , 0 if it succeeds and vice versa
The above creates a zero sum game

Minimax principle

The player tries to minimize the maximum loss by choosing parameters that make factoring as hard as possible e.g 2048 bit keys

Information assymetry

The attacker knows N ( public key ) but not p and q. This is the assymetry for the security

Cost of attack vs defence

Cheap to multiply but hard to factor

References

Discrete mathematics with applications by SUSANNA S. EPP
An Introduction to Computer Networks Release 2.0.11 by Peter L Dordal
A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup
Understanding Cryptography by Christof Paar, Jan Pelzl and Tim Güneysu
Cryptography Made Simple by Nigel P. Smart
The Joy of Cryptography by Mike Rosulek
Nick Yung's blog on public key cryptography

RSA from ground up (2) loading .............
← Back