Crypto的第一步

摘要：嘛，既然开始学密码了，就还是记录一下自己的学习历程，这样也会有意思一些，希望自己能够做到一周写两次自己的学习进度吧，今天先来第一步什么叫密码学哦。

嘛，既然开始学密码了，就还是记录一下自己的学习历程，这样也会有意思一些，希望自己能够做到一周写两次自己的学习进度吧，今天先来第一步：什么叫密码学哦。

最近和教授讨论研究的方向，很烦，因为我才刚刚入学，信息安全方面的论文要说完整读下来的基本还没有，所以慢慢积累吧，最近在读的[1]基本也是卡在了经典的homomorphic Encrytion--Paillier加密上。没办法，数学基础比较堪忧，老师和我商量后也是基本定在做同态密码了，所以，慢慢啃吧。

啊，扯远了，首先开始写写什么叫密码学吧，然后在举个栗子。

Cryptography or cryptology (from Greek κρυπτός kryptós, "hidden, secret"; and γράφειν graphein, "writing", or -λογία -logia, "study", respectively[1]) is the practice and study of techniques for secure communication in the presence of third parties called adversaries.[2] More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages;[3] various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation[4] are central to modern cryptography. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, and electrical engineering. Applications of cryptography include ATM cards, computer passwords, and electronic commerce.[2]

意思基本就是两层：1，密码学的基本目标就是：保护两个人的通讯不会被第三方所攻击，即使被第三方截获通讯消息（密文）他也无法获取原始消息（明文）。2.现代密码学用处很大什么地方都在用。

上面说的现代密码学，既然有现代密码学自然有古典密码学咯~ 事实上古典密码学基本是不需要数学基础的是一些很简单很纯粹的想法，但是可以非常直观的展现什么是密码，作为启发。

那么要说最经典的当然是凯撒密码啦，具体名字咋来的我懒得去找了，大概就是这么个意思，见下图：

出处：http://invpy.com/cipherwheel
选定一个秘钥k∈[0,25]且为Z，然后去转动这个罗盘，将外层的A转到你选定的K值上，将原文（M）的每一个字母由外层字母映射到内层字母。
栗子如下：
if key = 8：

[3]
上面是原文M，下面是译文（E），于是我们把密文发送出去：BPM AMKZMB XIAAEWZL QA ZWAMJCL 并附上Key = 8。 收到的人只要再拿出这个罗盘，对准A，将内存字母映射到外层字母即可解密了。

当然，非常简单，当然，也很愚蠢。 因为秘钥只有26个，穷举也能破解，更不用说更高端的手段了。

嘛，顺手附上一个python读文件加解密的代码：

# -*- coding: utf-8 -*-
# __author__ = "summer"

dictionary = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]


def ceaserCipher(i_str, key, mode="encrypt"):
    o_str = ""
    if mode == "decrypt":
        key = 0 - key
    for i in xrange(len(i_str)):
        if i_str[i] in dictionary:
            index = (dictionary.index(i_str[i]) + key) % 26
            o_str += dictionary[index]
        else:
            if i_str[i].isupper():
                index = (dictionary.index(i_str[i].lower()) + key) % 26
                o_str += dictionary[index].upper()
            else:
                o_str += i_str[i]
    return o_str

def encryptFromText(filepath, filename, key=0):
    bufferstr = b""
    with open(filepath + filename, "rb") as f:
        for line in f.readlines():
            bufferstr += line
    o_str = ceaserCipher(bufferstr, key)
    with open(filepath + "encrypted " + filename, "w") as f_out:
        f_out.writelines(o_str)

def decryptFromText(filepath, filename, key=0):
    bufferstr = b""
    with open(filepath + filename, "rb") as f:
        for line in f.readlines():
            bufferstr += line
    o_str = ceaserCipher(bufferstr, key, "decrypt")
    with open(filepath + "decrypted " + filename, "w") as f_out:
        f_out.writelines(o_str)

所以呢，通过这个例子，我们可以数学上的来定义一个cipher system：

Def：a cipher defined over(K,M,C)(all sets of Keys/Messages/Ciphertext) is a pair of "efficient" algorithm (E,D) where:E => Encrypt algo. :K M -> C ,D => Decrypt algo. :K C -> M
s.t. for all m∈M，k∈K：D(k,E(k,m)) = m

且一般情况下E是一个随机算法（Randomized algo.），D是一个确定算法（Deterministic algo.）

当然，密码体系是否安全，这些概念以及具体的数学定义以后再写。原谅我懒得去弄TeX写数学符号了，很累的！

上面说了，凯撒加密有个大问题在于秘钥数量太少即|K|=26... 专业的说就是秘钥空间太小，那么古典密码学上有一种叫做transposition Encrypt，他扩大了秘钥空间。
具体的方案：
我们选定一个信息比如：“Common sense is not so common.”
选定一个任意整数的秘钥k，比如k = 8
然后我们确定出k个格子

这个样子，然后往里面依照信息的字母往格子里填字母：

依次往后推如图的感觉。注：（s）表示空格space
然后，我们竖着来输出密文C：
“Cenoonommstmme oo snnio. s s c”

就这样，加密成功了！那么解密呢，一样是建立这样的格子，然后竖着往里面填密文，横向输出就OK了呗。实现起来也很简单，无非就是个数组的嵌套罢了数组里面扔数组。

代码凑合看吧没仔细斟酌：

# -*- coding: utf-8 -*-
# __author__ = "summer"
def main():
    myMessage = "We shade in the two boxes in the last row to remind us to ignore them."
    myKey = 8
    ciphertext = encryptMessage(myKey, myMessage)
    print ciphertext
    print decryptMessage(myKey, ciphertext)

def encryptMessage(key, message):
    o_arr = []
    for i in xrange(key):
        index = 0 + i
        while index < len(message):
            o_arr.append(message[index])
            index += key
    return "".join(o_arr)

def decryptMessage(key, message):
    o_arr = []
    row = len(message) / key + 1
    last_row = len(message) % key
    if last_row == 0:
        last_row = key
    for i in xrange(row):
        index = 0 + i
        flag = 0
        isLastRow = False
        if index == row - 1:
            isLastRow = True
        while index < len(message):
            flag += 1
            if isLastRow and flag > last_row:
                break
            o_arr.append(message[index])
            if flag <= last_row:
                index += row
            else:
                index += (row - 1)
    return "".join(o_arr)

if __name__ == "__main__":
    main()

明显解密比较麻烦主要就是难在最后的空格的问题，怎么去竖着填格子。有兴趣的可以去leetcode看看zigzag的那道题，意思差不多。

嘛，这种加密方法看上去把秘钥空间扩充为了无穷！乍一看好厉害，但是你计算能力有极限，我当然穷举也能破解啦。当然这个算法有很多改良比如打乱密码输出顺序之类的，不过攻击方法大同小异，经不起穷解攻击。

当然还有一些比较有意思的比如字母频率攻击Monoalphabetic Encryption啊之类的有兴趣的可以去查查（虽然基本也就是科普作用可以当故事来看啦嗯哼）

OK今天就写到这里，有遗漏错误之处也希望有大牛能够一击毙命点醒我啊我也还是个刚入门的孩子hohoho，下次准备写一写信息论与密码安全。

[1]Atallah M J, Frikken K B, Blanton M, et al. Private combinatorial group testing[C]//Proceedings of the 2008 ACM symposium on Information, computer and communications security. ACM, 2008: 312-320.
[2]Wikipedia,keyword:Cryptography
[3]Al Sweigart, Hacking Secret Ciphers with Python