RSA是由三位数学家Rivest、Shamir 和 Adleman 发明的非对称加密算法，这种算法非常可靠，秘钥越长，就越难破解。

目前被破解的最长RSA秘钥是768个二进制位，长度超过768位的秘钥还无法破解，但随着计算能力的增强，以后被破解到多少位还是未知数。就目前而言，1024位的秘钥属于基本安全，2048位的秘钥属于极其安全。

RSA是一种非对称加密算法，也就是加密和解密使用的不是同一把秘钥：公钥加密-私钥解密、私钥加密-公钥解密。

RSA算法在计算机网络中被普遍应用，如：https、ssh等。

该算法还可以实现应用许可证（license），有以下几个步骤：


	
甲方构建密钥对（公钥和私钥，公钥给对方，私钥留给自己）。
	
	

	
甲方使用私钥加密许可证，然后用私钥对加密的许可证进行签名，并把这些发送给乙方。
	
	

	
乙方使用公钥、签名来验证待解密许可证是否有效（许可的来源是否有效、许可的内容是否被篡改），如果有效使用公钥对许可证解密。
	
	

	
乙方使用公钥加密数据，向甲方发送经过加密后的数据；甲方获得加密数据，通过私钥解密。
	
注意：RSA加密要求明文最大长度117字节，解密要求密文最大长度为秘钥长度除以8（1024位秘钥 / 8 = 128，2048位秘钥 / 8 = 256），所以在加密和解密的过程中需要分块进行。

Java实现RSA：

import org.apache.commons.codec.binary.Base64;
import org.apache.commons.codec.binary.Hex;
import org.apache.commons.lang3.StringUtils;

import javax.crypto.Cipher;
import java.io.ByteArrayOutputStream;
import java.security.*;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.HashMap;
import java.util.Map;


public class RSAUtil {
    private static final String KEY_ALGORITHM = "RSA";       //加密算法RSA
    private static final String SIGNATURE_ALGORITHM = "MD5withRSA";  //签名算法

    //RSA本身的限制：最大加密明文大小 = 117
    private static final int MAX_ENCRYPT_BLOCK = 117;
    //RSA本身的限制：最大解密密文大小 = keySize / 8 = 128 或 256
    private static int MAX_DECRYPT_BLOCK = 128;

    private enum KeyType {
        PUBLIC_KEY, PRIVATE_KEY
    }

    /**
     * 指定字符串生成密钥对(公钥和私钥)
     *
     * @param randomKey 加密的密码
     * @param keySize   秘钥的长度：1024 或 2048
     * @return
     * @throws Exception
     */
    public static Map<KeyType, Object> genKeyPair(String randomKey, int keySize) throws Exception {
        MAX_DECRYPT_BLOCK = keySize / 8;
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance(KEY_ALGORITHM);

        if (StringUtils.isBlank(randomKey)) {   //不指定密码
            keyPairGen.initialize(keySize);
        } else {    //指定密码
            SecureRandom random = SecureRandom.getInstance("SHA1PRNG");
            random.setSeed(randomKey.getBytes());
            keyPairGen.initialize(keySize, random);
        }

        KeyPair keyPair = keyPairGen.generateKeyPair();
        RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();
        RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();
        Map<KeyType, Object> keyMap = new HashMap<>(2);
        keyMap.put(KeyType.PUBLIC_KEY, publicKey);
        keyMap.put(KeyType.PRIVATE_KEY, privateKey);
        return keyMap;
    }

