<?php require_once('Connections/TOM.php'); ?>
<?php
if (isset($_POST['pwd'])) { $_POST['pwd'] = sha1($_POST['pwd']); }
if (!function_exists("GetSQLValueString")) {
function GetSQLValueString($theValue, $theType, $theDefinedValue = "", $theNotDefinedValue = "") 
{
  $theValue = get_magic_quotes_gpc() ? stripslashes($theValue) : $theValue;
global $TOM;
  $theValue = function_exists("mysqli_real_escape_string") ? mysqli_real_escape_string($TOM, $theValue) : mysqli_real_escape_string($TOM, $theValue);

  switch ($theType) {
    case "text":
      $theValue = ($theValue != "") ? "'" . $theValue . "'" : "NULL";
      break;    
    case "long":
    case "int":
      $theValue = ($theValue != "") ? intval($theValue) : "NULL";
      break;
    case "double":
      $theValue = ($theValue != "") ? "'" . doubleval($theValue) . "'" : "NULL";
      break;
    case "date":
      $theValue = ($theValue != "") ? "'" . $theValue . "'" : "NULL";
      break;
    case "defined":
      $theValue = ($theValue != "") ? $theDefinedValue : $theNotDefinedValue;
      break;
  }
  return $theValue;
}
}
?>
<?php
// *** Validate request to login to this site.
if (!isset($_SESSION)) {
  session_start();
}

$loginFormAction = $_SERVER['PHP_SELF'];
if (isset($_GET['accesscheck'])) {
  $_SESSION['PrevUrl'] = $_GET['accesscheck'];
}

if (isset($_POST['username'])) {
  $loginUsername=$_POST['username'];
  $password=$_POST['username'];
  $MM_fldUserAuthorization = "";
  $MM_redirectLoginSuccess = "success.php";
  $MM_redirectLoginFailed = "loginfailed.php";
  $MM_redirecttoReferrer = false;
  // bool mysqli_connect_db($TOM, "thepord2_TOM");
  
  $LoginRS__query=sprintf("SELECT username, username FROM users WHERE username=%s AND username=%s",
    GetSQLValueString($loginUsername, "text"), GetSQLValueString($password, "text")); 
   
  $LoginRS = mysqli_query($TOM, $LoginRS__query) or die(mysqli_error($TOM));
  $loginFoundUser = mysqli_num_rows($LoginRS);
  if ($loginFoundUser) {
     $loginStrGroup = "";
    
    //declare two session variables and assign them
    $_SESSION['MM_Username'] = $loginUsername;
    $_SESSION['MM_UserGroup'] = $loginStrGroup;	      

    if (isset($_SESSION['PrevUrl']) && false) {
      $MM_redirectLoginSuccess = $_SESSION['PrevUrl'];	
    }
    header("Location: " . $MM_redirectLoginSuccess );
  }
  else {
    header("Location: ". $MM_redirectLoginFailed );
  }
}
?>
<!DOCTYPE html >
<html >
<html lang = "en" >
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>GC1D4JV Start</title>
<link href="admin.css" rel="stylesheet" type="text/css" />
<link rel = "stylesheet" href = "https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-alpha.6/css/bootstrap.min.css" integrity = "sha384-rwoIResjU2yc3z8GV/NPeZWAv56rSmLldC3R/AZzGRnGxQQKnKkoFVhFQhNUwEyJ" crossorigin = "anonymous" >
</head>
<script type="text/javascript">
var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
</script>
<script type="text/javascript">
try {
var pageTracker = _gat._getTracker("UA-2922014-6");
pageTracker._trackPageview();
} catch(err) {}</script>
<body>
<h1 class="text-success text-center">GC1D4JV</h1>
<div style="display: block; padding: 4rem">
<!-- <div align="center">
  <h1>GC1D4JV</h1>
</div> -->
<div >
  <h6>Welcome to The Prime Factor geocaching site. If you are an existing user, please login to the site. <br />
