Really Simple Arithmetic Mystery Cache
-
Difficulty:
-
-
Terrain:
-
Size: 
(small)
Please note Use of geocaching.com services is subject to the terms and conditions
in our disclaimer.
The Cache is not at the given coordinates, but they are a good and safe place to park.
A lot of modern computer security is based on some surprisingly simple arithmetic, the RSA algorithm.
RSA (which stands for Rivest, Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography and was one of the first great advances in public key cryptography.
RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations. RSA involves a public key and a private key. Thepublic key can be known to everyone and is used for encrypting
messages. Messages encrypted with the public key can only be decrypted using the private key.
The keys for the RSA algorithm aregenerated the following way:
Choose two distinct prime numbers p and q.
Compute n = pq.
n is used as the modulus for both the public and private keys
Compute f(pq) = (p - 1)(q - 1) Choose an integer e such that 1
e is released as the public key exponent.
Determine d which satisfies de=1 (mod f(pq)).
Stated differently, ed - 1 can be evenly divided by (p - 1)(q - 1).
d is kept as the private key exponent.
The public key consists of the modulus n and the public exponent e.
The private key consists of the modulus n and the private exponent d which must be kept secret.
Encryption: Consider 2 people, Alice and Bob, trying to send a secure message.
Alice transmits her public key (n,e) to Bob and keeps the private key secret. Bob then wishes to send message m to Alice.
He then computes the ciphertext c corresponding to: m^e=c(mod n) Bob then transmits c to Alice.
Decryption: Alice can recover m from c by using her private key exponent d by the following computation:
c^d=m (mod n)
The strength of RSA comes from the difficulty of finding p and q for a given n, but if you can find p and q, you can run through the mathematics of key generation to find the value for d, and hence decrypt the message.
The message you need to crack is the decimal degrees of the coordinates.
The cipher text is 16658, 84012.
The public key is [118241,19]
Once you crack this the cache is hidden a short walk from a track, approach the location from below, and climb in, and then up. Good luck!
PS: if you manage to crack this example,
don't worry too much about your online banking being hacked, you had to factorize a number, n, of the order of 10^6, for standard security protocol, n is of order 10^200 or more.
Additional Hints
(No hints available.)
Treasures
You'll collect a digital Treasure from one of these collections when you find and log this geocache:
Loading Treasures