# RSA Demonstration

## 2760 days ago by jimlb

def random_between(j,k): a=int(random()*(k-j+1))+j return a

We begin by having SAGE pick two large random primes.  We keep these primes a secret.  We calculate $n = pq$ and post this on our website.

# Generate random primes p and q and compute n = p*q p = random_prime(10^100); print 'p = ', p, '\n' q = random_prime(10^100); print 'q = ', q, '\n' n = p*q; print 'n = ', n, '\n'
 p = 646442584158982459281028347914134804046251918008956416997750322267252662\ 7913529500600001140807562101 q = 260592915996849375852958103936576284107206896755219528880770706579042641\ 2707606539735758849889039619 n = 168458358030527949041566987438940938503755259056329259341806182040866486\ 942829605959384515087489338946405125377738123757034313041831963998706323\ 43916731551853901861540102976234122546550902111591879519  p = 6464425841589824592810283479141348040462519180089564169977503222672526627913529500600001140807562101 q = 2605929159968493758529581039365762841072068967552195288807707065790426412707606539735758849889039619 n = 16845835803052794904156698743894093850375525905632925934180618204086648694282960595938451508748933894640512537773812375703431304183196399870632343916731551853901861540102976234122546550902111591879519 

You can ask SAGE to factor $n$, but it will take a long time!  If you try it, be prepared to use the "interuppt" command above.

n.factor()
 Traceback (click to the left of this block for traceback) ... __SAGE__ ^CTraceback (most recent call last): File "", line 1, in File "_sage_input_22.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bi5mYWN0b3IoKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in File "/tmp/tmpZ4B3q7/___code___.py", line 2, in exec compile(u'n.factor() File "", line 1, in File "integer.pyx", line 3581, in sage.rings.integer.Integer.factor (build/cythonized/sage/rings/integer.c:22697) File "factorint.pyx", line 301, in sage.rings.factorint.factor_using_pari (build/cythonized/sage/rings/factorint.c:7208) File "factorint.pyx", line 342, in sage.rings.factorint.factor_using_pari (build/cythonized/sage/rings/factorint.c:6875) File "gen.pyx", line 8741, in sage.libs.pari.gen.gen.factor (build/cythonized/sage/libs/pari/gen.c:46926) File "c_lib.pyx", line 73, in sage.ext.c_lib.sig_raise_exception (build/cythonized/sage/ext/c_lib.c:872) KeyboardInterrupt __SAGE__

Our next step is to generate the encryption key.  We take this to be any integer that is relatively prime to $k=(p-1)(q-1)$.  Note that since no one knows $p$ or $q$, no one will know $k$ as one cannot obtain this from $n$ without factoring $n$.  We publish the encryption key $e$ on our website.

# Generate the encryption key phi_n = (p-1)*(q-1) R1 = Zmod(phi_n) e = random_between(1,10^100) while gcd(e, phi_n) > 1: e = random_between(1,10^100) e = R1(e) print 'encryption key = ', e, '\n'
 encryption key = 348201124442540705770895847914430042221236638883821823041550070986842641\ 9939723397611340825574244353  encryption key = 3482011244425407057708958479144300422212366388838218230415500709868426419939723397611340825574244353

We now calculate the decryption key $d$.  Since the greatest common divisor of $k$ and $e$ is 1, the Euclidean algorithm gives integers $d$ and $x$ so that $de + kx = 1$.  The decryption key is $d$.  (We will see why this is true below.)  We keep $d$ secret.  Note that since no one knows $k$, they cannot calculate $d$ even though they know $e$ and $n$.

# Compute the decryption key # Decryption Key d = R1(1/e) print 'decryption key = ', d, '\n'
 decryption key = 160699905811829656884589181149452649250221339069027900638929359397603707\ 620015904510745221342517122660380040541256441282297340285065868820238037\ 47637571488168375216891951984696037539372485248375172817  decryption key = 16069990581182965688458918114945264925022133906902790063892935939760370762001590451074522134251712266038004054125644128229734028506586882023803747637571488168375216891951984696037539372485248375172817

This is a quick check that $ed \equiv 1 \pmod{k}$.

# Should evaluate to 1 e*d
 1 1

We print one last time all the relevant information we have so far.