If you have not registered, please follow this link: <a  href="newuser.php">NEW USER</a></h6>
</div>
<form id="login" name="login" method="POST" action="<?php echo $loginFormAction; ?>">
<div class="form-group">
  <p>
    <label for="textfield">Geocaching Log Name:</label>
    <br />
    <input type="text" name="username" id="username" class="form-control" />
  </p>
  <p>
    <input name="doLogin" type="submit" id="doLogin" value="Login" />
</p>
</div>
</form>
<p align="center">RSA Encryption</p>
<img src="publickey.jpg" alt="public key" align="right" class="floatRight" style="padding: 1rem;" />
<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 intensive  and runs 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 with. 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>
<p   align="center"><em>The RSA  algorithm in detail</em></p>
<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 </em><em>p</em><em> and </em><em>q</em></li>
  <li><em>Compute </em><em>n</em><em>=</em><em>pq</em></li>
  <li><em>Compute the totient</em><em> &#966;(n) = (p-1)(q-1) </em>this is used to find the modular multiplicative inverse of one of the exponents</li>
  <li><em>Choose an integer </em><em>e </em><em>such that 1 &lt; e &lt; &#966;(n) &nbsp;and </em><em>e </em><em>and &#966(n)&nbsp;are coprime (share no  common factors other than 1) and frequently is chosen as </em><em>3</em><em> or </em><em>17</em><em> or 65537</em><em></em><em>.</em></li>
  <li><em>Compute </em><em>d </em><em>such that 1 &lt; d &lt;&#966;(n) &nbsp;and ed &#8801; 1 mod &#966;(n) &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  (<em>n,e</em>) and the private key is (<em>n,d</em>). The values of <em>p</em>,<em>q</em>, and &#966;(n) &nbsp;should be kept secret.</li>
</ol>
<p> &#8729; <em>n</em> is known as the modulus<br />
  &#8729; <em>e</em> is known as the public exponent or  encryption exponent<br />
  &#8729; <em>d</em> is known as the private exponent or  decryption exponent</p>
