RSA
RSA
A simple Public Key Cryptosystem
Introduction
Introduction
Public-key cryptography, also known as asymmetric cryptography, uses two different but mathematically linked keys, one public and one private. The public key can be shared with everyone, whereas the private key must be kept secret. In RSA cryptography, both the public and the private keys can encrypt a message; the opposite key from the one used to encrypt a message is used to decrypt it. This attribute is one reason why RSA has become the most widely used asymmetric algorithm: It provides a method of assuring the confidentiality, integrity, authenticity and non-reputability of electronic communications and data storage.
Algorithm
Algorithm
The idea of the algorithm is to encrypt some message between two users. Fermat’s little theorem says that, given a prime and any integer , = ,then =. This generalizes for any integer n coprime to a and we get = = . Proof is omitted here for brevity. 1) First, each user chooses two big primes p and q. This is 1024 binary digit number
p
a
p-1
a
1(modp)
p
a
a(modp)
t
a
1(modn)
=>
t+1
a
a(modn)
In[8]:=
{p,q}=RandomPrime[{2^1023,2^1024},2]
Out[8]=
{124135304750935389101829569207491608858452497369218307570131916500178335285601195620380920185688812460995644721105165863780728156832666913830281793197764623494141542687180596940966781715471216807701536065293555099508547959504605780071665578297999070795076297478091197306199710127348111265364327347687298990243,105804299838591147786332038488124686327319285108316669056604508051021365218259116665144616414673756923507429454104785588699407778130806419551434649691320403442815939739790211646187440010157747464104670107424933595278303681760178662679621865788185713289449160636063768669455462324569119149032689573194781169461}
2) Then they compute the products and . and can be discarded now.
2) Then they compute the products
n=p*q
t=(p-1)(q-1)
p
q
In[9]:=
n = p * qt =(p-1)(q-1)
Out[9]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411311290510802202837296466691550619160746806673305079177739942029272523240337534784565490836329566295119900366295860590557192532195047169402521085939197195494237477216193962517077664997795911950463967491557359688377055085332257319762021641514503864302008426124034770298864472725512987989735531287294895968569023
Out[10]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411081350906212676300408305083855002865561034890827544201113205604721323539833674472279965299729203725735397292120650639104712396260083696069139369496308110467300519733766991708490510776070282986192161285384641199682268233690992535319270354070417679517923900665920615332888817553061070759321134270374013888409320
3) Choose 2 numbers and such that . Discard t after this. We should just be careful that e isn’t a divisor of and it should be between 1 and
3) Choose 2 numbers
e
d
e*d=
1(modt)
n
n
In[11]:=
e = RandomPrime[{1,n}]
Out[11]=
2854289466462136659611101336102597314970341397109371713251441294101027922685938235620400720747901232116856212433934953836178793004777035745706904831215564716398114761600760888500874381242845820744886585789624989716667318471908473714953184681021043419857008473166394591011087248841157437672011841586559918092418879572177786313394001449757995080249619695487070389753452139906564736769990999160575251859710039838585792859749964386403962776636315339390940114998035702774441288360574144000897729622532921022178014011162480447389473857249245443828748991024156413716913070553726594541175355722442941769391984479060376807391
In[12]:=
d = PowerMod[e, -1, t]
Out[12]=
216511704083026632201493887376314631392361542616986703624185291432796437266605579588780195420385126934849151161011787103418073798094948877679666594861666022850734919063117043075674735114021528720570399080785407491956456172651105008711989588372263760269028496316374009473119075007256385256343071055564860199219871466483900844019117717907995047383092142130828040699649079465418886975072315770963774585989561245712619990925484620266937828502411676147571287097172565839906506510978181576173595380012129275048206692185550686410897929140236007513079674017519368898791164548363342313677288206677786644571331320176712268551
4) Now, the couple (e, n) is called the public key(n is called the modulus and is called the exponent) and the private key is
5) The public key can be given to others but the private key () should not leave the computer.
6) For a secure enough implementation the modules n has at least 2048 bits. I used much smaller numbers here though
e
d
5) The public key can be given to others but the private key (
d
6) For a secure enough implementation the modules n has at least 2048 bits. I used much smaller numbers here though
Encryption
Encryption
Let’s say the message to be encrypted can be represented as an integer m which is smaller than n. If the integer representation is larger than n, then the message has to be broken down into multiple pieces. m should also be prime to n.
Now, to encrypt the message and get the ciphertext (another integer) we compute Let the secret message be “The magic words are Squeamish Ossifrage”. Let’s convert it into digits before encrypting it over.
Now, to encrypt the message
m
c
c=(modn).
e
m
In[13]:=
m=Total@MapIndexed[#1&,ToCharacterCode["The Magic Words are Squeamish Ossifrage"]]c=PowerMod[m,e,n]
First[#2-1]
256
Out[13]=
3305012019449526228978496962940312012718199938660609170647220059089162474114678523318979881044
Out[14]=
2926494418312680963702032656640996541406870165125921034982078449349963230216677281512432184507788353191108799408604369354719178653255114369040394004140497286043246642205182730253284240875534073136231682584551345634153416969769020496794820106287298359308958491923984924645399507938513750226792443268965476462260207656864698472764571918041047295550787771196201722114069911642240869792782784999492013847649614052213357047598751057874326399169747584401811398789526102503166866090167399524968701484301951024383779125541003181558031945427493799509734368748658466807831441213624181298123521679661139225042981460885537162835
Decryption
Decryption
Why is it secure ?
Why is it secure ?
As you see, the above functions takes really long(doesn’t finish) and this problem is computationally difficult.
Authorship information
Nikhil. R
20-6-2017
rnikhil275@gmail.com