Thursday, November 21, 2013

Josephus Crypto

So suppose you have a message that you want to encrypt M. I'll just show a short one:
watson come here i need you
i mean if you have a minute

The basic idea I had was that you take the length of message M, n, which in this case is 54, and generate a key K which can be any number significantly greater than L. For this example it will be 386. Then to find the first letter of the new message find the 386th letter of the message modulo L. 386 mod 54 is 8. The eighth letter of the message (first letter is letter 0) is the o in "come" which becomes the first letter of the new message S.

Now the letter that was chosen is removed from the original message to generate M2.
watson cme here i need you
i mean if you have a minute

To get the second letter of the new message start with the next letter after the one removed and count to the 386th letter after that this time modulo 53 because there are 53 letters in the message. Mathematically that is (7+386) mod 53 = 22 (remember it is a 7 instead of an 8 because the first letter is letter 0). The 22th letter of the message is the space before the first y so that becomes the second letter of the new message S and this whole process iterates until all the letters from M are now in S.
o eenuwham  su nem i  euia
i eea v  aefdmiyoronynhtoct

python code:
def main():
M = "watson come here i need you i mean if you have a minute"
S = ""
K = 386
p = 0
while len(M) > 1:
i = (p+K)%(len(M)-1)
S+=M[i]
M = M[:i] + M[(i+1):]
print(S)
main()

To decode, start with an empty string and build it up in reverse.
The name:
It's related to the Josephus problem which is based on a historical occurrence:
http://en.wikipedia.org/wiki/Josephus_problem

It's sort of a different dimension to cryptography, that instead of scrambling the value of the characters as the starting point you scramble the order that they appear. But you could also combine both...