Jump to content

One-time Pad Question


Recommended Posts

Not asking for the solution to a puzzle or how to solve it... but if anyone could point me to a ONE-TIME PAD FOR DUMMIES type of site - that would be great. I have the key and I've gone through what I thought to be the formula but it came out <sigh> nonsense :unsure: . CO hasn't gotten back to me when I sent in what I thought to be the way to solve it... but did confirm I had the correct key... so my breakdown is on the formula mechanica. Again, not looking for help with the puzzle - just help with one-time pads in general. Trying to get help without violating TOS. :huh: Thank you!

 

HH

Link to comment

niraD, yes - I read some articles posted when I searched for puzzle caches in general (from here - think they were yours?). I then went to the wikipedia article. I read that - thought I understood... then did a tutorial here: http://s13.zetaboards.com/Crypto/topic/123779/1/ and... I've also looked at examples at various websites. :unsure: Tried to decrypt and I am for sure missing something.

Link to comment

The gist of the one-time pad is that you have to know the correct key to successfully decode the message, OR know part of the message to derive the corresponding part of the key, and then use that to make an educated guess about the rest of the key.

 

Since you already have the key, the question is how to apply the key to the message. There's a million different ways, but they all have to be reversible.

 

A common way is to use alphabet shifts, much like the Caesar cipher (of which the well-known ROT13 is a variant), but with a different amount of shift for each letter. The shift to be used for each letter is then determined by the corresponding letter of the key. Does this make any sense to you?

 

Edit: The letter-shift method is actually described in detail under "examples" in the wikipedia article.

Edited by dfx
Link to comment

Hmm - Okay the ROT13 is what geocaching.com uses as it's variant, yes? I am not thinking it shifts, to be honest. Where I think my breakdown is: One of the OTP tutorials suggests "One-Time Pad decryption uses a non-standard type of subtraction. Carefully note how the subtraction was done. When a larger number is subtracted from a smaller number, the smaller number is actually "10 + that number". Therefore, 1-9=2, because 1+10-9=2. and: 6-7=9, because 6+10-7=9." - thus, the magic number is 10... However, another tutorial suggests that the magic number variant when using negative numbers is 26. I'm unsure if there is a OTP standard number, or the magic number variant can be changed. I think this is where I am missing the mark. Does that make sense?

Link to comment

I'd guess they're talking about the wrap-around case. If you're working on an alphabet, you only have 26 letters, right? So you number the letters 1-26 (A-Z). Then if you were to shift the letter S (19) by 15 positions, you'd have 19+15=34. Now there's no letter with the number 34, so you have to wrap the number around by subtracting 26, giving you 8, making it an H. To decode, you have to reverse the process: 8-15=-7, -7+26=19.

 

If you number the letters 0-25 instead of 1-26, you can use the modulo operation to do it for you: S would then be 18, so 18+15=33, 33 mod 26 = 7, and 7=H. The same works the other way around.

 

In any case, the "magic number" is simply how many different values you have. If you're encoding letters, it's gonna be 26. If you're encoding numeric digits, it's gonna be 10 (0-9). If you're working on an alphabet that distinguishes between upper and lower cases, it's gonna be 52 (26+26). If you're working with binary bytes, it's gonna be 256. etc.

Edited by dfx
Link to comment

Yes, that makes sense... but I used both the 10 and the 26 when a negative number came out of the process... and nothing. Let's say the key is "PUMPERNICKEL" does the number of letters (12) get involved in a one-time pad? Or is "pumpernickel" the only key. So let's say the coded letters (random... just hitting the keyboard...)

 

TWXWU WXAUR NI

Then, would the formula be:

T(20) - P(16) MOD 10 or 26?= 4 D

W(23) - U(21) MOD 10 or 26?= 1 A

X(24) - M(13) MOD 10 or 26?= 11 K

W(23) - P(16) MOD 10 or 26?= 7 G

U(21) - E(05) MOD 10 or 26?= 16 P

W(23) - R(18) MOD 10 or 26?= 5 E

X(24) - N(14) MOD 10 or 26?= 10 J

A(01) - I(09) MOD 10 or 26?= 1 - 9 = -8+10 or 26?

U(21) - C(03) MOD 10 or 26?= 18 R

R(18) - K(11) MOD 10 or 26?= 7 G

N(14) - E(05) MOD 10 or 26?= 9 I

I(09) - L(12) MOD 10 or 26?= 9 - 12 = -3+10 or 26?

 

So my PRE-CODED message would be (if it made sense) - DAKGPEJ?RGI?

 

 

and so on with my key "pumpernickel" matching up to my given code? Sigh - seriously need a one-time pad for those of us that are a little less gifted in other hemisperes of our brains... but with enough stubborness to not give up! Am I close to understanding how to do this? Am I way off in this formula? Again, this is in no way trying to violate terms of service... but I just want to know how to solve a one-time pad.

 

