Sage and RSAWith 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\). TheoryWe 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\) CodingThe following defines the Sage code: p, q = random_prime(2^512), random_prime(2^512) 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() 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=8782263196713947800371958894134599580018573479365740261354098538071076647452997129939183356613006391137183984631097318596317558554161134794440697454307211,q=2252071705528496304773548575613482975107515563371070129624065161327112517229703552446585458197108450000795403437111884723279944944050098057756860053418617 n=19778286455823724467076730645129920234154202032253759526949358739974558038295597117966707448613913258926845895329960634639080888031911776124774195836901956709363607378449240521720700896270317894229239696088877976577782005728309993878980019876492014637189652438722388328888768346704623697057329241971904747187 e=65537, d=3457284429221914147654470394900718162297183857691061066889419011018944060404265690883418535046172243072858790864702824823005487790005360441970386003441547364895079818088634372490330287221554393271191790370238904036372283625561876266209586894999009033187734892444481305081351005856967721525324763428465329153 m=18962457078142675866446999602346621091114743056606616921205390668748641331788480727232782944499325680193029909204487643139190299156941713168320148538089025397862204593219794345683769771362855780495648759012253926353196488758146962544303719465939423598886970396123986244223452761723122722872637498598614066297 c=8531188790056977129279973769889729518058409692364521680248470599344102866406840148805932446560809958450579655800776982356622408446063859381476275796104519454740559608487202180180555785031080547592646142793160853880152369704260469780746798126279319340358086280169428405761943673892083693174601349649788013259 dec=18962457078142675866446999602346621091114743056606616921205390668748641331788480727232782944499325680193029909204487643139190299156941713168320148538089025397862204593219794345683769771362855780495648759012253926353196488758146962544303719465939423598886970396123986244223452761723122722872637498598614066297 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 |