    /**
     * 用私钥对数据生成数字签名
     *
     * @param data       已加密数据
     * @param privateKey 私钥(BASE64编码)
     * @return
     * @throws Exception
     */
    public static String sign(byte[] data, String privateKey) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(privateKey);
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PrivateKey privateK = keyFactory.generatePrivate(pkcs8KeySpec);
        Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
        signature.initSign(privateK);
        signature.update(data);
        return Base64.encodeBase64String(signature.sign());
    }

    /**
     * 用公钥校验数字签名
     *
     * @param data      已加密数据
     * @param publicKey 公钥(BASE64编码)
     * @param sign      数字签名
     * @return
     * @throws Exception
     */
    public static boolean verify(byte[] data, String publicKey, String sign) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(publicKey);
        X509EncodedKeySpec keySpec = new X509EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        PublicKey publicK = keyFactory.generatePublic(keySpec);
        Signature signature = Signature.getInstance(SIGNATURE_ALGORITHM);
        signature.initVerify(publicK);
        signature.update(data);
        return signature.verify(Base64.decodeBase64(sign));
    }

    /**
     * 私钥加密
     *
     * @param data       数据
     * @param privateKey 私钥(BASE64编码)
     * @return
     * @throws Exception
     */
    public static byte[] encryptByPrivateKey(byte[] data, String privateKey) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(privateKey);
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        Key privateK = keyFactory.generatePrivate(pkcs8KeySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  //获取算法
        cipher.init(Cipher.ENCRYPT_MODE, privateK);                     //设置加密模式，并指定私钥

        // 对数据分段加密
        int inputLen = data.length;
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int offSet = 0;
        byte[] buffer;
        int i = 0;
        while (inputLen - offSet > 0) {
            if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
                buffer = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
            } else {
                buffer = cipher.doFinal(data, offSet, inputLen - offSet);
            }
            out.write(buffer, 0, buffer.length);
            i++;
            offSet = i * MAX_ENCRYPT_BLOCK;
        }
        byte[] encryptedData = out.toByteArray();
        out.close();
        return encryptedData;
    }

    /**
     * 私钥解密
     *
     * @param encryptedData 已加密数据
     * @param privateKey    私钥(BASE64编码)
     * @return
     * @throws Exception
     */
    public static byte[] decryptByPrivateKey(byte[] encryptedData, String privateKey) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(privateKey);
        PKCS8EncodedKeySpec pkcs8KeySpec = new PKCS8EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        Key privateK = keyFactory.generatePrivate(pkcs8KeySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  //获取算法
        cipher.init(Cipher.DECRYPT_MODE, privateK);                     //设置解密模式，并指定私钥

        // 对数据分段解密
        int inputLen = encryptedData.length;
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int offSet = 0;
        byte[] buffer;
        int i = 0;
        while (inputLen - offSet > 0) {
            if (inputLen - offSet > MAX_DECRYPT_BLOCK) {
                buffer = cipher.doFinal(encryptedData, offSet, MAX_DECRYPT_BLOCK);
            } else {
                buffer = cipher.doFinal(encryptedData, offSet, inputLen - offSet);
            }
            out.write(buffer, 0, buffer.length);
            i++;
            offSet = i * MAX_DECRYPT_BLOCK;
        }
        byte[] decryptedData = out.toByteArray();
        out.close();
        return decryptedData;
    }

    /**
     * 公钥加密
     *
     * @param data      数据
     * @param publicKey 公钥(BASE64编码)
     * @return
     * @throws Exception
     */
    public static byte[] encryptByPublicKey(byte[] data, String publicKey) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(publicKey);
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        Key publicK = keyFactory.generatePublic(x509KeySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  //获取算法
        cipher.init(Cipher.ENCRYPT_MODE, publicK);                      //设置加密模式，并指定公钥

        // 对数据分段加密
        int inputLen = data.length;
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int offSet = 0;
        byte[] buffer;
        int i = 0;
        while (inputLen - offSet > 0) {
            if (inputLen - offSet > MAX_ENCRYPT_BLOCK) {
                buffer = cipher.doFinal(data, offSet, MAX_ENCRYPT_BLOCK);
            } else {
                buffer = cipher.doFinal(data, offSet, inputLen - offSet);
            }
            out.write(buffer, 0, buffer.length);
            i++;
            offSet = i * MAX_ENCRYPT_BLOCK;
        }
        byte[] encryptedData = out.toByteArray();
        out.close();
        return encryptedData;
    }

    /**
     * 公钥解密
     *
     * @param encryptedData 已加密数据
     * @param publicKey     公钥(BASE64编码)
     * @return
     * @throws Exception
     */
    public static byte[] decryptByPublicKey(byte[] encryptedData, String publicKey) throws Exception {
        byte[] keyBytes = Base64.decodeBase64(publicKey);
        X509EncodedKeySpec x509KeySpec = new X509EncodedKeySpec(keyBytes);
        KeyFactory keyFactory = KeyFactory.getInstance(KEY_ALGORITHM);
        Key publicK = keyFactory.generatePublic(x509KeySpec);
        Cipher cipher = Cipher.getInstance(keyFactory.getAlgorithm());  //获取算法
        cipher.init(Cipher.DECRYPT_MODE, publicK);                      //设置解密模式，并指定公钥

        // 对数据分段解密
        int inputLen = encryptedData.length;
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        int offSet = 0;
        byte[] buffer;
        int i = 0;
        while (inputLen - offSet > 0) {
            if (inputLen - offSet > MAX_DECRYPT_BLOCK) {
                buffer = cipher.doFinal(encryptedData, offSet, MAX_DECRYPT_BLOCK);
            } else {
                buffer = cipher.doFinal(encryptedData, offSet, inputLen - offSet);
            }
            out.write(buffer, 0, buffer.length);
            i++;
            offSet = i * MAX_DECRYPT_BLOCK;
        }
        byte[] decryptedData = out.toByteArray();
        out.close();
        return decryptedData;
    }


    /**
     * 获取私钥
     *
     * @param keyMap
     * @return
     * @throws Exception
     */
    public static String getPrivateKey(Map<KeyType, Object> keyMap) {
        Key key = (Key) keyMap.get(KeyType.PRIVATE_KEY);
        return Base64.encodeBase64String(key.getEncoded());
    }

    /**
     * 获取公钥
     *
     * @param keyMap
     * @return
     * @throws Exception
     */
    public static String getPublicKey(Map<KeyType, Object> keyMap) throws Exception {
        Key key = (Key) keyMap.get(KeyType.PUBLIC_KEY);
        return Base64.encodeBase64String(key.getEncoded());
    }


    public static void main(String[] args) throws Exception {
        String password = "123456";     //加解密的密码
        int keySize = 2048;     //秘钥的长度：1024 或 2048
        Map<KeyType, Object> keyMap = RSAUtil.genKeyPair(password, keySize);
        String publicKey = RSAUtil.getPublicKey(keyMap);
        String privateKey = RSAUtil.getPrivateKey(keyMap);
        System.out.println("publicKey : " + publicKey);
        System.out.println("privateKey : " + privateKey);

        System.out.println();

        System.out.println("公钥加密 -- 私钥解密");
        String data = "RSA 非对称加密算法：公钥加密 -- 私钥解密";
        System.out.println("明文 ：" + data);
        byte[] encryptData = RSAUtil.encryptByPublicKey(data.getBytes(), publicKey);
        System.out.println("公钥加密 ：" + Hex.encodeHexString(encryptData));
        byte[] decryptData = RSAUtil.decryptByPrivateKey(encryptData, privateKey);
        System.out.println("私钥解密 ：" + new String(decryptData));

        System.out.println();

        System.out.println("私钥加密 -- 公钥解密");
        String data2 = "RSA 非对称加密算法：私钥加密 -- 公钥解密";
        System.out.println("明文 ：" + data2);
        byte[] encryptData2 = RSAUtil.encryptByPrivateKey(data2.getBytes(), privateKey);
        System.out.println("私钥加密 ：" + Hex.encodeHexString(encryptData2));
        byte[] decryptData2 = RSAUtil.decryptByPublicKey(encryptData2, publicKey);
        System.out.println("公钥解密 ：" + new String(decryptData2));

        System.out.println();

        System.out.println("私钥签名 -- 公钥验证签名");
        String sign = RSAUtil.sign(encryptData2, privateKey);
        System.out.println("私钥签名 ：" + sign);
        boolean status = RSAUtil.verify(encryptData2, publicKey, sign);
        System.out.println("公钥验证签名 ：" + status);
    }
}


 