HH

Link to comment

Yeah, almost. The "magic number" is always the number of distinct symbols in your alphabet (which can be anything). If your alphabet is the regular English alphabet, it's gonna be 26, because the "symbols" are the letters, and there's 26 distinct letters.

 

To make it easier, number the letters A-Z as 0-25, because then you can use the modulo operation.

Your key PUMPERNICKEL then translates to the numbers: 15 20 12 15 4 17 13 8 2 10 4 11

And your ciphertext (ignoring the spaces) translates to: 19 22 23 22 20 22 23 0 20 17 13 8

Now, assuming the encryption was done by doing a "right-shift" (addition) of the alphabet by the letter number of the key, the reversal would be subtraction, together with the modulo, giving you:

 

( 19 [T] - 15 [P] ) modulo 26 = 4 [E]

( 22 [W] - 20 ) modulo 26 = 2 [C]

( 23 [X] - 12 [M] ) modulo 26 = 11 [L]

( 22 [W] - 15 [P] ) modulo 26 = 7 [H]

( 20 - 4 [E] ) modulo 26 = 16 [Q]

( 22 [W] - 17 [R] ) modulo 26 = 5 [F]

( 23 [X] - 13 [N] ) modulo 26 = 10 [K]

( 0 [A] - 8 ) modulo 26 = 18

( 20 - 2 [C] ) modulo 26 = 18

( 17 [R] - 10 [K] ) modulo 26 = 7 [H]

( 13 [N] - 4 [E] ) modulo 26 = 9 [J]

( 8 - 11 [L] ) modulo 26 = 23 [X]

 

And that's what it would decrypt to. Note that when encryption was done by a "left-shift" (subtraction), decryption would be done using addition, not subtraction. Also, for interpreting the letters of the key as numbers, instead of 0-25 for A-Z it could also be 1-26 (meaning an "A" in the key would not cause a shift by 0, but rather a shift by 1), or backwards 26-1 ("A" would shift by 26 and "Z" by 1) or any such thing.

Edited by dfx
Link to comment

Kudos to you for trying the one time pad by hand. Now that you've paid your dues, check out the online decoder at rumkin.com.

 

You mentioned that you had considered Mod 26. Another variant that is sometimes used is Mod 36 - this incorporates the 26 letters and the numerals 0-9. There are other variants as well that use punctuation characters.

Link to comment

Ah - okay this is VERY helpful... and yes I did 133 letters in the code this way (by hand) with both MOD 10 and MOD 26.

 

I just tried the program through rumkin with a snippet of the code and I think it may work. Is it sick that I still want to figure this out by hand? What is WRONG with me? I'm a musician/artist type... what has geocaching done to me? :lol::blink: I tend to do things the hard way.

 

HH

Link to comment

People are using the term "one-time pad" incorrectly here.

 

  • If they key is shorter than the ciphertext, it's not a one-time pad.
  • If the key is from a book or other text, it's not a one-time pad.
  • If the key is generated by some function, it's not a one-time pad.
  • If the key is ever re-used for another decryption, it's not a one-time pad.

This one sounds like a running-key or stream cipher. It might also be a Vigenere cipher, in which the key length is shorter than the ciphertext.

 

There are two ways commonly used to encrypt ciphertext with a running key or stream cipher:

 

  • Modular addition, where the modulus is the length of the alphabet being used. 26 and 36 are common, although I have also seen 52 and 62 used with case sensitivity.
  • The exclusive-or or XOR operation. This is more commonly used on binary data, but there is a variant that can be used on alphabets.

If you will send me the link to the cache page I would be glad to explain how you can figure out which one is being used, without giving away the answer.

Link to comment

I solved it using the program for a one-time pad at rumkin.com. Obviously the CO was not a code purist as I repeated the key to solve... i.e. pumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickel. I had already tried the Vigenere cipher (amongst others) and came up dry. I read the directions more carefully which eluded to the perfection in security of the code. So I searched "perfect security" and code to come up with One-Time Pad. I also figured out the key as the cache name. I emailed the CO with the key and the "One-Time Pad" suggestion and he said I was on the right track. SO glad this is solved. My first REAL puzzle cache solved. However, the find is also going to be a challenge apparently. Phew. I will sign this log with a great deal of satisfaction. :D

Link to comment

No wonder I can't solve these types of caches--I don't even understand what y'all are saying! Good thing there are still hundreds of other cache types within just 10 miles of my home.

 

Quite honestly most of the time I figure these things out the hard way :unsure: using really weird methods that are way more difficult than they should be. I'm just more stubbourn than mentally gifted... so it works for me.

