# A Brief Notebook on Cryptography

github 上有一个版本的笔记。

# 凯撒转移

## Demo-1

alpha = "abcdefghijklmnopqrstuvwxyz".upper()
punct = ",.?:;'\n "

from functools import partial

def shift(l, s=2):
l = l.upper()
return alpha[(alpha.index(l) + s) % 26]

def caesar_shift_encrypt(m, s=2):
m = m.upper()
c = "".join(map(partial(shift, s=s), m))
return c

def caesar_shift_decrypt(c, s=-2):
c = c.upper()
m = "".join(map(partial(shift, s=s), c))
return m

print "Original Message: HI"
print "Ciphertext:", caesar_shift_encrypt("hi")


Original Message: HI Ciphertext: JK

## Demo-2

m = """To be, or not to be, that is the question:
Whether 'tis Nobler in the mind to suffer
The Slings and Arrows of outrageous Fortune,
Or to take Arms against a Sea of troubles,
And by opposing end them."""

m = "".join([l for l in m if not l in punct])

print "Original Message:"
print m

print
print "Ciphertext:"
tobe_ciphertext = caesar_shift_encrypt(m)
print tobe_ciphertext


Original Message: TobeornottobethatisthequestionWhethertisNoblerinthemindtosuffer TheSlingsandArrowsofoutrageousFortuneOrtotakeArmsagainstaSeaof troublesAndbyopposingendthem

Ciphertext: VQDGQTPQVVQDGVJCVKUVJGSWGUVKQPYJGVJGTVKUPQDNGTKPVJGOKPFVQUWHHGT VJGUNKPIUCPFCTTQYUQHQWVTCIGQWUHQTVWPGQTVQVCMGCTOUCICKPUVCUGCQH VTQWDNGUCPFDAQRRQUKPIGPFVJGO

print "Decrypted first message:", caesar_shift_decrypt("JK")


Decrypted first message: HI

print "Decrypted second message:"
print caesar_shift_decrypt(tobe_ciphertext)


Decrypted second message: TOBEORNOTTOBETHATISTHEQUESTIONWHETHERTISNOBLERINTHEMINDTOSUFFER THESLINGSANDARROWSOFOUTRAGEOUSFORTUNEORTOTAKEARMSAGAINSTASEAOF TROUBLESANDBYOPPOSINGENDTHEM

# 替换密码

import random
permutation = list(alpha)
random.shuffle(permutation)

# Display the new alphabet
print alpha
subs = "".join(permutation)
print subs


ABCDEFGHIJKLMNOPQRSTUVWXYZ EMJSLZKAYDGTWCHBXORVPNUQIF

def subs_cipher_encrypt(m):
m = "".join([l.upper() for l in m if not l in punct])
return "".join([subs[alpha.find(l)] for l in m])

def subs_cipher_decrypt(c):
c = "".join([l.upper() for l in c if not l in punct])
return "".join([alpha[subs.find(l)] for l in c])
m1 = "this is a test"

print "Original message:", m1
c1 = subs_cipher_encrypt(m1)

print
print "Encrypted Message:", c1

print
print "Decrypted Message:", subs_cipher_decrypt(c1)


Original message: this is a test

Encrypted Message: VAYRYREVLRV

Decrypted Message: THISISATEST

print "Original message:"
print m

print
c2 = subs_cipher_encrypt(m)
print "Encrypted Message:"
print c2

print
print "Decrypted Message:"
print subs_cipher_decrypt(c2)


Original message: TobeornottobethatisthequestionWhethertisNoblerinthemindtosuffer TheSlingsandArrowsofoutrageousFortuneOrtotakeArmsagainstaSeaof troublesAndbyopposingendthem

Encrypted Message: VHMLHOCHVVHMLVAEVYRVALXPLRVYHCUALVALOVYRCHMTLOYCVALWYCSVHRPZZLO VALRTYCKRECSEOOHURHZHPVOEKLHPRZHOVPCLHOVHVEGLEOWREKEYCRVERLEHZ VOHPMTLRECSMIHBBHRYCKLCSVALW

Decrypted Message: TOBEORNOTTOBETHATISTHEQUESTIONWHETHERTISNOBLERINTHEMINDTOSUFFER THESLINGSANDARROWSOFOUTRAGEOUSFORTUNEORTOTAKEARMSAGAINSTASEAOF TROUBLESANDBYOPPOSINGENDTHEM

