CoCalc Shared Files4 - RSA (prof) / RSA (prof).sagews
Author: Gabriel Chênevert
Views : 239

Names of the collaborators:

## A) Using RSA

Check that you understand the arithmetic involved in the operation of the RSA cipher by encrypting a message of your choice with the following provided modulus and public encryption key:
load("n.sage"); n

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385569013893523061019203192770785237017515647172883614754263716486922656987253749712654919879651334951554259413440244766917064201270581678800997529724440775507818202313762025577352116338637253407982766386276026928209370641476042078273584380760128086173472341435934794839743511496914486637820060419211972356216187593
load("e.sage"); e

12247839702908519607469964861720233546811094976365755308787413004974779065412005434944511838560671317431616261860844161254163763575502215311000899990215530620570199960433473146880722860527497526392309152532514337375640213657360164179263743192204612223789850805682217085364986984918738763501006465596792521957884600379921032803410969845835123517826326472508737599966797634672728867076092733629591440672247670025307411784004340405102400471980805439254314145385537917544330411527323542521948105413271302359919582174314276958517848380894749379904748040080711973514294747678180947334564474006562613931545049201229681216009

The RSA modulus $\color{blue}$ is a 2048-bit integer:

N(log(n,2))

2048.00000000000

we can thus use it to encrypt any byte-string of length no bigger than $\color{blue} 2048 / 8 = 256$.

I would like you to write your own modular exponentiation function to really appreciate how fast this operation is once it is performed properly. You can check it against Sage's built-in modular capabilities: Zmod(n) is used to denote the ring of integers modulo $n$.

For example, here is the encryption of the string "Test vector", viewed as an integer written in base 256:

m = Zmod(n)(ZZ("Test vector".encode("hex"),16))
m^e

12509234860927539010216080355524065312008632102566446764901511522517021417541512139309081015464848859924173256558765485886101708617072487802611277194093804229645086130329181795437975950311971365513581481081946089891011600457080774855616434241505671409252759644518550583981299439904701564189430458555306811270164943611726695600017591857519226915203318269595276137254439101525977731780469730213609499179559503203828786739093536394156387720950567522589720085788581287431457643825424412831169631303984697158397814444925288510194810954362061066805990433605544675199716970718881565124810997062486177554145467126331604155339

Here's another way to write the fast exponentiation function: (scanning the binary expansion of the exponent from right to left and using a temporary variable that is repeatedly squared)

def fast_exp(a, b, n):

"Computes a^b mod n, assuming a, b, n are positive integers."

A = a
r = 1

while b > 0:

if b % 2 == 1:
r = r * A % n

b = b // 2
A = A * A % n

return r


Some unit tests:

%time

nb_tests = 40
max_size = 2^2048
nb_fails = 0

for i in range(nb_tests):

m = ZZ.random_element(max_size)
a = ZZ.random_element(max_size)
b = ZZ.random_element(max_size)

if not fast_exp(a, b, m) == power_mod(a, b, m):
nb_fails += 1

print "%s tests, %s failures" % (nb_tests, nb_fails)

40 tests, 0 failures CPU time: 1.16 s, Wall time: 1.17 s

Using public-key encryption with (plain-)RSA is only a matter of computing a modular power:

m = "Test vector"

m = ZZ(m.encode("hex"), 16)            # convert to integer

test_c = fast_exp(m, e, n); test_c     # ok

16880227852884600096850858248945879613556191521324636512525639711126011145935682640127410891364642868217601270699975606501823710551100886509009082810965964282214263711280194366484307372419731552709504400427705638318622504848361045105215366952294904284017579028271106024456878001693752206770610090134134214873549980877903100463805416658594467118269338068989104004456057089677735110030369353151961375485724471670285049683646442872782027835587703553102828259290187341285618055817419696525935701197834914008477201541014119054270147867703156492847399594407985738013595279964726862035781277302135078778024959256585501797956

## B) Exploiting RSA malleability