Link to comment

I solved it using the program for a one-time pad at rumkin.com. Obviously the CO was not a code purist as I repeated the key to solve... i.e. pumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickel. I had already tried the Vigenere cipher (amongst others) and came up dry. I read the directions more carefully which eluded to the perfection in security of the code. So I searched "perfect security" and code to come up with One-Time Pad. I also figured out the key as the cache name. I emailed the CO with the key and the "One-Time Pad" suggestion and he said I was on the right track. SO glad this is solved. My first REAL puzzle cache solved. However, the find is also going to be a challenge apparently. Phew. I will sign this log with a great deal of satisfaction. :D

 

That is not a one time pad cipher. As someone else pointed out, the key length must be at least as long as the cipher text to make a one time pad. Try decrypting your cipher text using rumkin's Vigenere cipher decoder and see if that works. Once you've done that, repeat using the autokey Vigenere decoder and see if it works. Why or why not?

 

You are doing absolutely the right thing to work the ciphers by hand, if your goal is to understand them and not just get to the cache as quickly as possible. Of course once you understand what's going on, the computerized decoders eliminate a lot of the drudgery!

Link to comment

No wonder I can't solve these types of caches--I don't even understand what y'all are saying! Good thing there are still hundreds of other cache types within just 10 miles of my home.

Really. Sounds too much like work to me.

 

Believe it or not, some people actually enjoy playing with stuff like that :lol:

Link to comment

People are using the term "one-time pad" incorrectly here.

 

  • If they key is shorter than the ciphertext, it's not a one-time pad.
  • If the key is from a book or other text, it's not a one-time pad.
  • If the key is generated by some function, it's not a one-time pad.
  • If the key is ever re-used for another decryption, it's not a one-time pad.

This one sounds like a running-key or stream cipher. It might also be a Vigenere cipher, in which the key length is shorter than the ciphertext.

 

There are two ways commonly used to encrypt ciphertext with a running key or stream cipher:

 

  • Modular addition, where the modulus is the length of the alphabet being used. 26 and 36 are common, although I have also seen 52 and 62 used with case sensitivity.
  • The exclusive-or or XOR operation. This is more commonly used on binary data, but there is a variant that can be used on alphabets.

If you will send me the link to the cache page I would be glad to explain how you can figure out which one is being used, without giving away the answer.

I own a true one time pad cache. its got a few finds.

Link to comment

I solved it using the program for a one-time pad at rumkin.com. Obviously the CO was not a code purist as I repeated the key to solve... i.e. pumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickelpumpernickel. I had already tried the Vigenere cipher (amongst others) and came up dry. I read the directions more carefully which eluded to the perfection in security of the code. So I searched "perfect security" and code to come up with One-Time Pad. I also figured out the key as the cache name. I emailed the CO with the key and the "One-Time Pad" suggestion and he said I was on the right track. SO glad this is solved. My first REAL puzzle cache solved. However, the find is also going to be a challenge apparently. Phew. I will sign this log with a great deal of satisfaction. :D

 

That is not a one time pad cipher. As someone else pointed out, the key length must be at least as long as the cipher text to make a one time pad. Try decrypting your cipher text using rumkin's Vigenere cipher decoder and see if that works. Once you've done that, repeat using the autokey Vigenere decoder and see if it works. Why or why not?

 

You are doing absolutely the right thing to work the ciphers by hand, if your goal is to understand them and not just get to the cache as quickly as possible. Of course once you understand what's going on, the computerized decoders eliminate a lot of the drudgery!

 

The CO clues indicated it was a one-time pad - "a perfect security" and "KGB" were mentioned in the description. I did a search for "perfect security" and KGB and came up with the one-time pad wiki. Yet, the style of the puzzle looked more like a Vigenere. However, when I wrote to him and asked about the Vigenere or One-Time pad he said One-Time pad. He said it wasn't a cipher but a code. It worked in BOTH the one-time pad and the Vigenere programs, but you have to repeat the key in both.

 

I did get a great deal of satisfaction trying to decode this. It is something completely new to me, but I totally dug it. It satisfied this little craving in my brain that old video games used to (King's Quest, etc.). I will be doing more puzzle caches now :)

Link to comment
However, when I wrote to him and asked about the Vigenere or One-Time pad he said One-Time pad. He said it wasn't a cipher but a code. It worked in BOTH the one-time pad and the Vigenere programs, but you have to repeat the key in both.

That's because when you take what a one-time pad does, apply it to an alphabet-shift as explained above, and use a key that's not random and repeated to match the length of the plaintext (which already makes it not a one-time pad), what you get is Vigenere :) So I agree: this is not an OTP, it's Vigenere.

Link to comment

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...