密码学原理

密码学是现代计算机安全通信的基石，早已在日常生活中被广泛应用。现代密码学的基层支撑是数学，而且还和信息论密切相关。恰巧最近看的吴军博士的《数学之美》中第17章也提到了密码学，因此鄙人打算将此篇当作一个读书笔记来写。

一. 密码学的历史

关于密码学的历史，最早大致可以追溯到古罗马时期。古罗马皇帝凯撒 (Julius Caesar) 为了防止敌方截获情报，采用密码传送情报。其做法很简单，就是给二十来个罗马字母建立一张对应表，大致如下：

Code

明码        密码
-----------------
 A           B
 B           E
 C           A
 D           F
 ...         ...
 R           P
 S           T
 ...         ...

这样一一对应之后，如果不知道密码本，即使截获一段信息，由于是加过密之后的乱码，敌人也会不得其解，可以说是实现了加密的目的。（如看上去毫无意义的 ABKTBP 经过解密后可得其实就是 CAESAR 一词）这种密码本一一对应的编码方法，史称 “凯撒大帝”。但是这种加密方式的安全与否，一方面取决于密码本保存的是否安全。另一方面，即使在不知道密码本的情况下，通过统计单词字母的出现频率（如高频词在经过密码本加密之后所对应的形式，出现的次数也一定是高频的）也可以推断出明文。因此，密码的设计者们开始逐渐地意识到，对于一种好的编码方式，破译者应该无法从密码中统计出明码的规律。更进一步的讲，什么才算是好的密码？好的密码要求必须做到根据已知的明文和密文的对应无法推断出新的密文内容。从数学的角度看，加解密的过程类似于这样：

Code

graph LR

明码 --> | 加密| 密码
密码 --> | 解密| 明码

加密的过程可以看作是一个函数运算 F, 解密的过程是含函数的运算。明码是自变量，密码就是函数的输出结果，也就是函数值。好的函数不应该通过几个自变量和函数值就能推出函数本身。这一点在二战及其之前做得很不好。比如美国就多次在二战中破译了日本军方的密码电报，并成功地在中途岛海战中伏击了日本联合舰队。

二. 信息论时代的密码学

二战期间，很多当时的顶级科学家如香农 (Sharon)、图灵 (Turing) 都参与到了军方的情报加解密工作当中。香农负责研究如何为英国首相丘吉尔和美国的通话加密，而图灵则主要研究如何解密德国人的密码机。在这个研究过程当中，香农提出了信息论，而信息论可以说是现代通信的理论基石了。信息论的提出给密码学的发展前进带来了新气象。根据信息论，密码的最高境界是敌方在截获密码之后，对我方的所知没有任何增加，用专业术语来说，就是其对我方所拥有的信息量没有增加。因为信息论的出现，现代密码的设计就有了理论基础。现如今通用的公开密钥的方法（即非对称加密，公钥和私钥是不同且配对出现，公钥公开，私钥不公开，用公钥加密的密文只有用私钥才能解开。与之相应的还有对称加密，对称加密采用相同的公钥和私钥）及其电子签名是今天大多数互联网安全协议的基础。

公开公钥的加密方法有很多，下面就用相对简单的 RSA 算法来描述非对称加密的原理。

假设此刻的明文为 X = 067097101115097114 （‘Caesar ’ 对应的 ASCII码串）

非对称加密的基本步骤：

找两大很大的素数（很大的意思是最好有上百位）P 和 Q , 计算它们的乘积得：N = P * Q
再计算 M = (P-1)(Q-1) 得到 M
找一个和 M 互素的整数 E，再找一个整数 D，使得 E * D mod M = 1

经过上述几步，就有了一个先进且最常用的密码系统了。其中呢， E 是公钥，是对外公开的，谁都可以保存。 D 是用于解密私钥，只能有解密方好好保存。联系公钥和私钥的乘积 N 也是公开的，就算被人知道了也没关系。

采用下面的公式
$$
X^E mod {N} = Y
$$
对 X 加密，得到密文 Y. 现在没有了私钥 D，神仙也没有办法从 Y 中得到 X. 如果知道了私钥 D，则根据费马小定理按照下列公式
$$
Y^D mod {N} = X
$$
就可以从 Y 中得到原来的 X.

通过一些简单的乘除运算，就可以得到目前来看最为可靠的安全加密方式，这不正好是将 “数学之美” 体现得淋漓尽致吗？

那么这样的密文破解起来有多难呢？首先说明世界上没有破解不了的密码，关键是看这个破解要花费多长时间，也就是密码的有效期。如果一个密码经历一百年都破解不出来，那我们完全可以说这个密码对于个人而言是绝对安全的，毕竟真没有几个人能活这么长时间。密码的有效期靠什么来保证呢？靠的是大数的因式分解的困难程度。至今的研究结果表明，要破解这样的加密最彻底的办法还是对大数 N 进行因式分解来求得 P 和 Q. 只要把这俩找到了，这密码就算成功破解了。而找 P 和 Q 目前所能采用的依然只有穷举法这一种。这实际上考验的就是计算机的计算能力，这也是为什么在选择 P 和 Q 时要求这俩数的长度要特别长的原因所在。对于 RSA 来说，就目前的情况来看，512位的密钥被视为不安全的，768位的密钥不用担心受到除了国家安全管理（NSA）外的其他事物的危害，1024位的密钥则几乎是安全的。

三. Java 代码实现

日常开发中常用的 RSA 加密方式 Java 代码

java

public class RSATest {

    private static KeyPair keyPair;

    static {
        try {
            keyPair = generateKeyPair();
        } catch (NoSuchAlgorithmException e) {
            System.err.println(e.getMessage());
        }
    }

    public static void main(String[] args) throws GeneralSecurityException {

        String plainText = "helloWorld";
        String encrypted = rsaEncrypt(plainText);
        System.out.println(encrypted);
        String decrypted = rsaDecrypt(encrypted);
        System.out.println(decrypted);
        System.out.println(plainText.equals(decrypted));	// it will output "true"

    }

    public static String rsaEncrypt(String plainText) throws GeneralSecurityException {
        PublicKey publicKey = keyPair.getPublic();
        X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(publicKey.getEncoded());
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        Key pubkey = keyFactory.generatePublic(x509EncodedKeySpec);

        // 公钥加密数据
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.ENCRYPT_MODE, pubkey);
        byte[] encryptData = cipher.doFinal(plainText.getBytes(StandardCharsets.UTF_8));
        return getBas64Encoder().encodeToString(encryptData);
    }

    public static String rsaDecrypt(String encryptText) throws GeneralSecurityException {
        PrivateKey privateKey = keyPair.getPrivate();
        PKCS8EncodedKeySpec pkcs8EncodedKeySpec = new PKCS8EncodedKeySpec(privateKey.getEncoded());
        byte[] encrypted = getBas64Decoder().decode(encryptText.getBytes(StandardCharsets.UTF_8));
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        Key prikey = keyFactory.generatePrivate(pkcs8EncodedKeySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());
        cipher.init(Cipher.DECRYPT_MODE, prikey);
        return new String(cipher.doFinal(encrypted));
    }

    private static KeyPair generateKeyPair() throws NoSuchAlgorithmException {
        KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("RSA");
        keyPairGenerator.initialize(1024);
        KeyPair keyPair = keyPairGenerator.generateKeyPair();
        return keyPair;

    }

    private static  Base64.Decoder getBas64Decoder() {
        return Base64.getDecoder();
    }

    private static  Base64.Encoder getBas64Encoder() {
        return Base64.getEncoder();
    }
}