<p>This &quot;classic&quot; description is not exactly how it is implemented in real life as it is insecure.</p>
<p>ENCRYPTION:</p>
<p>Divide the message into blocks such that the bit-string of the message can be viewed as a 200-digit number lets say. Call that block, m.</p>
<p>Compute and send the encrypted message c ≣ m^e (mod n)</p>
<p>DECRYPTION:</p>
<p>Compute c raised to the d power ≣ c^d ≣(m^e)^d ≣ m^ed ≣ m^kø(n) +1 ≣ m^kø(n) * m ≣ 1*m ≣ m (modulo n)</p>
<p>&nbsp;</p>
<p   align="center">A very simple example of RSA encryption</p>
<p   align="center">This example can be done using a calculator or by  hand.</p>
<ol>
  <li>Choose p=41 and  q=53</li>
  <li>n=pq  =41*53=2173&nbsp; and ø(n) = (p-1)(q-1)=(40)(52)=2080</li>
  <li>choose e=623 which  is &gt;1 and coprime to &oslash;(n)=2080 ie they have no common factors </li>
  <li>compute d such  that ed &#8801; 1 mod(&oslash;(n))&nbsp;<br />
    or d = e <sup>-1</sup>mod &oslash;(n)<br />
    or find d such that  &oslash;(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>The answer is 207 for d</li>
</ol>
<p>There is a algorithm to generate the multiplicative inverse given the &oslash;(N). This is called the Euler &oslash;-function</p>
<p>The easiest way to do this is to:</p>
<p>Begin by writing down a 3X2 array (called A) where the first row of A consists of the modulus and the number to invert; the second and third rows consist of the rows of the (2X2) identity matrix. In our situation, the modulus we want to use if the &oslash;(n). The following steps are performed until the last element of the top row is zero.</p>
<ol>
  <li>The greatest integer multiplier (m) of the [1,2]- element of the array is found, such that the product is less than the [1,1] element of the array. Then A[1,1] - m*A[1,2] is computed.</li>
  <li>It is only necessary to carry two columns' worth of information. Thus A[1,1] can be replaced by A[1,2], and A[1,2] by the quatity computed in 1 above.</li>
  <li>The same process is carried out for the second and third rows: computing A[j,1] - m*A[j,2], replacing A[j,1] by A[j,2], and A[j,2] by the previous computation (j = 2,3).</li>
  <li>Once A[1,2] becomes zero, the desired inverse is the value of A[3,1].</li>
</ol>
<p>The calculation to compute the inverse of 623 (mod 2080) is as follows (from the above algorithm)</p>
<table class="table table-striped table-sm table-bordered" style="width: 80%">
  <tr>
    <th scope="row" >m</th>
    <td >&nbsp;</td>
    <td >&nbsp;</td>
    <td >3</td>
    <td >2</td>
    <td >1</td>
    <td >20</td>
    <td >10</td>
  </tr>
  <tr>
    <th scope="row" >A[1,j]</th>
    <td>2080</td>
    <td>623</td>
    <td>211</td>
    <td>201</td>
    <td>10</td>
    <td>1</td>
    <td>0</td>
  </tr>
  <tr>
    <th scope="row" >A[2,j]</th>
    <td>1</td>
    <td>0</td>
    <td>1</td>
    <td>-2</td>
    <td>3</td>
    <td>-62</td>
    <td>&nbsp;</td>
  </tr>
  <tr>
    <th scope="row" >A[3,j]</th>
    <td>0</td>
    <td>1</td>
    <td>-3</td>
    <td>7</td>
    <td>-10</td>
    <td>207</td>
    <td>&nbsp;</td>
  </tr>
</table>
<p>Thus the required inverse is 207. (This is what you would need to plug in on the site as the answer).</p>
<p>623 * 207 (Mod 2080) is 128961 (Mod 2080) which is 1 because 2080 divides into 128961 62 times with a remainder of 1.</p>
<p>Now to use this, to encrypt a message, we take the message, raise it to the power of the encryption exponent and reduce it modulus n</p>
<p>&nbsp;</p>
<p>Now for a very simple example: choose p=17, q=23, then pq=n=391, compute the ø(n) = (17-1)(23-1) = (16)(22)=352</p>
<p>Choose the encryption exponent to be 29. Publish 29 and 391 and now calculate the secrete decryption exponent.</p>
<p>&nbsp;</p>
<table class="table table-striped table-sm table-bordered" style="width: 80%">
  <tr>
    <th scope="row">m</th>
    <td>&nbsp;</td>
    <td>&nbsp;</td>
    <td>12</td>
    <td>7</td>
    <td>4</td>
  </tr>
  <tr>
    <th scope="row">A[1,j]</th>
    <td>352</td>
    <td>29</td>
    <td>4</td>
    <td>1</td>
    <td>0</td>
  </tr>
  <tr>
    <th scope="row">A[2,j]</th>
    <td>1</td>
    <td>0</td>
    <td>1</td>
    <td>-7</td>
    <td>&nbsp;</td>
  </tr>
  <tr>
    <th scope="row">A[3,j]</th>
    <td>0</td>
    <td>1</td>
    <td>-12</td>
    <td>85</td>
    <td>&nbsp;</td>
  </tr>
</table>
<p>So 85 is our calculated decryption exponent</p>
<p>29*85 (mod 352) = 2465 (mod 352) = 7*352 +1 = 1 The answer you would plug in on the site is 85</p>
<p>Now one more time ultra simple:</p>
<p>lets choose p=5 and q = 17, then pq = 85, (4)(16) = 64, choose e to be 3</p>
<table class="table table-striped table-sm table-bordered" style="width: 80%">
  <tr>
    <th scope="row">m</th>
    <td>&nbsp;</td>
    <td>&nbsp;</td>
    <td>21</td>
    <td>3</td>
  </tr>
  <tr>
    <th scope="row">A[1,j]</th>
    <td>64</td>
    <td>3</td>
    <td>1</td>
    <td>0</td>
  </tr>
  <tr>
    <th scope="row">A[2,j]</th>
    <td>1</td>
    <td>0</td>
    <td>1</td>
    <td>&nbsp;</td>
  </tr>
  <tr>
    <th scope="row">A[3,j]</th>
    <td>0</td>
    <td>1</td>
    <td>-21</td>
    <td>&nbsp;</td>
  </tr>
</table>
<p>So our answer is -21. To convert this to a positive number, add it to the modulus 64 to get 43 as our exponent.</p>
<p>43 * 3 = 129 and 129 (mod 64) = 2*64 +1 = 1 (mod 64).</p>
<p>so lets encrypt the number 5 (<a href="https://www.wolframalpha.com">wolfram alpha</a> is a great site to help with this)</p>
<p>5 ^ 3 (mod 85) = 40 to the encrypted message would be 40.</p>
<p>to decrypt,</p>
<p>40 ^ 43 (mod 85) = 5 (which is our original message).</p>
<p>&nbsp;</p>
<p>I hope this gives you an idea on how the RSA encryption works.</p>
<p>&nbsp;</p>
<p>&nbsp;</p>
<p>So our answer is -21. In order to convert it to a positive number, we add it to the modulus 64 to get 43 as our exponent.</p>
          <p>43 * 3 = 129 and 129 (mod 64) = 2*64 +1 = 1 (mod 64).</p>
          <p>so lets <strong>encrypt</strong> the number 5 (<a href="https://www.wolframalpha.com">Wolfram Alpha</a> is a great site to help with this)</p>
          <p>5 ^ 3 (mod 85) = 40 to the encrypted message would be 40.</p>
          <p>to <strong>decrypt</strong>:</p>
          <p>40 ^ 43 (mod 85) = 5 (which is our original message).</p>
          <p>I hope this gives you an idea on how the RSA encryption works.</p>
          <p>If you decide you want to try solving this puzzle and logging this cache, you will need to follow the link at the top of the page to take you to my puzzle site. This site requires you to enter your name you will sign on the log sheet (This can be an individual geocaching name or a team name). This is needed to link the name on the log sheet with a unique puzzle. You will be given a choice of 10
            puzzles that have not been used to pick from.. You will then be asked to &quot;log in&quot; again with the log name and at that time you will be presented with your unique puzzle ( the modulus and the public encryption key e) and prompted to enter
            the private key (d) which you will have to calculate.</p>
            <p>If you enter the correct private key for that puzzle, you will be shown the coordinates for the cache and be allowed to log the cache. If you enter the wrong private key, you will be allowed
            to continue trying until you get it correctly or give up. You may not log the cache without first calculating the correct private key (and everyone will have their own unique modulus and encryption key), or your log will be deleted. You may undertake this as a team as long as you sign the log with the team name.</p>
<br />
<strong>Remember: </strong><a href="https://www.wolframalpha.com">Wolfram Alpha</a> is your friend.
<h2 align="center">A</h2>
<p align="center"><img src="images/Tom Creative Group.jpg" alt="TOM" width="288" height="184" /></p>
<h2 align="center">Production</h2>
<p>&nbsp;</p>
<script src = "https://ajax.googleapis.com/ajax/libs/jquery/3.1.1/jquery.min.js" ></script >
<script src = "https://cdnjs.cloudflare.com/ajax/libs/tether/1.4.0/js/tether.min.js" ></script >
<script src = "https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-alpha.6/js/bootstrap.min.js"
        integrity = "sha384-vBWWzlZJ8ea9aCX4pEW3rVHjgjt7zpkNpZk+02D9phzyeVkE+jo0ieGizqPLForn" crossorigin = "anonymous" ></script >
</div>
</body>
</html>