# 德国的谜团

Enigma通过使用一系列齿轮或转子来工作，其位置决定了替代密码。在每封信之后，通过机械过程改变了职位。 一台Enigma机器是一台非常令人印象深刻的机器而且“用于帮助打破它们的”计算机“也非常令人印象深刻。

from random import shuffle,randint,choice
from copy import copy
num_alphabet = range(26)

def en_shift(l, n):                         # Rotate cogs and arrays
return l[n:] + l[:n]

class Cog:                                  # Each cog has a substitution cipher
def __init__(self):
self.shuf = copy(num_alphabet)
shuffle(self.shuf)                  # Create the individual substition cipher
return                              # Really, these were not random

def subs_in(self,i):                    # Perform a substition
return self.shuf[i]

def subs_out(self,i):                   # Perform a reverse substition
return self.shuf.index(i)

def rotate(self):                       # Rotate the cog by 1.
self.shuf = en_shift(self.shuf, 1)

def setcog(self,a):                     # Set up a particular substitution
self.shuf = a

class Enigma:
self.numcogs = numcogs
self.cogs = []
self.oCogs = []                     # "Original Cog positions"

for i in range(0,self.numcogs):     # Create the cogs
self.cogs.append(Cog())
self.oCogs.append(self.cogs[i].shuf)

refabet = copy(num_alphabet)
self.reflector = copy(num_alphabet)
while len(refabet) > 0:             # Pair letters in the reflector
a = choice(refabet)
refabet.remove(a)

b = choice(refabet)
refabet.remove(b)

self.reflector[a] = b
self.reflector[b] = a

def print_setup(self): # Print out substituion setup.
print "Enigma Setup:\nCogs: ",self.numcogs,"\nCog arrangement:"
for i in range(0,self.numcogs):
print self.cogs[i].shuf
print "Reflector arrangement:\n",self.reflector,"\n"

def reset(self):
for i in range(0,self.numcogs):
self.cogs[i].setcog(self.oCogs[i])

def encode(self,text):
t = 0     # Ticker counter
ciphertext=""
for l in text.lower():
num = ord(l) % 97
# Handle special characters for readability
if (num>25 or num<0):
ciphertext += l
else:
pass

else:
# Pass through cogs, reflect, then return through cogs
t += 1
for i in range(self.numcogs):
num = self.cogs[i].subs_in(num)

num = self.reflector[num]

for i in range(self.numcogs):
num = self.cogs[self.numcogs-i-1].subs_out(num)
ciphertext += "" + chr(97+num)

# Rotate cogs
for i in range(self.numcogs):
if ( t % ((i*6)+1) == 0 ):
self.cogs[i].rotate()
return ciphertext.upper()

plaintext="""When placed in an Enigma, each rotor can be set to one of 26 possible positions.
When inserted, it can be turned by hand using the grooved finger-wheel, which protrudes from
the internal Enigma cover when closed. So that the operator can know the rotor's position,
each had an alphabet tyre (or letter ring) attached to the outside of the rotor disk, with
26 characters (typically letters); one of these could be seen through the window, thus indicating
the rotational position of the rotor. In early models, the alphabet ring was fixed to the rotor
disk. A later improvement was the ability to adjust the alphabet ring relative to the rotor disk.
The position of the ring was known as the Ringstellung ("ring setting"), and was a part of the
initial setting prior to an operating session. In modern terms it was a part of the
initialization vector."""

# Remove newlines for encryption
pt = "".join([l.upper() for l in plaintext if not l == "\n"])
# pt = "".join([l.upper() for l in plaintext if not l in punct])

x=enigma(4)
#x.print_setup()

print "Original Message:"
print pt

print
ciphertext = x.encode(pt)
print "Encrypted Message"
print ciphertext

print
# Decryption and encryption are symmetric, so to decode we reset and re-encrypt.
x.reset()
decipheredtext = x.encode(ciphertext)
print "Decrypted Message:"
print decipheredtext