SM2算法是一种新的国产非对称算法，相对于RSA算法，它更先进。基于国家商业密码安全等原因，国家密码管理部门正式全国范围内大力推广。
1．SM2算法简介
SM2算法与RSA算法一样，同属于非对称算法体系，是属于椭圆曲线加密（ECC）算法的一种。但与RSA算法不同的是RSA算法是基于大整数分解数学难题，SM2算法是基于椭圆曲线上点群离散对数难题。
　　相对于RSA算法，SM2算法具有以下优点：
　　安全性高。192位的SM2密码强度已经比RSA 2048位密码强度要高。
　　存储空间小。SM2算法的密码一般使用192－256位，RSA算法密码一般需要使用2048－4096位。
　　签名速度快。SM2在私钥运算上，速度远比RSA快得多。
　　国产算法。由国家密码管理部门制订规范，不存在不可公开的密码，保证无国外可利用的后门。
　　目前认为在国内被非常广泛使用的RSA 1024位算法不再安全，国家密码管理局下达了通知：自2011年7月1日起，投入运行并使用公钥密码的信息系统，应使用SM2椭圆曲线密码算法。

图的存储结构分为邻接矩阵和邻接表两种。

邻接矩阵

1. 图的邻接矩阵

图的邻接矩阵为表示图的各顶点之间关系的矩阵。

