With RSA, we create a public key (\(e,N\)) and a private key (\(d,N\)), and where the modulus (\(N\)) is generated from two random prime numbers (\(p\) and \(q\)). We encrypt a message (\(M\)) with \(C=M^e \pmod N\), and recover the message with \(m=C^d \pmod N\). In this case, we will use 256-bit prime numbers (\(p\) and \(q\)), and produce a 512-bit public modulus (\(N\)).
RSA with parameters |
Theory
We start by generating two prime numbers (\(p,q\)) and then calculate the modulus (\(N\)):
\(N=pq\)
It is this modulus (N) that provides the core of the security of RSA, and it must be difficult to determine the prime numbers for a given modulus value. Our prime numbers must thus be of a size that makes it difficult to factorize, and they must be randomly generated. Next we calculate PHI, which is:
\(\varphi=(p-1)(q-1)\)
We then pick \(e\) so that it does not share a factor with PHI:
\( \textrm{GCD} (e,\varphi)=1 \)
and where GCD is the greatest common denominator. In practice \(e\) typically has a value of 65,537 (and which is a prime number, so is safe). The encryption key is now \((e,N)\). Bob and then send this to Alice for her to encrypt a message using this public key.
We determine the decryption value (\(d\)) with:
\(d \times e \pmod {\varphi} = 1\)
For this we use an inverse mod function to determine \(d\). In the code below, we use:
\(d=e^{-1} \pmod \varphi\)
To encrypt a message (\(M\)), we use:
\(C=M^e \pmod N\)
and to decrypt:
\(M=C^d \pmod N\)
Coding
The following defines the Sage code:
p, q = random_prime(2^256), random_prime(2^256) n = p*q ZZn = IntegerModRing(n) r = (p-1)*(q-1) ZZr = IntegerModRing(r) e = Integer(65537) d = ZZr(e)^-1 m = ZZn.random_element() str=sys.argv[1] m=ZZn((str.split(";")[2]).replace(' ','')) c = m^e mess = c^d print (f"p={p},q={q}") print (f"n={n}") print (f"e={e}, d={d}") print (f"\nm={m}") print (f"c={c}") print (f"dec={mess}") print (c^d == m)
and a sample run is:
p=6270461986659252399853005193902251526899399863104388724227943251297211729813 q=43833706629392418280321402669161699520998187522737454106262814540843690854833 N=274857591153978825393246382385749998498235339138282672095369778006172251105137335488704335139719747904488094341491869270481540305863765781495324601236229 e=65537, d=269585821129709307662509383398019590513245458287819249619152071810378142133985492611124629772340262513741198918133855681361543818053602064843380810066433 m=2 c=79072506227930380500282345301044714489898168370295214796635010424851523851395561279777531588617084083373910005077498161206699271372900728788856346691493 dec=2 True
If we modify for 512-bit RSA, we can generate with two 256-bit prime numbers:
p, q = random_prime(2^256), random_prime(2^256)
and a sample run is:
p=4872857963647940184804122939617147699719752147824912110917486555872011329627,q=89666185651958144812540370954883807798087938375013681684760720848627522358819 n=436930586824078917394505045967325024762007757582276104846982009871658874783097105811888667054867042064415815686378427798447234015822983748725427579430513 e=65537, d=31481243129580247004544804111535602284605652246875929125340632781695427113315197831450713244422611836489336529887213149055022280281565173354249084211881 m=126260074257349857607511026767157663284782653060933047549577115769095296334608135249498219433149189964685631807395832467130124101034730227800350292428894 c=337955392187679186204918076458344661289384166711221993050682679811785982819210142276758835993479722286545144839883925910963949434136950735205530336582082 dec=126260074257349857607511026767157663284782653060933047549577115769095296334608135249498219433149189964685631807395832467130124101034730227800350292428894 True