310 lines
11 KiB
HTML
310 lines
11 KiB
HTML
|
|
||
|
|
<!-- saved from url=(0041)https://samsclass.info/141/proj/pRSA2.htm -->
|
||
|
|
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
|
||
|
|
<title>Proj RSA2: Cracking a Short RSA Key (15 pts.)</title>
|
||
|
|
</head>
|
||
|
|
<body bgcolor="#cccccc">
|
||
|
|
<h1>Proj RSA2: Cracking a Short RSA Key (15 pts.)</h1>
|
||
|
|
What you need:
|
||
|
|
<ul>
|
||
|
|
<li>A Mac or Linux computer with Python.
|
||
|
|
</li></ul>
|
||
|
|
<h2>Purpose</h2>
|
||
|
|
To break into RSA encryption without prior knowledge of the
|
||
|
|
private key. This is only possible for small RSA keys,
|
||
|
|
which is why RSA keys should be long for security.
|
||
|
|
<p>
|
||
|
|
</p><h2>Summary</h2>
|
||
|
|
Here's a diagram from the textbook showing the
|
||
|
|
RSA calculations.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA1-1.png"></blockquote>
|
||
|
|
<h2>Problem Statement</h2>
|
||
|
|
Meghan's public key is (10142789312725007, 5).
|
||
|
|
Find her private key.
|
||
|
|
<h2>1. Factoring n</h2>
|
||
|
|
<h3>Finding the Square Root of n</h3>
|
||
|
|
n = 10142789312725007. This is the product of
|
||
|
|
two prime numbers, p and q.
|
||
|
|
<p>
|
||
|
|
How large are p and q? Well, they can't both be
|
||
|
|
larger than the square root of n, or they'd be larger
|
||
|
|
than n when multiplied together.
|
||
|
|
</p><p>
|
||
|
|
Start Python in interactive mode. On a Mac
|
||
|
|
or Linux box, you can do that by
|
||
|
|
typing this command into a Terminal window:
|
||
|
|
</p><blockquote><b><big><code>
|
||
|
|
python
|
||
|
|
</code></big></b></blockquote>
|
||
|
|
Execute these commands:
|
||
|
|
<blockquote><b><big><code><pre>import math
|
||
|
|
n = 10142789312725007
|
||
|
|
print math.sqrt(n)
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
The square root prints out,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-1.png"></blockquote>
|
||
|
|
<h3>Displaying More Decimal Places</h3>
|
||
|
|
It's not clear from that output whether the result
|
||
|
|
is an integer, or just rounded off to one decimal
|
||
|
|
place. To see more decimal places, we'll use
|
||
|
|
the repr() function.
|
||
|
|
<p>
|
||
|
|
Execute this command:
|
||
|
|
</p><blockquote><b><big><code><pre>print repr(math.sqrt(n))
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Now more decimal places appear,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-2.png"></blockquote>
|
||
|
|
<h3>Testing 20 Candidates</h3>
|
||
|
|
So one of the prime factors must be a prime number
|
||
|
|
less than 100711415. All we have to do is try dividing
|
||
|
|
n by odd numbers starting at 100711413 and going down until
|
||
|
|
we get an integer result. (We don't need to test 100711415 because
|
||
|
|
it's divisible by 5 and therefore not a prime number.)
|
||
|
|
<p>
|
||
|
|
A good way to do this is to calculate n mod c, where c is a candidate. If c is a factor of n, the result will be zero.
|
||
|
|
</p><p>
|
||
|
|
We can test the first 20 candidates with a for loop.
|
||
|
|
</p><p>
|
||
|
|
Execute these commands:
|
||
|
|
</p><blockquote><b><big><code><pre>c = 100711413
|
||
|
|
for i in range(c, c-40, -2):
|
||
|
|
print i, n%i
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Press Enter twice after the last command to terminate the loop.
|
||
|
|
<p>
|
||
|
|
The third candidate is the winner, with a remainder of zero,
|
||
|
|
as shown below.
|
||
|
|
</p><blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-3.png"></blockquote>
|
||
|
|
<h3>Calculating q</h3>
|
||
|
|
We now know p and we can calculate q.
|
||
|
|
<p>
|
||
|
|
Execute these commands:
|
||
|
|
</p><blockquote><b><big><code><pre>p = 100711409
|
||
|
|
q = n / p
|
||
|
|
print p, q, n, p*q, n - p*q
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
The calculation worked, so the last value is zero,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-4.png"></blockquote>
|
||
|
|
<h2>2. Compute phin = (p-1) * (q-1)</h2>
|
||
|
|
Execute these commands:
|
||
|
|
<blockquote><b><big><code><pre>phin = (p-1) * (q-1)
|
||
|
|
print p, q, n, phin
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
The parameters print out, as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-6.png"></blockquote>
|
||
|
|
<h2>3. Compute Private Key d</h2>
|
||
|
|
We need to find a <b>d</b> with this
|
||
|
|
property:
|
||
|
|
<blockquote>
|
||
|
|
<b> (d * e) mod phin = 1 </b>
|
||
|
|
</blockquote>
|
||
|
|
We know that e = 5 from the Problem Statement.
|
||
|
|
<p>
|
||
|
|
It's not obvious how to find d, but
|
||
|
|
<a href="https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python">there's
|
||
|
|
a simple way to do it in Python</a>, using the
|
||
|
|
"gmpy> library.
|
||
|
|
</p><p>
|
||
|
|
Open a <b>new Terminal window</b>, not the one
|
||
|
|
running Python, and execute this command to
|
||
|
|
download and install a few dependencies and gmpy:
|
||
|
|
</p><blockquote><b><big><code><pre>brew install gmp mpfr mpc
|
||
|
|
pip install gmpy
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
<p>
|
||
|
|
In the Terminal window running python,
|
||
|
|
execute these commands.
|
||
|
|
</p><blockquote><b><big><code><pre>e = 5
|
||
|
|
import gmpy
|
||
|
|
d = gmpy.invert(e, phin)
|
||
|
|
print d, e, d*e %phin
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
We get the value of d, and, to verify it,
|
||
|
|
we see that d*e %phin is indeed 1,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-7.png"></blockquote>
|
||
|
|
<h2>4. Encrypting a Message</h2>
|
||
|
|
<h3>Encoding the Message as a Number</h3>
|
||
|
|
Cueball wants to send Meghan this message:
|
||
|
|
<blockquote><b><big><code><pre>Hi!
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
We can only send numbers.
|
||
|
|
Let's convert that message to three bytes of ASCII
|
||
|
|
and then interpret it as a 24-bit binary value.
|
||
|
|
<p>
|
||
|
|
In the Terminal window running python,
|
||
|
|
execute these commands.
|
||
|
|
</p><blockquote><b><big><code><pre>x1 = ord('H')
|
||
|
|
x2 = ord('i')
|
||
|
|
x3 = ord('!')
|
||
|
|
x = x1*256*256 + x2*256 + x3
|
||
|
|
print x
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
We get the value of x,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-8.png"></blockquote>
|
||
|
|
<h3>Encrypting the Message with the Public Key</h3>
|
||
|
|
A public key contains two numbers: <b>n</b>
|
||
|
|
and <b>e</b>. To encrypt a message <i>x</i>,
|
||
|
|
use this formula:
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA1-11.png"></blockquote>
|
||
|
|
<p>
|
||
|
|
Execute these commands:
|
||
|
|
</p><blockquote><b><big><code><pre>y = x ** e % n
|
||
|
|
print y
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
The encrypted message appears,
|
||
|
|
as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-9.png"></blockquote>
|
||
|
|
<h2>5. Decrypting a Message</h2>
|
||
|
|
To decrypt a message, use this formula:
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA1-13.png"></blockquote>
|
||
|
|
Execute these commands:
|
||
|
|
<blockquote><b><big><code><pre>xx = y ** d % n
|
||
|
|
print xx
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Python crashes,
|
||
|
|
as shown below. It cannot handle such large numbers.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-10.png"></blockquote>
|
||
|
|
To compute such a number, we must use the pow() function.
|
||
|
|
<p>
|
||
|
|
Execute these commands to restart python and restore
|
||
|
|
all the values we calculated previously:
|
||
|
|
</p><blockquote><b><big><code><pre>python
|
||
|
|
n = 10142789312725007
|
||
|
|
p = 100711409
|
||
|
|
q = 100711423
|
||
|
|
phin = (p-1) * (q-1)
|
||
|
|
e = 5
|
||
|
|
import gmpy
|
||
|
|
d = gmpy.invert(e, phin)
|
||
|
|
x1 = ord('H')
|
||
|
|
x2 = ord('i')
|
||
|
|
x3 = ord('!')
|
||
|
|
x = x1*256*256 + x2*256 + x3
|
||
|
|
y = x ** e % n
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Your screen should look like the image
|
||
|
|
below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-11.png"></blockquote>
|
||
|
|
Let's try that decryption again with the pow()
|
||
|
|
function. Execute these commands:
|
||
|
|
<blockquote><b><big><code><pre>xx = pow(y, d, n)
|
||
|
|
print xx
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Now it works, showing our original message in
|
||
|
|
numerical form.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-12.png"></blockquote>
|
||
|
|
<h3>Converting the Message to Readable Text</h3>
|
||
|
|
To convert that number back to letters,
|
||
|
|
execute these commands:
|
||
|
|
<blockquote><b><big><code><pre>xx1 = xx / (256*256)
|
||
|
|
xx2 = (xx - 256*256*xx1) / 256
|
||
|
|
xx3 = xx - 256*256*xx1 - 256*xx2
|
||
|
|
msg = chr(xx1) + chr(xx2) + chr(xx3)
|
||
|
|
print xx1, xx2, xx3, msg
|
||
|
|
</pre></code></big></b></blockquote>
|
||
|
|
Now it works, showing the original message in
|
||
|
|
readable form, as shown below.
|
||
|
|
<blockquote><img src="./Proj RSA2_ Cracking a Short RSA Key (15 pts.)_files/pRSA2-13.png"></blockquote>
|
||
|
|
<hr>
|
||
|
|
<h2>Challenge 2a: Encrypt "OBEY!"</h2>
|
||
|
|
Using the same system and keys, encrypt this message:
|
||
|
|
<blockquote><b><big><pre>OBEY!
|
||
|
|
</pre></big></b></blockquote>
|
||
|
|
<i>Hint 1: The message, converted to a number, is 12 digits long and ends in 41.</i>
|
||
|
|
<p>
|
||
|
|
<i>Hint 2: The encrypted message is 16 digits long and ends in 81.</i>
|
||
|
|
</p><p>
|
||
|
|
Use the form
|
||
|
|
below to put your name on the
|
||
|
|
<a href="http://ad.samsclass.info/python/RSAchal2a-winners.htm">
|
||
|
|
<b>WINNERS PAGE</b></a>.
|
||
|
|
</p><blockquote>
|
||
|
|
<form action="http://ad.samsclass.info/python/RSAchal2a.php" method="post">
|
||
|
|
<table cellpadding="5" border="10"><tbody><tr><td>
|
||
|
|
<table cellpadding="5">
|
||
|
|
<tbody><tr><td><big><b>Your Name (without spaces):</b></big></td>
|
||
|
|
<td><textarea name="u" rows="1" cols="25"></textarea></td></tr>
|
||
|
|
<tr><td><big><b>Encrypted message:</b></big></td>
|
||
|
|
<td><textarea name="p" rows="1" cols="30"></textarea></td></tr>
|
||
|
|
<tr><td colspan="2" align="center"><big><b>
|
||
|
|
<input type="submit" value="SUBMIT"></b></big></td></tr>
|
||
|
|
</tbody></table>
|
||
|
|
</td></tr></tbody></table>
|
||
|
|
</form>
|
||
|
|
</blockquote>
|
||
|
|
<hr>
|
||
|
|
<h2>Challenge 2b: Message to Cueball</h2>
|
||
|
|
Cueball's public key is:
|
||
|
|
<blockquote><b><big><pre>(111036975342601848755221, 13)
|
||
|
|
</pre></big></b></blockquote>
|
||
|
|
Meghan sends this message to Cueball. Decrypt it.
|
||
|
|
<blockquote><b><big><pre>80564890594461648564443
|
||
|
|
</pre></big></b></blockquote>
|
||
|
|
Use the form
|
||
|
|
below to put your name on the
|
||
|
|
<a href="http://ad.samsclass.info/python/RSAchal2b-winners.htm">
|
||
|
|
<b>WINNERS PAGE</b></a>.
|
||
|
|
<blockquote>
|
||
|
|
<form action="http://ad.samsclass.info/python/RSAchal2b.php" method="post">
|
||
|
|
<table cellpadding="5" border="10"><tbody><tr><td>
|
||
|
|
<table cellpadding="5">
|
||
|
|
<tbody><tr><td><big><b>Your Name (without spaces):</b></big></td>
|
||
|
|
<td><textarea name="u" rows="1" cols="25"></textarea></td></tr>
|
||
|
|
<tr><td><big><b>Cleartext Message:</b></big></td>
|
||
|
|
<td><textarea name="p" rows="1" cols="25"></textarea></td></tr>
|
||
|
|
<tr><td colspan="2" align="center"><big><b>
|
||
|
|
<input type="submit" value="SUBMIT"></b></big></td></tr>
|
||
|
|
</tbody></table>
|
||
|
|
</td></tr></tbody></table>
|
||
|
|
</form>
|
||
|
|
</blockquote>
|
||
|
|
<hr>
|
||
|
|
<h2>Challenge 3: Message to Rob</h2>
|
||
|
|
Rob public key is:
|
||
|
|
<blockquote><b><big><pre>(1234592592962967901296297037045679133590224789902207663928489902170626521926687, 5557)
|
||
|
|
</pre></big></b></blockquote>
|
||
|
|
Meghan sends this message to Rob. Decrypt it.
|
||
|
|
<blockquote><b><big><pre>272495530567010327943798078794037733865151017104532777645776936985235709526002
|
||
|
|
</pre></big></b></blockquote>
|
||
|
|
<i>Hint:
|
||
|
|
<a href="https://stackoverflow.com/questions/10725522/arbitrary-precision-of-square-roots">make square root calculations more precise</a>.</i>
|
||
|
|
<p>
|
||
|
|
Use the form
|
||
|
|
below to put your name on the
|
||
|
|
<a href="http://ad.samsclass.info/python/RSAchal2c-winners.htm">
|
||
|
|
<b>WINNERS PAGE</b></a>.
|
||
|
|
</p><blockquote>
|
||
|
|
<form action="http://ad.samsclass.info/python/RSAchal2c.php" method="post">
|
||
|
|
<table cellpadding="5" border="10"><tbody><tr><td>
|
||
|
|
<table cellpadding="5">
|
||
|
|
<tbody><tr><td><big><b>Your Name (without spaces):</b></big></td>
|
||
|
|
<td><textarea name="u" rows="1" cols="25"></textarea></td></tr>
|
||
|
|
<tr><td><big><b>Cleartext Message:</b></big></td>
|
||
|
|
<td><textarea name="p" rows="1" cols="25"></textarea></td></tr>
|
||
|
|
<tr><td colspan="2" align="center"><big><b>
|
||
|
|
<input type="submit" value="SUBMIT"></b></big></td></tr>
|
||
|
|
</tbody></table>
|
||
|
|
</td></tr></tbody></table>
|
||
|
|
</form>
|
||
|
|
</blockquote>
|
||
|
|
<hr>
|
||
|
|
<h2>Sources</h2>
|
||
|
|
<a href="https://stackoverflow.com/questions/4078902/cracking-short-rsa-keys">
|
||
|
|
Cracking short RSA keys</a>
|
||
|
|
<p>
|
||
|
|
<a href="http://www.numberempire.com/primenumbers.php">
|
||
|
|
Prime Numbers Generator and Checker</a>
|
||
|
|
</p><p>
|
||
|
|
<a href="https://stackoverflow.com/questions/10725522/arbitrary-precision-of-square-roots">Arbitrary precision of square roots</a>
|
||
|
|
</p><hr>
|
||
|
|
Posted 3-31-16 by Sam Bowne <br>
|
||
|
|
Winners pages added 8-6-16 <br>
|
||
|
|
Attack server name updated 4-4-17 <br>
|
||
|
|
|
||
|
|
|
||
|
|
</body></html>
|