设G=(V,E)是n个顶点的图，则G的邻接矩阵用n阶方阵G表示，若(Vi ,Vj )或< Vi ,Vj >属于E(G)，则G[i][j]为1，否则为0。



通过观察图与邻接矩阵的关系，我们可以得出以下结论。

1. 无向图的邻接矩阵是对称的。因为(Vi ,Vj )属于E(G)，则 (Vj ,Vi)亦属于E(G)。

2. 从邻接矩阵容易判断任意两顶点间是否有边相联， 容易求出各顶点的度。

(1). 无向图：顶点 Vi 的度D(Vi) 等于矩阵中第 i 行 或 第 j 列元素之和。如上图G1中顶点1的度为3。

(2). 有向图：OD(Vi) 等于矩阵中第 i 行元素之和，ID(Vi) 等于矩阵中第i列元素之和。如上图中G2中顶点3的出度为0，入度为1。

 

2. 带权图(网)的邻接矩阵

设G=(V,E)是n个顶点的图，则G的邻接矩阵用n阶方阵G表示，若(Vi ,Vj )或< Vi ,Vj > 属于 E(G)，则G[i][j]为边或弧的权Wij，否则Vi与Vj间无边或弧，用 ∞ 表示。



 

3. 邻接矩阵的类型定义

const int vnum=20;
typedef struct gp{ 
    // 顶点信息
    VertexType vexs[vnum]; 
    // 邻接矩阵
    WeightType arcs[vnum][vnum]; 
    // 顶点数，边数
    int vexnum,arcnum; 
}WGraph;


 

4. 建立无向带权邻接矩阵

实现步骤如下：

(1). 将矩阵A的每个元素都初始化为最大值。

(2). 然后读入边和权值（i，j，Wij），将A的相应 元素设为Wij，算法如下：

Void CreatGraph(Graph *g){ 
    int i,j,n,e,w;
    char ch;
    scanf("%d %d",&n,&e);
    g->vexnum=n;
    g->arcnum=e;
    for (i=0;i<g->vexnum;i++){
        scanf("%c",&ch);
        g->vexs[i]=ch;
    };
    for (i=0;i<g->vexnum;i++){
        for (j=0;j<g->vexnum;j++){
            g->arcs[i][j]=MAX_INT
        }
    };
    for (k=0;k<g->arcnum;k++){
        scanf("%d %d %d",&i, &j,&w);
        g->arcs[i][j]=w;
        g->arcs[j][i]=w;
    }
}


 

邻接表

1. 邻接表的定义

邻接表是顺序存储与链式存储相结合的存储方法。

在邻接表中，对图中每个顶点建立一个单链表，每个单链表中链接图中与顶点相邻接的所有顶点。

邻接表中的每个单链表均有一个表头结点，表头结点均含有两个域 ，一个是 vertex，用于存放当前顶点的信息，另一个是firstarc，用于指向邻接表中的第一个结点。

邻接表中的每个单链表含有不等个数的表结点，表结点含有两或三个域，一个是adjvex，存放与顶点相邻接顶点的序号，另一个是nextarc，指向该顶点的下一个邻接点，带权图表结点的形式还会多一个weight表示权重。



以下是无向图的邻接表示例。

 

以下是有向图的邻接表示例，每个单链表上记录是该顶点的出度。



对于有向图，有时需要建立一个逆邻接表，记录每个顶点相关联的入度。



 

2. 邻接表的特点

(1). n个顶点、e条边的无向图，则其邻接表的表头结点数为n， 链表结点总数为2e；

(2). 对于无向图，第i个链表的结点数为顶点Vi的度；对于有向图，第i个链表的结点数为顶点Vi的出度；

(3). 在边稀疏时，邻接表比邻接矩阵省单元；

(4). 邻接表表示在检测边数方面比邻接矩阵表示效率要高。



 