One of the weaknesses of unpadded RSA is the fact that an attacker can easily manipulate a ciphertext to produce a predictable effect on the plaintext. Demonstrate this by performing the following: in the file c.sage you will find the encrypted version of some secret integer $m$; produce the ciphertext that corresponds to the integer $2m$. (Since you have the encryption key, you can easily produce the ciphertexts corresponding to any plaintext of your liking.)

load("c.sage"); c

1710281096819399623283365973631330946906395899975640757517345774046368047252096515544297833350820327836032803018256137716484284856792289761920012418624803598590975162155273176772452084379527251661758665289082752742312483636396162384142025981752427958534283353000591873645855598235750000093228619471164661154330901192395374771307553043364550921873118951544728367487811943240551019633356222173617274616504392790465390048152244580771933677697893861747464252521083768703810096874740178355971338602958584442258534454724185510473270559459555636560258228220456199429386831132755379527280344364296751808098443948339016282898

We know that this ciphertext satisfies $\color{blue} c \equiv m^e \ \mathrm{mod} \, n, \qquad m \equiv c^d \ \mathrm{mod} \, n.$ We would like to find some other ciphertext $\color{blue} c'$ that decrypts to $\color{blue} 2m$: $\color{blue} (c')^d \equiv 2m \ \mathrm{mod} \, n,$ or, taking $\color{blue} e^\text{th}$ powers on both sides, $\color{blue} c' \equiv (2m)^e \equiv 2^e c \ \mathrm{mod} \, n.$ Easy enough!

cc = fast_exp(2, e, n) * c % n
cc

9300590725838577187624069244301290313701643241900005723645675274963395130716097540527443004808827503609508695826264939097333664529522548591878023493105501803936394683516100695950316029851633264725959939171828870905987973678774769631693705886078035841863935263370252522267204641227597224054432456289817988641854368042970873917942826118360617473851428807588742670740043825864406405585528985061809726642254018060229077730373104230308970423053327529468639984291543816498262671322246780839211971078931734547270839365409700431844835760564728724946576141854861342853866416422260645602372689282974293483034425047902752304016

## C) Breaking RSA

Generating RSA parameters is a bit more tricky than it might seem because special care should be exercised so that the modulus $n$ doesn't end up "by chance" easily factored by a special-purpose factorization algorithm.

