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
Encryption
Encryption
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