RSA

A simple public-key cryptosystem.
June 20, 2017—Nikhil Ramesh

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)
. The proof is omitted here for brevity.
First, each user chooses two big primes,
p
and
q
. This is a binary number with 1024 digits:
In[]:=
{p,q}=RandomPrime[{2^1023,2^1024},2]
Out[]=
{124135304750935389101829569207491608858452497369218307570131916500178335285601195620380920185688812460995644721105165863780728156832666913830281793197764623494141542687180596940966781715471216807701536065293555099508547959504605780071665578297999070795076297478091197306199710127348111265364327347687298990243,105804299838591147786332038488124686327319285108316669056604508051021365218259116665144616414673756923507429454104785588699407778130806419551434649691320403442815939739790211646187440010157747464104670107424933595278303681760178662679621865788185713289449160636063768669455462324569119149032689573194781169461}
Then compute the products
n=p*q
and
t=(p-1)(q-1)
.
p
and
q
can be discarded now:
In[]:=
n=p*q​​t=(p-1)(q-1)
Out[]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411311290510802202837296466691550619160746806673305079177739942029272523240337534784565490836329566295119900366295860590557192532195047169402521085939197195494237477216193962517077664997795911950463967491557359688377055085332257319762021641514503864302008426124034770298864472725512987989735531287294895968569023
Out[]=
13134049004422856130104341690412807076338184877421027145734840629431186679254739234308828426871131942750284851991414362738984651607162519797913813747974559250462409316025487425060309101936147847997515147613157820810608794204378532523814503122935242339517336863794328758741927461165655862921824556045252958411081350906212676300408305083855002865561034890827544201113205604721323539833674472279965299729203725735397292120650639104712396260083696069139369496308110467300519733766991708490510776070282986192161285384641199682268233690992535319270354070417679517923900665920615332888817553061070759321134270374013888409320
Choose two numbers
e
and
d
such that
e*d=
1(modt)
. Discard
t
after this. We should be careful that
e
isn’t a divisor of
n
, and it should be between 1 and
n
:
In[]:=
e=RandomPrime[{1,n}]
Out[]=
2854289466462136659611101336102597314970341397109371713251441294101027922685938235620400720747901232116856212433934953836178793004777035745706904831215564716398114761600760888500874381242845820744886585789624989716667318471908473714953184681021043419857008473166394591011087248841157437672011841586559918092418879572177786313394001449757995080249619695487070389753452139906564736769990999160575251859710039838585792859749964386403962776636315339390940114998035702774441288360574144000897729622532921022178014011162480447389473857249245443828748991024156413716913070553726594541175355722442941769391984479060376807391
In[]:=
d=PowerMod[e,-1,t]
Out[]=
216511704083026632201493887376314631392361542616986703624185291432796437266605579588780195420385126934849151161011787103418073798094948877679666594861666022850734919063117043075674735114021528720570399080785407491956456172651105008711989588372263760269028496316374009473119075007256385256343071055564860199219871466483900844019117717907995047383092142130828040699649079465418886975072315770963774585989561245712619990925484620266937828502411676147571287097172565839906506510978181576173595380012129275048206692185550686410897929140236007513079674017519368898791164548363342313677288206677786644571331320176712268551
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
.
The public key can be given to others, but the private key (
d
) should not leave the computer.
For a secure implementation, the module n should have at least 2048 bits. I used much smaller numbers here, though.

Encryption

Decryption

Why Is It Secure?

AUTHORSHIP INFORMATION
Nikhil Ramesh
6/20/17