# Encryption & Decryption Key Information print 'n = ', n, '\n' print 'Encryption key is e = ', e, '\n' print 'Decryption key is d = ', d
 n = 250270783030669003430577400776482490340863082876283879835917960134969055\ 725656687185449877913318903154110891723931208269075456860412904421878113\ 7461678927382165349016861801385881417208618389624354961 Encryption key is e = 767844991449893682647110891418202675259593735189214325676808685373587377\ 9053526517784346777159204865 Decryption key is d = 946140962020399178995560401406293636385919285379233643095834275613286618\ 618862095856506598806429196432600828373942209610795830014274170379871366\ 386065947688241128554361367305062159207611981615628289 n = 2502707830306690034305774007764824903408630828762838798359179601349690557256566871854498779133189031541108917239312082690754568604129044218781137461678927382165349016861801385881417208618389624354961 Encryption key is e = 7678449914498936826471108914182026752595937351892143256768086853735873779053526517784346777159204865 Decryption key is d = 946140962020399178995560401406293636385919285379233643095834275613286618618862095856506598806429196432600828373942209610795830014274170379871366386065947688241128554361367305062159207611981615628289

Here we enter the message we would like to send.  For example, here we have "I hope this works" as our message.

# Enter any message you would like to send message = 'I hope this works' print 'The message we are encrypting is "',message, '"', '\n'
 The message we are encrypting is " I hope this works "  The message we are encrypting is " I hope this works "

The message is encrypted by calculating the number $(\textrm{message})^{e} \pmod{n}$.  This giant number is what will be sent to us.  Note the only things needed to calculate this are $e$ and $n$, both of which we've made available to the public.