WHEN PLACED IN AN ENIGMA, EACH ROTOR CAN BE SET TO ONE OF 26 POSSIBLE POSITIONS. WHEN INSERTED, IT CAN BE TURNED BY HAND USING THE GROOVED FINGER-WHEEL, WHICH PROTRUDES FROM THE INTERNAL ENIGMA COVER WHEN CLOSED. SO THAT THE OPERATOR CAN KNOW THE ROTOR’S POSITION, EACH HAD AN ALPHABET TYRE (OR LETTER RING) ATTACHED TO THE OUTSIDE OF THE ROTOR DISK, WITH 26 CHARACTERS (TYPICALLY LETTERS); ONE OF THESE COULD BE SEEN THROUGH THE WINDOW, THUS INDICATING THE ROTATIONAL POSITION OF THE ROTOR. IN EARLY MODELS, THE ALPHABET RING WAS FIXED TO THE ROTOR DISK. A LATER IMPROVEMENT WAS THE ABILITY TO ADJUST THE ALPHABET RING RELATIVE TO THE ROTOR DISK. THE POSITION OF THE RING WAS KNOWN AS THE RINGSTELLUNG (“RING SETTING”), AND WAS A PART OF THE INITIAL SETTING PRIOR TO AN OPERATING SESSION. IN MODERN TERMS IT WAS A PART OF THE INITIALIZATION VECTOR.

RYQY LWMVIH OH EK GGWFBO, PDZN FNALL ZEP AP IUD JM FEV UG 26 HGRKODYT XWOLIYTSA. TJQK KBCNVMHG, VS YBB XI BYZTVU XP BGWP IFNIY UQZ IQUPTKJ QXPVYE-EAOVT, PYMNN RXFIOWYVK LWNN OJL JXZBTRVP YMQCXX STJQF KXNZ LXSWDC. LK KGRH ZKT RDZUMCWA GKY LYKC LLV ZNFAD’Z BAXLDFTH, QSHA NBY RZ SXEXDAMP FXUS (WC RWHZOX ARWP) VKYNDJQP WL OLW ICBALPI RV ISD GXSDQ ZKMJ, OHNN 26 IBGUHNYIQE (GDBNTEBWP QGECUNA); QPG SQ JYUQX NDBWB NM AAUF RUNKYDL OLD LMPZQV, ZMKP SQZFDEHKCI KLJ AKPZLRAZZX QXPJEXLV HS AFG IIMGK. NT PVAYP RFOKYV, XUY CHZAQEXG DUSS CKN YENSR FX PLS CYMZK YHTB. J RLZLB DNIDWNWAIOO HOK PGM HVXXHIJ VV SCTNIC QGM TFKPQYPQ XFQU PSAECHTX RA QUW CUNRV JCUW. LCP GFKZLLXW LN YWF OAQM CMF YVTQH EI JAU LZTXEYDGDFLQ (“CDBS TQHUEIR”), BLN QIG O UHJJ DV DQY KQGVFKI EBEFRCT WEZWG LJ WC NIAUKIYQJ EHZLZLS. TY XPZSBL IPGWN ZS IUY E YQMD BW NVF QYWSDMTRSNSHYO GJGNUL.

WHEN PLACED IN AN ENIGMA, EACH ROTOR CAN BE SET TO ONE OF 26 POSSIBLE POSITIONS. WHEN INSERTED, IT CAN BE TURNED BY HAND USING THE GROOVED FINGER-WHEEL, WHICH PROTRUDES FROM THE INTERNAL ENIGMA COVER WHEN CLOSED. SO THAT THE OPERATOR CAN KNOW THE ROTOR’S POSITION, EACH HAD AN ALPHABET TYRE (OR LETTER RING) ATTACHED TO THE OUTSIDE OF THE ROTOR DISK, WITH 26 CHARACTERS (TYPICALLY LETTERS); ONE OF THESE COULD BE SEEN THROUGH THE WINDOW, THUS INDICATING THE ROTATIONAL POSITION OF THE ROTOR. IN EARLY MODELS, THE ALPHABET RING WAS FIXED TO THE ROTOR DISK. A LATER IMPROVEMENT WAS THE ABILITY TO ADJUST THE ALPHABET RING RELATIVE TO THE ROTOR DISK. THE POSITION OF THE RING WAS KNOWN AS THE RINGSTELLUNG (“RING SETTING”), AND WAS A PART OF THE INITIAL SETTING PRIOR TO AN OPERATING SESSION. IN MODERN TERMS IT WAS A PART OF THE INITIALIZATION VECTOR.

# 公钥加密

Bartolo不是保密密码系统，而是告诉每个人（在我们的比喻中，他对整个教室大喊大叫）公钥K，并解释如何使用它向他发送信息。 Anabel使用此密钥加密她的消息。然后她将此消息发送给Bartolo。

