<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>
</head>

<body>
<h1 align="center"><img src="publickey.jpg" alt="Public Key Crypto" width="178" height="241" align="right" class="floatRight" /></h1>
<h1 align="center">RSA Encryption</h1>
<p>Encryption has been used to  exchange information between two parties and keep that information from a third  party. The problem with classical symmetric encryption is that the key used to  encrypt the information must be distributed to the people who are supposed to  be able to read the message before they can decrypt it. When a lot of messages  are to be exchanged, lots of keys must be distributed which can be a logistical  problem. Computers can efficiently encrypt and decrypt messages with symmetric  ciphers. </p>
<p>In 1976, Whitfield Diffie  along with Martin Hellman discovered public key cryptography and purposed the  Diffie-Hellman key exchange which is still a commonly used key exchange.</p>
<p>In 1977, Ron Rivest, Adi  Shamir, and Leonard Aldeman at MIT publicized the algorithm named from the  initials of the three inventors. The algorithm is based on the fact that it is  easy to multiply two large prime numbers together to get a product but it is  very difficult to reverse the process. Given the product, it is difficult to  calculate what two prime numbers were multiplied together initially.</p>
<p>In 1991, Senate Bill 266 was  introduced by the US  government. This anti-crime bill had a measure in it requiring all encryption  software must have a back door in it to allow the government to obtain the  plaintext of voice, data and other communications when authorized by law. This  bill prompted Phil Zimmerman to develop Pretty Good Privacy (PGP). In the  pgpguide.1st in PGP 1.0 was the following:</p>
<p><em>The 17 Apr 1991 New York Times reports on an unsettling US Senate  proposal that is part of a counterterrorism bill. If this nonbinding resolution  became real law, it would force manufacturers of secure communications  equipment to insert special &quot;trap doors&quot; in their products, so that  the Government can read anyone's encrypted messages. It reads: &quot;It is the  sense of Congress that providers of electronic communications services and  manufacturers of electronic communications service equipment shall insure that  communications systems permit the Government to obtain the plain text contents  of voice, data, and other communications when appropriately authorized by  law.&quot;</em></p>
<p>The problem with public key  encryption systems with includes RSA is that they are computationally intense  and run slowly as compared to symmetric key ciphers when dealing with large pieces  of data. PGP utilized the RSA public key/private key system to exchange the  symmetric key securely. The gist of a public key/private key system is that the  key you want to exchange is encrypted with the recipient&rsquo;s public key and the  only way to decrypt the key is to have the corresponding private key. Knowing  the public key does not help someone in trying to decrypt the message. PGP uses  the RSA public key system to encrypt the session key that the rest of the  message is encrypted in. RSA can run fairly quickly with the small amount of  data that makes up the session key. So the message is encrypted with the IDEA  cipher using a randomly generated key. The key is encrypted with the public key  of the recipient using RSA. The recipient receives the message and uses his  private RSA key to decrypt what the IDEA key was and that is used to decrypt  the message itself.</p>
<p><em>I was involved in the porting of PGP to A/UX  (Apple&rsquo;s Unix) and so I thought a puzzle based on a simplified RSA would be  interesting for my contribution to the TOM Creative Group puzzle.</em></p>
<h2 align="center"><em>The RSA  algorithm  detail</em><em>s</em></h2>
<p><em>RSA involves a public key and a private key. The  public key can be known by everyone and be used to encrypt messages being sent  to the recipient who uses the private key to decrypt the message. The keys for  the RSA algorithm are generated the following way:</em></p>
<ol>
  <li><em>Choose  two large prime numbers <strong>p</strong> and <strong>q</strong></em></li>
  <li><em>Compute <strong>n=pq</strong></em><strong><em></em></strong></li>
  <li><em>Compute the totient  <strong>phi = (p-1)(q-1) </strong></em></li>
  <li><em>Choose an integer e such that <strong>1 &lt; e &lt; phi(n)</strong> &nbsp;and <strong>e</strong> and <strong>phi(n)</strong>&nbsp;are coprime (share no  common factors other than 1) and frequently is chosen as <strong>3</strong> or <strong>17</strong> or <strong>2<sup>16</sup> + 1 = 65537 </strong></em>.</li>
  <li><em>Compute <strong>d</strong> such that<strong> 1 &lt; d &lt; phi(n) </strong>&nbsp;and<strong> ed </strong>is congruent to <strong> 1 phi(n) </strong>&nbsp;(</em>To compute the value for d, use the Extended  Euclidean Algorithm this is known as modular inversion.) </li>
  <li>The public key is  <strong>(<em>n,e</em>)</strong> and the private key is <strong>(<em>n,d</em>)</strong> the values of <em><strong>p</strong></em><strong>, <em>q</em></strong> and <strong>phi</strong>&nbsp;should be kept secret  also.</li>
</ol>
<p>	&#8729; <em><strong>n</strong></em> is known as the modulus<br />
  &#8729; <em><strong>e</strong></em> is known as the public exponent or  encryption exponent<br />
&#8729; <em><strong>d</strong></em> is known as the private exponent or  decryption exponent</p>
<p>&nbsp;</p>
<h3 align="center">A very simple example of RSA encryption</h3>
<p align="center">This example can be done using a calculator or by  hand.</p>
<ol>
  <li>Choose p=3 and  q=11</li>
  <li>n=pq  =3*11=33&nbsp; and phi(n) = (p-1)(q-1)=(2)(10)=20</li>
  <li>choose e=3 which  is &gt;1 and coprime to phi(n)=20</li>
  <li>compute d such  that ed &#8801; 1 mod(&#966;(n))&nbsp;<br />
  or&nbsp;d = e<sup>-1</sup> mod phi(n)<br />
  or find d such that  &#966;(n) divides (ed &ndash; 1)&nbsp;<br />
  or find d such that 20 divides 3d &ndash; 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li>
  <li> by brute force d=7 or 3*7-1/20 = 21-1/20 = 20/20=1<br />
  the public key is  (33,3) and the private key is (33,7)</li>
</ol>
<p>&nbsp;</p>
<p>If we want to encrypt the  message m=7<br />
  <strong>c = m<sup>e</sup> mod n = 7<sup>3</sup> mod 33 = 343 mod 33 = 13 </strong></p>
<p>If we want to decrypt the  ciphertext c=13<br />
  <strong>m = c<sup>d</sup> mod n = 13<sup>7</sup> mod 33 = 7 </strong>which is the original message text.</p>
<p>&nbsp;</p>
<h3 align="center">Your Mission</h3>
<p align="left">If you decide that you want to try and find this cache, you will be asked to follow a link to a web page where you will enter your geocaching login name and a password. The first time you go to the site, a unique modulus will be generated for you and you will be given that value and the public encryption key e. You will be asked to enter the other key (decryption key d) in order for you to log the cache. If you return to the site, you will be able to login with your goecaching login name and password and retrieve your unique modulus and encryption key. You will be prompted to enter the decryption key to be able to log the cache. Once you enter the correct decryption key, you will be given the coordinates of the cache and a flag will be set in the database notifying me that you are able to log the cache. </p>
</body>
</html>