# Encryption Algorithm R = Zmod(n) ciphertext = [] for k in range(0,len(message)): M = R(ord(message[k])) E = M^e ciphertext.append(E) print 'encoded message = ', ciphertext, '\n'
 encoded message = [29911786634081440879695040848910549738234690013693253420361913845686760\ 477821927312995300137602268331689053331767434427171475900861738964613803\ 42565288786377189464144992701067848506779576231889659861, 282586994520791811691055077314304476118234264038621362503982558806015767\ 291557413384274265856736782202917628242097265939054187807837386966449571\ 2756365679367590294804101174773395542909451029637542834, 125415050560248576036166147190612995261966931083122375252030082753288303\ 370540147204921809034385844510000327680151556376199945239107832028127933\ 75154328386411239186699953405627704003740450120362808433, 778113673304924683900462034719822695382149354870697554750405548886201664\ 364599762638109806202962309022703632345786966656111134952787323810644337\ 8647773024328021477890178907984793514952120408465458877, 208511594999819493234417269207910412928781981702505121240427930605213499\ 012371479702726939108095175218825558917696301278635191712544027710674585\ 8370752639997109092135214609406615295655359940307089502, 969589241955076305734700652030378744431679067527843096963104731574894638\ 201624792438728464885934037776738008771623365469023016703572645600151134\ 3788719277529939884616510454084766708515150424078675151, 969589241955076305734700652030378744431679067527843096963104731574894638\ 201624792438728464885934037776738008771623365469023016703572645600151134\ 3788719277529939884616510454084766708515150424078675151, 118298782585258837273346901968561007206301316043524690217615653795229163\ 629063287597072585820626224926170357993966024624306610130381356014276287\ 47194066321186634075943450816740093291836772132976713913, 282586994520791811691055077314304476118234264038621362503982558806015767\ 291557413384274265856736782202917628242097265939054187807837386966449571\ 2756365679367590294804101174773395542909451029637542834, 256909489126822662105658315001387929970828501929082375046885185474529986\ 650788156303353512577691054464180701044482864210702863018454236436230824\ 8045855939228797778638906607251070251061575536908037780, 630218077430845941741863476118294786842961058017771430472132735398621878\ 959881991170836524065261063109830760715673114413948499046773716356561408\ 6353631704914570491482331757090611816543494302487743014, 146753921052856782952640568507887425094500831833905888251240173199571591\ 052121421978753042556619515202336293046265648707586941998730803363586761\ 14460600131839122384956669360832749585108075996031222687, 778113673304924683900462034719822695382149354870697554750405548886201664\ 364599762638109806202962309022703632345786966656111134952787323810644337\ 8647773024328021477890178907984793514952120408465458877, 282586994520791811691055077314304476118234264038621362503982558806015767\ 291557413384274265856736782202917628242097265939054187807837386966449571\ 2756365679367590294804101174773395542909451029637542834, 155234043913425337148140479546997808867974300666754349862283947534308596\ 808592312699960157839657195073291892297493253080409785218429020892108265\ 48936341923671438270055605910696402414046238061629570102, 256909489126822662105658315001387929970828501929082375046885185474529986\ 650788156303353512577691054464180701044482864210702863018454236436230824\ 8045855939228797778638906607251070251061575536908037780, 458718414467736298467502592301345561279231910074413228739649100227160993\ 201231313843973225167895901710328779706866627042727019139473066738146297\ 48406115629142368866086783201679469879626340422843338, 124928392976274407502257033001197253601812889109248556251580981826018538\ 562203950248984710482093386617919047173494645370564122561673826234469818\ 29257618369917992521189185157697446735810041899978065319, 282586994520791811691055077314304476118234264038621362503982558806015767\ 291557413384274265856736782202917628242097265939054187807837386966449571\ 2756365679367590294804101174773395542909451029637542834, 570574206972796279422999247137414685463996632400529724832834564062418684\ 091189929520937938081862937952266226252762903015324392746152800954412594\ 06768069636091789793729746289650891541020245736873120, 630218077430845941741863476118294786842961058017771430472132735398621878\ 959881991170836524065261063109830760715673114413948499046773716356561408\ 6353631704914570491482331757090611816543494302487743014, 125415050560248576036166147190612995261966931083122375252030082753288303\ 370540147204921809034385844510000327680151556376199945239107832028127933\ 75154328386411239186699953405627704003740450120362808433, 101652212670626847126887521230614748308460063754762238903929395281881348\ 123813977817197242842671537570298393422972119120956154031022386681424214\ 22623381410808338186928101495517720510607894248358063780, 124928392976274407502257033001197253601812889109248556251580981826018538\ 562203950248984710482093386617919047173494645370564122561673826234469818\ 29257618369917992521189185157697446735810041899978065319]  encoded message = [2991178663408144087969504084891054973823469001369325342036191384568676047782192731299530013760226833168905333176743442717147590086173896461380342565288786377189464144992701067848506779576231889659861, 2825869945207918116910550773143044761182342640386213625039825588060157672915574133842742658567367822029176282420972659390541878078373869664495712756365679367590294804101174773395542909451029637542834, 12541505056024857603616614719061299526196693108312237525203008275328830337054014720492180903438584451000032768015155637619994523910783202812793375154328386411239186699953405627704003740450120362808433, 7781136733049246839004620347198226953821493548706975547504055488862016643645997626381098062029623090227036323457869666561111349527873238106443378647773024328021477890178907984793514952120408465458877, 2085115949998194932344172692079104129287819817025051212404279306052134990123714797027269391080951752188255589176963012786351917125440277106745858370752639997109092135214609406615295655359940307089502, 9695892419550763057347006520303787444316790675278430969631047315748946382016247924387284648859340377767380087716233654690230167035726456001511343788719277529939884616510454084766708515150424078675151, 9695892419550763057347006520303787444316790675278430969631047315748946382016247924387284648859340377767380087716233654690230167035726456001511343788719277529939884616510454084766708515150424078675151, 11829878258525883727334690196856100720630131604352469021761565379522916362906328759707258582062622492617035799396602462430661013038135601427628747194066321186634075943450816740093291836772132976713913, 2825869945207918116910550773143044761182342640386213625039825588060157672915574133842742658567367822029176282420972659390541878078373869664495712756365679367590294804101174773395542909451029637542834, 2569094891268226621056583150013879299708285019290823750468851854745299866507881563033535125776910544641807010444828642107028630184542364362308248045855939228797778638906607251070251061575536908037780, 6302180774308459417418634761182947868429610580177714304721327353986218789598819911708365240652610631098307607156731144139484990467737163565614086353631704914570491482331757090611816543494302487743014, 14675392105285678295264056850788742509450083183390588825124017319957159105212142197875304255661951520233629304626564870758694199873080336358676114460600131839122384956669360832749585108075996031222687, 7781136733049246839004620347198226953821493548706975547504055488862016643645997626381098062029623090227036323457869666561111349527873238106443378647773024328021477890178907984793514952120408465458877, 2825869945207918116910550773143044761182342640386213625039825588060157672915574133842742658567367822029176282420972659390541878078373869664495712756365679367590294804101174773395542909451029637542834, 15523404391342533714814047954699780886797430066675434986228394753430859680859231269996015783965719507329189229749325308040978521842902089210826548936341923671438270055605910696402414046238061629570102, 2569094891268226621056583150013879299708285019290823750468851854745299866507881563033535125776910544641807010444828642107028630184542364362308248045855939228797778638906607251070251061575536908037780, 45871841446773629846750259230134556127923191007441322873964910022716099320123131384397322516789590171032877970686662704272701913947306673814629748406115629142368866086783201679469879626340422843338, 12492839297627440750225703300119725360181288910924855625158098182601853856220395024898471048209338661791904717349464537056412256167382623446981829257618369917992521189185157697446735810041899978065319, 2825869945207918116910550773143044761182342640386213625039825588060157672915574133842742658567367822029176282420972659390541878078373869664495712756365679367590294804101174773395542909451029637542834, 57057420697279627942299924713741468546399663240052972483283456406241868409118992952093793808186293795226622625276290301532439274615280095441259406768069636091789793729746289650891541020245736873120, 6302180774308459417418634761182947868429610580177714304721327353986218789598819911708365240652610631098307607156731144139484990467737163565614086353631704914570491482331757090611816543494302487743014, 12541505056024857603616614719061299526196693108312237525203008275328830337054014720492180903438584451000032768015155637619994523910783202812793375154328386411239186699953405627704003740450120362808433, 10165221267062684712688752123061474830846006375476223890392939528188134812381397781719724284267153757029839342297211912095615403102238668142421422623381410808338186928101495517720510607894248358063780, 12492839297627440750225703300119725360181288910924855625158098182601853856220395024898471048209338661791904717349464537056412256167382623446981829257618369917992521189185157697446735810041899978065319]