Bartolo收到这条消息并且（只使用他知道的东西）他解密了这条消息。

## RSA

Bartolo取两个素数，如p = 12553和q = 13007。他注意到了他们的产品

m=pq=163276871

φ(m)=(p−1)(q−1)=163251312.

conversion_dict = dict()
alpha = "abcdefghijklmnopqrstuvwxyz".upper()
curnum = 11
for l in alpha:
conversion_dict[l] = curnum
curnum += 1
print "Original Message:"
msg = "NUMBERTHEORYISTHEQUEENOFTHESCIENCES"
print msg
print

def letters_to_numbers(m):
return "".join([str(conversion_dict[l]) for l in m.upper()])

print "Numerical Message:"
msg_num = letters_to_numbers(msg)
print msg_num


NUMBERTHEORYISTHEQUEENOFTHESCIENCES

2431231215283018152528351929301815273115152425163018152913191524131529

24312312,15283018,15252835,19293018,15273115,15242516,30181529,13191524,131529。 为了发送她的信息，她取出一个8位数的块并将其提升到k模数m的幂。也就是说，为了传输第一个块，她计算

24312312^79921≡13851252(mod 163276871).

# Secret information
p = 12553
q = 13007
phi = (p-1)*(q-1) # varphi(pq)

# Public information
m = p*q # 163276871
k = 79921

print pow(24312312, k, m)


13851252

uk=1+φ(m)v.

def extended_euclidean(a,b):
if b == 0:
return (1,0,a)
else :
x, y, gcd = extended_euclidean(b, a % b) # Aside: Python has no tail recursion
return y, x - y * (a // b),gcd           # But it does have meaningful stack traces

# This version comes from Exercise 6.3 in the book, but without recursion
def extended_euclidean2(a,b):
x = 1
g = a
v = 0
w = b
while w != 0:
q = g // w
t = g - q*w
s = x - q*v
x,g = v,w
v,w = s,t
y = (g - a*x) / b
return (x,y,g)

def modular_inverse(a,m) :
x,y,gcd = extended_euclidean(a,m)
if gcd == 1 :
return x % m
else :
return None
print "k, p, q:", k, p, q
print
u = modular_inverse(k,(p-1)*(q-1))
print u


k, p, q: 79921 12553 13007

145604785

13851252^u≡（24312312^k)^u≡24312312^(1+φ（PQ）v)≡24312312（mod pq）。

24312312^(φ（PQ）v)≡1（mod pq）。

# Checking this power explicitly.
print pow(13851252, 145604785, m)


24312312

# Break into chunks of 8 digits in length.
def chunk8(message_number):
cp = str(message_number)
ret_list = []
while len(cp) > 7:
ret_list.append(cp[:8])
cp = cp[8:]
if cp:
ret_list.append(cp)
return ret_list

msg_list = chunk8(msg_num)
print msg_list


['24312312', '15283018', '15252835', '19293018', '15273115',
'15242516', '30181529', '13191524', '131529']


# Compute ciphertexts separately on each 8-digit chunk.
def encrypt_chunks(chunked_list):
ret_list = []
for chunk in chunked_list:
#print chunk
#print int(chunk)
ret_list.append(pow(int(chunk), k, m))
return ret_list

cipher_list = encrypt_chunks(msg_list)
print cipher_list


[13851252, 14944940, 158577269, 117640431, 139757098, 25099917,
88562046, 6640362, 10543199]


# Decipher the ciphertexts all in the same way
def decrypt_chunks(chunked_list):
ret_list = []
for chunk in chunked_list:
ret_list.append(pow(int(chunk), u, m))
return ret_list

decipher_list = decrypt_chunks(cipher_list)
print decipher_list


[24312312, 15283018, 15252835, 19293018, 15273115, 15242516,
30181529, 13191524, 131529]


alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

# Collect deciphered texts into a single list, and translate back into letters.
def chunks_to_letters(chunked_list):
s = "".join([str(chunk) for chunk in chunked_list])
ret_str = ""
while s:
ret_str += alpha[int(s[:2])-11].upper()
s = s[2:]
return ret_str

print chunks_to_letters(decipher_list)


NUMBERTHEORYISTHEQUEENOFTHESCIENCES


## 为什么这种算范是安全的

x^k≡13851252(mod pq)

x^79921≡13851252(mod 163276871).

# 参考资料

A Brief Notebook on Cryptography