MATH 2500
Hayne Floyd
RSA Homework
The my_div(a,b) function from the previous homeowkr.
Returns a list [q,r] where a=bq+r.
|
The my_gcd(a,b) function from the previous homeowkr. It returns
[d,m,n] where d=gcd(a,b) and am+bn=d.
|
Calculate two 100 digit primes p,q.
p= 892865435574141139887424433109814969279259831981891329430982083149285096\ 754369120652734342979229193 p= 892865435574141139887424433109814969279259831981891329430982083149285096754369120652734342979229193 |
q= 970848498221124871309703769944431020918532114012241612565856315340880242\ 5461848399836595379103448623 q= 9708484982211248713097037699444310209185321140122416125658563153408802425461848399836595379103448623 |
Multiply p and q together to get m.
Rm will be a function that takes an integer, x, and
translates it into an integer in the ring of integers modulo M.
m= 866837067240705447837928461916953019099589075418114660803908716686180587\ 350932511186571525715755210017710467435466525141283604808897916154247261\ 5236002721908657490098499187857382471811710124617251239 m= 8668370672407054478379284619169530190995890754181146608039087166861805873509325111865715257157552100177104674354665251412836048088979161542472615236002721908657490098499187857382471811710124617251239 |
Calculate phi = (p-1)(q-1)
phi= 866837067240705447837928461916953019099589075418114660803908716686180587\ 350932511186571525715755208957575425656927539842837391553485398307789164\ 3131695266819112253540411665641164951322380402534573424 phi= 8668370672407054478379284619169530190995890754181146608039087166861805873509325111865715257157552089575754256569275398428373915534853983077891643131695266819112253540411665641164951322380402534573424 |
My CUID is C65099899. We take the number, 65099899
and calculate its equivalence in the ring of integers modulo m.
65099899 65099899 |
Here we must find an integer, e, such that
gcd(e,phi) = 1. In this case 1<=e<=10000000.
This allows the later calculations to run in real time.
e= 154290553236243076694946471381992707055497449259524227623383816536659562\ 3027934305811724028444934145 e= 1542905532362430766949464713819927070554974492595242276233838165366595623027934305811724028444934145 |
The RSA algorithm works by taking the message and raising it to the e power.
This gives us the secure encrypted message that can only be decrypted by those
who know d, whic can be found by solving d*e + phi*m = 1 = gcd(e,phi).
Encrypted message: 186703877856401638759986877690775226640561078094659057387825313002605353\ 483167229778667494388237522115346921195663031662548792788529347938855232\ 1889543554712669965154737924504783064902569916077055436 Encrypted message: 1867038778564016387599868776907752266405610780946590573878253130026053534831672297786674943882375221153469211956630316625487927885293479388552321889543554712669965154737924504783064902569916077055436 |
To decrypt the message, we take the d, found as explained above, and raise
the decrypted message to the d power. This gives us our original message, my CUID.
Decrypted message: 65099899 Decrypted message: 65099899 |
|