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
4) Now, the couple (e, n) is called the public key(n is called the modulus and
e
is called the exponent) and the private key is
d
​
5) The public key can be given to others but the private key (
d
) 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

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
m
and get the ciphertext
c
(another integer) we compute
c=
e
m
(modn).
Let the secret message be “The magic words are Squeamish Ossifrage”. Let’s convert it into digits before encrypting it over.
In[13]:=
m=Total@MapIndexed[#1
First[#2-1]
256
&,ToCharacterCode["The Magic Words are Squeamish Ossifrage"]]​​c=PowerMod[m,e,n]
Out[13]=
3305012019449526228978496962940312012718199938660609170647220059089162474114678523318979881044
Out[14]=
2926494418312680963702032656640996541406870165125921034982078449349963230216677281512432184507788353191108799408604369354719178653255114369040394004140497286043246642205182730253284240875534073136231682584551345634153416969769020496794820106287298359308958491923984924645399507938513750226792443268965476462260207656864698472764571918041047295550787771196201722114069911642240869792782784999492013847649614052213357047598751057874326399169747584401811398789526102503166866090167399524968701484301951024383779125541003181558031945427493799509734368748658466807831441213624181298123521679661139225042981460885537162835

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