Assuming we have received the encoded message, which is sent to us as the remainder of $(\textrm{message})^{e}$ when divided by $n$, we calculate $((\textrm{message})^{e})^{d} \pmod{n}$.  This will give us back the original message.  Since we are the only ones that know $d$, we are the only ones that can recover the original message once it is encoded.  See below for why this works.

# Decryption Algorithm R2 = Zmod(n) plaintext = '' for k in range(0,len(ciphertext)): E = R2(ciphertext[k]) D = R2(E^d) plaintext += chr(D) print 'decoded message = ', plaintext, '\n'
 decoded message = I really hope this works  decoded message = I really hope this works

The point now is to see why this works.  The claim is that for any number $a$, we have $a^{k} \equiv a \pmod{n}$ when $n = pq$ and $k = (p-1)(q-1)$.  We show the easier case of when $n$ is a prime, namely, we have $a^{p} \equiv a \pmod{p}$ for any prime number $p$.

Theorem (Fermat's Little Theorem):  Let $a$ be an integer and $p$ a prime number.  Then $a^{p} \equiv a \pmod{p}$.

Proof:  If $a \equiv 0 \pmod{p}$ the result is true, so assume $p \nmid a$.  Consider the set $X = \{a, 2a, 3a, \dots, (p-1)a\}$.  There are $p-1$ elements in this set, and we claim that if $ra \equiv sa \pmod{p}$, then $r \equiv s \pmod{p}$.  If $ra \equiv sa \pmod{p}$, then $p \mid (ra - sa)$.  This gives $p \mid a (r-s)$.  Since $p$ is prime, $p \mid a$ or $p \mid (r-s)$.  We assumed $p \nmid a$, so it must be that $p \mid (r-s)$, so $r \equiv s \pmod{p}$.  This shows all the elements in $X$ are distinct when considered modulo $p$.  Since there are $p-1$ elements in $X$ and they are all distinct, there is a bijection between $X$ and the set $\{1, 2, \dots, p-1\}$ modulo $p$.  Thus, we must have $a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}$. Factoring out the $a$'s in the left hand side we see $a^{p-1} (p-1)! \equiv (p-1)! \pmod{p}$.  Since $p \nmid (p-1)!$, we have $a^{p-1} \equiv 1 \pmod{p}$.  Multiplying both sides by $a$ gives the result. $\square$

The key in the above result is that $p-1$ is how many integers $1 \leq b \leq p-1$ satisfy that $b$ and $p$ have greatest common divisor 1.  If we consider $n = pq$, there are $(p-1)(q-1)$ elements between 1 and $n-1$ that have greatest common divisor with $n$ of 1. The elements that have a common divisor with $n$ are $\{p, 2p, \dots, (q-1)p\}$ and $\{q, 2q, \dots, q(p-1)\}$.  There are $q-1$ elements in the first set and $p-1$ in the second set, so there are $(p-1)(q-1) = (n-1) - (p-1) - (q-1)$ elements that are relatively prime to $n$ between $1$ and $n-1$.  The same type of argument now works, but we have to set $X$ to be the elements that are relatively prime to $n$.  It is a bit messier, but the same idea.