<h1 align="center"><img src=
    "http://img.geocaching.com/cache/5c909624-96ad-4102-9f43-dcb8696d4029.jpg"
     alt="Public Key Crypto" width="178" height="241" align="right"
     class="floatRight"></h1>
<h2>The Cache is not at the posted coordinates</h2>
<br>
<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 "trap doors"
in their products, so that the Government can read anyone's
encrypted messages. It reads: "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."</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’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><strong>I was involved in the porting of PGP to A/UX
(Apple’s Unix). Each member of the TOM Creative Group was asked to come up with a puzzle on their own that refelcts something about that individual. So given my PGP porting background, I (ppporch) thought a puzzle based on a simplified RSA factoring of a modulus
would be interesting problem for my contribution to the TOM Creative Group puzzle that reflects something about me. </strong></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></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>· <em><strong>n</strong></em> is known as the modulus<br>
 · <em><strong>e</strong></em> is known as the public exponent or
encryption exponent<br>
· <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 = 1 mod(f(n))&nbsp;<br>
 or&nbsp;d = e<sup>-1</sup> mod phi(n)<br>
 or find d such that f(n) divides (ed – 1)&nbsp;<br>
 or find d such that 20 divides 3d –
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 would like to try and do the math, you need to follow the link below and there you will be asked your geocaching log name that will be tied to a unique puzzle for you. Once you solve the puzzle, you will be shown the coordinates for the cache and will be eligible to log it. Any logs without a corresponding solved puzzle for that log name will be deleted. </p>
<h3>The web site to go to is: <a href=
"http://tom.theporch.com">Take me to the site</a></h3>
<center>
<h2 align="center">A</h2>
<p align="center"><img src=
"http://img.geocaching.com/cache/6bfba2ee-cb1b-4a87-8c5b-16f041c1b079.jpg">
</p>
<h2 align="center">Production</h2></center>