Insert
Sample

RSA

A simple Public Key Cryptosystem

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

The idea of the algorithm is to encrypt some message between two users. Fermat’s little theorem says that, given a prime
p
and any integer
a
,
p-1
a
=
1(modp)
,then
p
a
=
a(modp)
. This generalizes for any integer n coprime to a and we get
t
a
=
1(modn)
=>
t+1
a
=
a(modn)
. Proof is omitted here for brevity. ​1) First, each user chooses two big primes p and q
​​
. This is 1024 binary digit number
In[8]:=
{p,q}=RandomPrime[{2^1023,2^1024},2]
Out[8]=
{124135304750935389101829569207491608858452497369218307570131916500178335285601195620380920185688812460995644721105165863780728156832666913830281793197764623494141542687180596940966781715471216807701536065293555099508547959504605780071665578297999070795076297478091197306199710127348111265364327347687298990243,105804299838591147786332038488124686327319285108316669056604508051021365218259116665144616414673756923507429454104785588699407778130806419551434649691320403442815939739790211646187440010157747464104670107424933595278303681760178662679621865788185713289449160636063768669455462324569119149032689573194781169461}
​
2) Then they compute the products
n=p*q
and
t=(p-1)(q-1)
.
p
and
q
can be discarded now.
In[9]:=
n = p * q​​t =(p-1)(q-1)
Out[9]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411311290510802202837296466691550619160746806673305079177739942029272523240337534784565490836329566295119900366295860590557192532195047169402521085939197195494237477216193962517077664997795911950463967491557359688377055085332257319762021641514503864302008426124034770298864472725512987989735531287294895968569023
Out[10]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411081350906212676300408305083855002865561034890827544201113205604721323539833674472279965299729203725735397292120650639104712396260083696069139369496308110467300519733766991708490510776070282986192161285384641199682268233690992535319270354070417679517923900665920615332888817553061070759321134270374013888409320
​
3) Choose 2 numbers
e
and
d
such that
e*d=
1(modt)
. Discard t after this. We should just be careful that e isn’t a divisor of
n
and it should be between 1 and
n
In[11]:=
e = RandomPrime[{1,n}]
Out[11]=
2854289466462136659611101336102597314970341397109371713251441294101027922685938235620400720747901232116856212433934953836178793004777035745706904831215564716398114761600760888500874381242845820744886585789624989716667318471908473714953184681021043419857008473166394591011087248841157437672011841586559918092418879572177786313394001449757995080249619695487070389753452139906564736769990999160575251859710039838585792859749964386403962776636315339390940114998035702774441288360574144000897729622532921022178014011162480447389473857249245443828748991024156413716913070553726594541175355722442941769391984479060376807391
In[12]:=
d = PowerMod[e, -1, t]
Out[12]=
216511704083026632201493887376314631392361542616986703624185291432796437266605579588780195420385126934849151161011787103418073798094948877679666594861666022850734919063117043075674735114021528720570399080785407491956456172651105008711989588372263760269028496316374009473119075007256385256343071055564860199219871466483900844019117717907995047383092142130828040699649079465418886975072315770963774585989561245712619990925484620266937828502411676147571287097172565839906506510978181576173595380012129275048206692185550686410897929140236007513079674017519368898791164548363342313677288206677786644571331320176712268551

Encryption

Decryption

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