3. 计算图的度

(1). 对于无向图，第i个链表的结点数为顶点Vi的度；

(2). 对于有向图，第i个链表的结点数只为顶点Vi的出度；若要求入度， 必须遍历整个邻接表。在单链表中，其邻接点域的值为i的结点个数是顶点Vi的入度。

(3). 对于有向图，有时候就要建立一个邻接表。即队每个顶点Vi建立 一个以Vi为弧头的邻接点的链表。这样，逆邻接表第i个单链表中的 结点个数就是Vi的入度。

 

4. 带权图邻接表

带权图的邻接表中的结点包含一个权重域，如下所示。



以下是带权重的无向图的表现形式。



以下是带权重的有向图的表现形式。



 

5. 邻接表的类型定义

#define vnum 20
Typedef struct arcnode{ 
    // 下一条边的顶点编号
    int adjvex; 
    // 带权图的权值域
    WeightType weight; 
    // 指向下一条边的指针
    struct arcnode *nextarc;
}ArcNode;

Typedef struct vexnode{ 
    // 顶点编号
    int vertex; 
    // 指向第一条边的指针
    ArcNode *firstarc; 
}AdjList[vnum];

Typedef struct gp{ 
    AdjList adjlist;
    // 顶点和边的个数
    int vexnum,arcnum; 
}Graph;

 

对称密码分析实验总结

首先声明以下一段文字属于个人感慨，并不十分涉及在对称密码分析上课所教授内容。仅仅在此希望给自己的年末总结！

这学期是一个比较多使用C编程的时期，感觉对于长程序有一点点自己的算法思路和个人思考。对于我们这一学科，共布置了四次作业，第一次是古典密码解密，第二次是实现BM算法，第三次是破解找到一段由线性反馈寄存器产生的序列的初始序列，第四次是破解RSA加密密文。总结以下在解决这些问题的过程中自己所感受的学习方法或者个人感想。


有实际问题后，首先需要读懂题意。了解已知信息，需要解决的问题。从各种搜索平台查看有无先人的成果和研究，这一点很重要，有时候，如果别人已经用比较完善的方法解决了问题，而我们又从零开始，并且不很好利用网络资源，最终以工作效率方面来考虑，自己已经不如别人，虽然确实是由自己实现，有更好理解。但花费的精力更多，而且倘若是长时间陷入问题，若是较为理解还可以。若很难读懂，恐怕最终的收益为零。


学会与同学或者同事共同商讨解决问题，目前有哪些进展，接下来的想法是什么。如果是比较友善的同学或者同事倒还好，若是白嫖，建议不要分享，白嫖恶心人。（虽然有时候我也白嫖）学会与人合作，倘若他人因为某一资料引发联想，建议寻求帮助。


数学原理和编程是两件事。确实可以通过数学思想编写出程序，但是两者有着区别，清楚数学原理后，整理好自己的编程思路。可先设计流程图，然后尽量简单的去编写子函数，将大函数框架粗略做出来，这样子可以对每个子函数进行测试。确保每一步子函数都能正确，编写核心函数的时候要保证自己的每一步流程有合适的注释，这样对于之后的调试和分析省了不少力气。长此以往，规范化编程对于自己的自信心有很大的照顾。


倘若在编程中没有合适的思路，建议放下此题去做其他的事，闲暇时候想想有没有思考到其他的点子。不管怎么样，只是用一种思路去考虑问题是很难把事情做到最好，但是生活是复杂的，复杂到什么时候该坚持什么时候需要转换思路，这是难处。感觉可行，一步步向下做，如果某一步做不下去，跳出这步做下一步。如果发现只有这一关卡，建议继续坚持。若是有一个地方卡住脑袋，而后该怎么做没有头绪，那不如直接换一个思路，大多数时候，一个问题不止一个解决方案，适合自己才最佳。


坚持不懈对生活思考，这个问题怎么解决，有没有其他的解决方式，我要怎么去更好的解决它。只有对生活保持热情，才能坚持热爱自己的事业。


放松生活，总会有你做不出来的题目，反思自己哪里做到的不足，然后慢慢进步，反思过程不可少，之后有时间的时候把之间做的事情回顾一遍，整理复盘。发布博客帮助其他人。


要说的也就这么多了，我希望以后能变成一个自己想成为的人！