The Codes: RSA Mystery Cache

This cache has been archived.

Dr_B: With very sporadic seekers of this series, I'm taking it off-line. This park appears to get very limited (legal?) use with the pool out of commission. Cache was still in place and visible from 15' away.

More
Hidden : 6/26/2008
Difficulty:
3.5 out of 5
Terrain:
1.5 out of 5

Size: Size: micro (micro)

Join now to view geocache location details. It's free!

Watch

How Geocaching Works
Looking for a different adventure?

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

Geocache Description:

This cache is one of a series designed to introduce cachers to the use of encryption codes. CACHE IS NOT AT THE POSTED COORDINATES, but is within a mile. This cache is only available during daylight hours. BYOP.

RSA Encryption


UPDATE: 12/18/2008 moved cache and changed initial and final coordinates accordingly

RSA Encryption is a mathematics based encryption system. The strength of RSA lies in the large amount of computation necessary for factoring very large numbers (numbers with hundreds of digits!). The system is named after Ron Rivest, Adi Shamir, and Leonard Adleman and was developed by them in 1977.

It is different from most other codes because it is not necessary for the sender and receiver to agree on a key (be it a word, phrase, matrix, chapter, etc.). Not only that, but the recipient actually acts first and announces a "public key" indiscriminately.

So where does the key come from? Here are the steps (it can be complicated if you're not used to these numbers, so brace yourself):
  1. Choose two prime numbers P and Q. In actual use you would probably want these to be 100 digits or so.
  2. Multiply the two to get N=P*Q, called the modulus.
  3. Subtract one from each and multiply the results to get T=(P-1)*(Q-1), called the totient.
  4. Choose another prime number E that is smaller than T and does not divide evenly into it (other numbers will work, but primes are easiest).
  5. Find a positive number D such that D*E=1+kT for a number k, or D*E is one more than some multiple of T. This is a tricky step, and can take some effort, but with relatively small numbers it is easiest to see if you can make k=1 work, then k=2, ...
For an example here, I will use P=13 and Q=11. This means N=13*11=143 and T=12*10=120. E=7 will work for this example since 7 does NOT go into 130 evenly. Then to find D, it turns out that 7*103=1+6*120, which means D=103.

Now tell the world what N and E are. Together, these are called the "public key". N and D are the "private key".

To encode, convert your message into numbers and break the resulting string of numbers up so that each chunk gives a number less than N. Then raise each number to the power E, modulo N (this uses modular arithmetic also known as clock arithmetic – for a refresher, see here). Confused? Let’s return to our example.

Using A=1, B=2, … the message HELLO becomes 85121215, which can be broken up into 8 51 21 21 5 (any way to break them up is okay as long as you have numbers smaller than N). Because E=7 in the example, raise each number to the seventh power, so we get 8*8*8*8*8*8*8=2097152, but we really want to send the remainder when dividing by N=143, which gives 57. Likewise 51 will become 116, 21 will become 109 (twice), and 5 will become 47. The coded message is 57 116 109 109 47.

Decoding is the same process except using D instead of E as the power.

One possibly helpful hint for keeping numbers small (ignore if you are confused) – it is okay to divide by N between each time you multiply a number by itself. For example, since 85*85=7225, which leaves a remainder of 75 when dividing by 143, we can then do 85*85*85=75*85=6375=83 mod 143, thus keeping the numbers somewhat smaller. There are further shortcuts, but I will leave that to you to discover!

If I have lost you, here are some links to more information about RSA and other explanations of the processes involved:
Wikipedia's article - very useful, as usual
Guts of RSA - slightly different take on RSA
RSA Algorithm - in-depth explanation and examples

As this is an educational cache, the first finder must have solved the puzzle on his/her own.

Your task, should you choose to accept it, is to break the following message sent to me using the public key N=11009, E=1543 and follow the instructions contained within.
10287 6783 3906 7974 2463 5629 8967 4721 3637
8510 1038 5577 1364 4275 2876 118 7892 8745
7976 5650 9150 7199 8599 7552 45 4916

Additional Hints (No hints available.)



Advertising with Us

Inventory

View past Trackables

What are Trackable Items?

Bookmark Lists

View all bookmark lists...