For the provided modulus $n$, you can try to ask Sage for its factorization: (but don't hold your breath... and be kind enough to stop the process at some point)

factor(n)

Error in lines 1-1 Traceback (most recent call last): File "/projects/c4a32d58-ff58-4533-b6dc-9042362fb3fa/.sagemathcloud/sage_server.py", line 865, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/usr/local/sage/sage-6.3.beta6/local/lib/python2.7/site-packages/sage/rings/arith.py", line 2467, in factor int_ = int_, verbose=verbose) File "integer.pyx", line 3581, in sage.rings.integer.Integer.factor (build/cythonized/sage/rings/integer.c:22697) File "factorint.pyx", line 301, in sage.rings.factorint.factor_using_pari (build/cythonized/sage/rings/factorint.c:7208) File "factorint.pyx", line 342, in sage.rings.factorint.factor_using_pari (build/cythonized/sage/rings/factorint.c:6875) File "gen.pyx", line 8741, in sage.libs.pari.gen.gen.factor (build/cythonized/sage/libs/pari/gen.c:46926) File "c_lib.pyx", line 73, in sage.ext.c_lib.sig_raise_exception (build/cythonized/sage/ext/c_lib.c:872) KeyboardInterrupt

However, I was careless during the prime generation step and ended up with two primes tthat stand uncomfortably close to each other (say, with $|p-q| < 2^{30}$). Use this knowledge to find the factorization of $n$ in a matter of seconds and recover the secret decryption exponent $d$. Verify your findings by decrypting the ciphertext provided in the file c.sage.

If $\color{blue} n = pq$ with $\color{blue} p$ and $\color{blue} q$ "close", then both $\color{blue} p$ and $\color{blue} q$ need to be close to $\color{blue} \sqrt{n}$. An exhaustive search for a divisor of $\color{blue}$ starting at that number is then guaranteed to end quickly:

i = 0

p = floor(sqrt(n))

while n % p != 0:

p -= 1
i += 1

print "Divisor found after %s trials" % i
p

Divisor found after 500103 trials 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624223637243

Just for fun, let's check that this indeed gives us the ability to decrypt messages encrypted with the RSA modulus $\color{blue} n$.

q = n // p
n == p*q and is_prime(p) and is_prime(q)

True
import base64

phi_n = (p-1)*(q-1)
d = inverse_mod(e, phi_n)
test_m = fast_exp(test_c, d, n)
base64.b16decode(hex(test_m).upper())         # Pwned!

'Test vector'



## D) Parameter generation

Help me by generating a set of valid parameters $(n,e,d)$ for a 2048-bit RSA cryptosystem. You can use Sage's built-in is_prime() function to quickly test an integer for primality.
# or: use the built-in random_prime()

def random_prime_of_size(L):

found = false

while not found:                                        # expect roughly L iterations

p = ZZ.random_element(2^(L-1), 2^L)
if is_prime(p):
found = true

return p

%time

p = random_prime_of_size(1024)

q = random_prime_of_size(1024)

n = p * q

phi = (p-1) * (q-1)

e = ZZ.random_element(phi)

while gcd(e,phi) != 1:
e = ZZ.random_element(phi)

d = inverse_mod(e, phi)

print "n = %s" % n
print "e = %s" % e
print "d = %s" % d

n = 25347075022050602090763381678762301744285190004722713883530303141588928196349724122641457297087518028452188300344399187514363669540638034037614565285291298943159594464991574600291474469919997902107298057703541700769133090235094112525814285075731568535554152591266552709825390252010477426202113530934192662595184232139655176614683067890682243493144042112938223349941657150554473927689742687931563729550224862605181150431777287932542479448462278924129234999178098171070532668055062080070687822253916835724851114490525108410760454512634635444605628706010311159635745110277071775731033004565571623647269897555519616286729 e = 12786315471628131646368155466721363560044030422328160213419765263236872080910791463181800621164636495884411787603484664824661385836276446109199868874705892875696258613069379612882526709636703607493549700645785124767863354502456772749075596824866462368227739127199990675387245082187515495087475002083722380971648731287856807338842196625076421024368614716182677554456808941375031329367420653135985647468616906681734245877583256337363560302094663975077925336088995165881432265696257893688907179251462166763409937938765148534700073814466517338920556381704345746336149738211007050635566877365734875004976370008786814882829 d = 11277725854375425245009274877112563244994982920719593610730849753314308505946761756733370282928969191840944262907275227892034782956829382300128861669151936936081627470658904776511866502461596386685342249296006910152295140782645207178426113703340391292233667042552777039294035985018865028886072395083126555747238184344781454517285507258329181509856057178190065334371386980755025418999283077984856575926052883266505793677379435896570199062772801786982616516605896093887679848391639714075052512458032972969852869267132369512305712381690634130002474022007030920248924886703191403597870014420312581259871221334718629259829 CPU time: 10.18 s, Wall time: 10.32 s

Verification:

m = ZZ("It works!".encode("hex"), 16)

c  = fast_exp(m, e, n)
mm = fast_exp(c, d, n)

print "encrypted message: %s" % hex(c)
print "decrypted message: %s" % base64.b16decode(hex(mm).upper())

encrypted message: 7d8428df8f6d4549df3925635741f798f986073b37dc7f6010ac649113256926e4b2ab1fc0de37efc5a4d2b587b7c57045e9c0c2801a6af515ca4b0a38f2f0e0fe55dd280572a9849fcdd1bc39d80a205d66ae4065ef8463a391c05e69f062765aac5074ae3a06de8c2dec6e0c21dbb1de80eef17109b3b7118de41d3b5b7cb15a84922763a02b032a802499fa92a54af7bd8e1f69e6bb66f0797e97a98228f3c51751066cbd04c0a15caa4fd811ee2ff89b20b61d6ae805d4517395ad716946c980cb0356b7a638a5c5b16bc37d7188e846c7bb103ffb85450eec240f326b062e226f13c79fb6b1de81d7c9a9abd5e7fe303d131ffcb6977a187f859f5879d5 decrypted message: It works!