精华内容
参与话题
问答
  • 密码学:RSA加密算法详解

    万次阅读 多人点赞 2016-02-29 18:03:37
    RSA算法一直是最广为使用的"非对称加密算法"。本文旨在说明RSA加密算法的原理及实现,而其相关的数学部分的证明则不是本文内容。

    概述

      本文旨在说明RSA加密算法的原理及实现,而其相关的数学部分的证明则不是本文内容。


    版权说明

    著作权归作者所有。

    商业转载请联系作者获得授权,非商业转载请注明出处。

    作者:Q-WHai

    发表日期: 2016年2月29日

    本文链接:http://blog.csdn.net/lemon_tree12138/article/details/50696926

    来源:CSDN

    更多内容:分类 » 数据加密与信息安全


    RSA简介

      1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

                                                                                       -- 摘自网络


    数学背景

      此部分旨在补充本文的完整性。如果说你已经了解,或是不想了解此部分内容。那么可以直接跳过此部分的阅读。

      虽说只是补充说明(只能是补充的原因是因为博主的数学也是比较差的-_-!!!),但是此部分的内容却是相当重要的。博主还是希望可以重新阅读一下此部分。

    1.互质

      从小学开始,我们就了解了什么是质数。互质是针对多个数字而言的,如果两个正整数,除了1以外,没有其他公因子,那么就称这两个数是互质关系(注意,这里并没有说这两个数一定是质数或有一个为质数。比如15跟4就是互质关系)。以下有一些关于质数与互质的性质:

    • 质数只能被1和它自身整除
    • 任意两个质数都是互质关系
    • 如果两个数之中,较大的那个数是质数,则两者构成互质关系
    • 如果两个数之中,较小的那个数是质数,且较大数不为较小数的整数倍,则两者构成互质关系
    • 1和任意一个自然数是都是互质关系
    • p是大于1的整数,则p和p-1构成互质关系
    • p是大于1的奇数,则p和p-2构成互质关系

    2.欧拉函数

      欧拉函数是求小于x并且和x互质的数的个数。其通式为:φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)

      其中p1, p2……pn为x的所有质因数,x是不为0的整数。看到这里是不是有一些头疼,太理论的东西的确不够具象。我们且不去理会后面公式计算与论证,因为已经超出本文的范围了。就前一句来说说吧,欧拉函数是求小于x并且和x互质的数的个数。这里我可以列举一个例子:

      令x = 16,那么x的所有质因数为:φ(16) = 16 * (1 - 1/2) = 8

      我们也可以枚举出所有比16小,且与16互质的数:1, 3, 5, 7, 9, 11, 13, 15

      现在也给出部分欧拉函数的性质:

    • 若n是素数p的k次幂,,因为除了p的倍数外,其他数都跟n互质
    • 欧拉函数是积性函数——若m,n互质,
    • 当n为奇数时,
    • p是素数,,φ(p)称为p的欧拉值

      欧拉函数更多参考请见这里的链接


    3.模反元素

    定义:如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

    关于模反元素的求解,使用的是朴素的解法。如果读者想要更进一步了解的话,请自行搜索其他解法(比如:辗转相除法、欧几里德算法)。


    RSA原理

      在RSA原理之前,我想还是有必要了解一下非对称加密算法的加密跟解密过程。下面就是一幅非称加密算法的流程图。

      

      在此可以看到,非对称加密是通过两个密钥(公钥-私钥)来实现对数据的加密和解密的。公钥用于加密,私钥用于解密。对于非对称的加密和解密为什么可以使用不同的密钥来进行,这些都是数学上的问题了。不同的非对称加密算法也会应用到不同的数学知识。上面也对RSA中使用的数学问题做了一个小小的介绍。现在就来看看RSA算法是怎么来对数据进行加密的吧,如下是一幅RSA加密算法流程及加密过程图。

      


    RSA应用

    1. 实例模型

      就以上图中的Bob和Alice来举例吧。

      现在Alice通过密钥生成器生成了一对密钥(公钥-私钥)。只把公钥对外公开了。并说,你有什么要跟我说的,就用模幂运算和公钥加密后发给我吧。

      此时,Bob已经获得了Alice发布的公钥。使用模幂运算对明文进行了加密,就把加密后的密文发送给了Alice。

      Alice获得Bob发来的密文并没有使用公钥对密文进行解密,并获得了明文。因为解密过程需要使用的密钥是私钥。


    2. RSA算法实现

      下面的代码只是根据RSA算法的定义,使用Java开发语言实现。且这里只是展示了一些关键步骤,完整过程可以参见下面的源码下载文档。

    public class RSA {    
        /**
         * 获得(公/私)密钥
         */
        public final Map<String, RSAKey> getCipherKeys() {
            ...
            int[] primes = getRandomPrimes(2);
            int modulus = modulus(primes[0], primes[1]);
            int euler = euler(primes[0], primes[1]);
            int e = cipherExponent(euler);
            int inverse = inverse(euler, e);
            publicKey.setExponent(e);
            publicKey.setModulus(modulus);
            privateKey.setExponent(inverse);
            privateKey.setModulus(modulus);
            ...
        }
        
        /**
         * 加密
         */
        public int encode(int plaintext, RSAPublicKey key) {
            return modularPower2(plaintext, key.getExponent(), key.getModulus());
        }
        
        /**
         * 解密
         */
        public int decode(int chipertext, RSAPrivateKey key) {
            return modularPower2(chipertext, key.getExponent(), key.getModulus());
        }
    
        // 随机生成count个素数
        private final int[] getRandomPrimes(int count) {
            ...
            try {
                primeLabels = FileReadUtils.readLines("./data/prime_table");
            } catch (IOException e) {
                e.printStackTrace();
            }
            for (int i = 0; i < primes.length; i++) {
                primes[i] = Integer.parseInt(primeLabels.get(indexs.get(i)));
            }
    
            return primes;
        }
    
        // 计算公共模数
        private final int modulus(int p, int q) {
            return p * q;
        }
    
        // 计算欧拉数
        private final int euler(int p, int q) {
            return (p - 1) * (q - 1);
        }
    
        // 计算加密指数
        private final int cipherExponent(int euler) {
            Random random = new Random();
    
            int e = 7;
            do {
                e = random.nextInt(euler - 1);
            } while (!isCoprime(e, euler) || e <= 1);
    
            return e;
        }
    
        // 判断两个数互素
        private final boolean isCoprime(int number1, int number2) {
    
            int sqrt = (int) Math.sqrt(Math.max(number1, number2));
            for (int i = 2; i <= sqrt; i++) {
                if (number1 % i == 0 && number2 % 2 == 0) {
                    return false;
                }
            }
    
            return true;
        }
    
        // 计算“模的逆元”
        // (d * e) ≡ 1 mod euler
        private final int inverse(int euler, int e) {
            ...
            while (flag) {
                q = m[2] / n[2];
                for (int i = 0; i < 3; i++) {
                    temp[i] = m[i] - q * n[i];
                    m[i] = n[i];
                    n[i] = temp[i];
                }
                if (n[2] == 1) {
                    if (n[1] < 0) {
                        n[1] = n[1] + euler;
                    }
                    return n[1];
                }
                if (n[2] == 0) {
                    flag = false;
                }
            }
            return 0;
        }
        
        // 模幂运算
        private final int modularPower(int base, int e, int modular) {
            int result = 1;
            do {
                if (isOdd(e)) {
                    result = (result * (base % modular)) % modular;
                    e -= 1;
                } else {
                    base = (base * base) % modular;
                    e /= 2;
                }
            } while (e > 0);
            
            result %= modular;
            
            return result;
        }
    }

    RSA算法判别

    RSA算法优点

    1. 不需要进行密钥传递,提高了安全性
    2. 可以进行数字签名认证

    RSA算法缺点

    1. 加密解密效率不高,一般只适用于处理小量数据(如:密钥)
    2. 容易遭受小指数攻击


    Ref

    1. 《算法导论》
    2. 《算法的乐趣》
    3. 《深入浅出密码学》
    4. RSA算法原理(一) -- 阮一峰
    5. RSA算法原理(二) -- 阮一峰
    6. 逆元详解 -- ACdreamers
    7. JAVA实现扩展欧几里德算法求乘法逆元


    源码下载

    http://download.csdn.net/detail/u013761665/9439852

    展开全文
  • RSA加密与解密(Java实现)

    万次阅读 多人点赞 2018-10-17 10:22:52
    现在,很多登陆表单的密码的都采用RSA加密,例如京东中的登陆使用公钥对密码进行加密。 Base64编码 apache.commons-codex包提供了许多编码格式转换,例如Base64。 以下为Base64编码表 使用apache.commons-...

    本文作者:合肥工业大学 管理学院 钱洋 email:1563178220@qq.com 内容可能有不到之处,欢迎交流。

    未经本人允许禁止转载。

    RSA的应用

    RSA是一种非对称加密算法。现在,很多登陆表单的密码的都采用RSA加密,例如京东中的登陆使用公钥对密码进行加密。
    在这里插入图片描述

    Base64编码

    apache.commons-codex包提供了许多编码格式转换,例如Base64。

    以下为Base64编码表在这里插入图片描述
    使用apache.commons-codex进行Base64对字符串进行编码与解码的程序如下:

    package com.qian.encoded;
    
    import org.apache.commons.codec.binary.Base64;
    
    public class Base64Coded {
    	public static void main(String[] args) {
    		String string = "qianyang123";
    		//编码
    		String encode = encode(string.getBytes());
    		System.out.println(string + "\t编码后的字符串为:" + encode);
    		//解码
    		String decode = decode(encode.getBytes());
    		System.out.println(encode + "\t字符串解码后为:" + decode);
    	}
    	//base64 解码
        public static String decode(byte[] bytes) {  
            return new String(Base64.decodeBase64(bytes));  
        }  
      
        //base64 编码
        public static String encode(byte[] bytes) {  
            return new String(Base64.encodeBase64(bytes));  
        }  
    }
    
    
    

    程序的输出结果为:

    qianyang123 编码后的字符串为:cWlhbnlhbmcxMjM=
    cWlhbnlhbmcxMjM= 字符串解码后为:qianyang123

    RSA加密与解密

    使用RSA一般需要产生公钥和私钥,当采用公钥加密时,使用私钥解密;采用私钥加密时,使用公钥解密。以下为Java程序:

    package com.qian.encoded;
    
    import org.apache.commons.codec.binary.Base64;
    import javax.crypto.Cipher;
    import java.security.KeyFactory;
    import java.security.KeyPair;
    import java.security.KeyPairGenerator;
    import java.security.NoSuchAlgorithmException;
    import java.security.SecureRandom;
    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 RSAEncrypt {
    	private static Map<Integer, String> keyMap = new HashMap<Integer, String>();  //用于封装随机产生的公钥与私钥
    	public static void main(String[] args) throws Exception {
    		//生成公钥和私钥
    		genKeyPair();
    		//加密字符串
    		String message = "df723820";
    		System.out.println("随机生成的公钥为:" + keyMap.get(0));
    		System.out.println("随机生成的私钥为:" + keyMap.get(1));
    		String messageEn = encrypt(message,keyMap.get(0));
    		System.out.println(message + "\t加密后的字符串为:" + messageEn);
    		String messageDe = decrypt(messageEn,keyMap.get(1));
    		System.out.println("还原后的字符串为:" + messageDe);
    	}
    
    	/** 
    	 * 随机生成密钥对 
    	 * @throws NoSuchAlgorithmException 
    	 */  
    	public static void genKeyPair() throws NoSuchAlgorithmException {  
    		// KeyPairGenerator类用于生成公钥和私钥对,基于RSA算法生成对象  
    		KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");  
    		// 初始化密钥对生成器,密钥大小为96-1024位  
    		keyPairGen.initialize(1024,new SecureRandom());  
    		// 生成一个密钥对,保存在keyPair中  
    		KeyPair keyPair = keyPairGen.generateKeyPair();  
    		RSAPrivateKey privateKey = (RSAPrivateKey) keyPair.getPrivate();   // 得到私钥  
    		RSAPublicKey publicKey = (RSAPublicKey) keyPair.getPublic();  // 得到公钥  
    		String publicKeyString = new String(Base64.encodeBase64(publicKey.getEncoded()));  
    		// 得到私钥字符串  
    		String privateKeyString = new String(Base64.encodeBase64((privateKey.getEncoded())));  
    		// 将公钥和私钥保存到Map
    		keyMap.put(0,publicKeyString);  //0表示公钥
    		keyMap.put(1,privateKeyString);  //1表示私钥
    	}  
    	/** 
    	 * RSA公钥加密 
    	 *  
    	 * @param str 
    	 *            加密字符串
    	 * @param publicKey 
    	 *            公钥 
    	 * @return 密文 
    	 * @throws Exception 
    	 *             加密过程中的异常信息 
    	 */  
    	public static String encrypt( String str, String publicKey ) throws Exception{
    		//base64编码的公钥
    		byte[] decoded = Base64.decodeBase64(publicKey);
    		RSAPublicKey pubKey = (RSAPublicKey) KeyFactory.getInstance("RSA").generatePublic(new X509EncodedKeySpec(decoded));
    		//RSA加密
    		Cipher cipher = Cipher.getInstance("RSA");
    		cipher.init(Cipher.ENCRYPT_MODE, pubKey);
    		String outStr = Base64.encodeBase64String(cipher.doFinal(str.getBytes("UTF-8")));
    		return outStr;
    	}
    
    	/** 
    	 * RSA私钥解密
    	 *  
    	 * @param str 
    	 *            加密字符串
    	 * @param privateKey 
    	 *            私钥 
    	 * @return 铭文
    	 * @throws Exception 
    	 *             解密过程中的异常信息 
    	 */  
    	public static String decrypt(String str, String privateKey) throws Exception{
    		//64位解码加密后的字符串
    		byte[] inputByte = Base64.decodeBase64(str.getBytes("UTF-8"));
    		//base64编码的私钥
    		byte[] decoded = Base64.decodeBase64(privateKey);  
            RSAPrivateKey priKey = (RSAPrivateKey) KeyFactory.getInstance("RSA").generatePrivate(new PKCS8EncodedKeySpec(decoded));  
    		//RSA解密
    		Cipher cipher = Cipher.getInstance("RSA");
    		cipher.init(Cipher.DECRYPT_MODE, priKey);
    		String outStr = new String(cipher.doFinal(inputByte));
    		return outStr;
    	}
    
    }
    
    

    在程序中,我们首先利用genKeyPair()函数生成公钥和私钥并将其保存到Map集合中。然后,基于产生的公钥对明文进行加密。针对已经已经加密的密文,我们再次使用私钥解密,得到明文。
    上述程序的输出结果为:

    随机生成的公钥为:MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCG77PYUAcCpANyUmsHJfuDIia9FcITsuu9lnfbE2BbEwd4SOxPBFTwEWTZ9/e+mtjP97KFEBohGkwy+VHE5KocypBv0O7YgEevwMgpvxyYY0v104CB/k0yjCFV7lc7FxY5VgEKrMiXTIkMr1ukCnWVvapvRCS6IFcsT/kkjPgfDQIDAQAB
    随机生成的私钥为:MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBAIbvs9hQBwKkA3JSawcl+4MiJr0VwhOy672Wd9sTYFsTB3hI7E8EVPARZNn3976a2M/3soUQGiEaTDL5UcTkqhzKkG/Q7tiAR6/AyCm/HJhjS/XTgIH+TTKMIVXuVzsXFjlWAQqsyJdMiQyvW6QKdZW9qm9EJLogVyxP+SSM+B8NAgMBAAECgYEAhj0FH9dNghUE0MCpdS0WL/jTrRxuPQase6mrhyiZnUErF0EExf87OLE1MZr8voRx2UNEOBgyxmfREozyCfyqNg1OdGYEHSyuJ9wglkhq8GVYO8IzI29Mqej0MSprtsE0BPAKBHRU/DWP19ej5bv5ZnAhLs10K7uVEsuGwJJYcMECQQDibedUr7tnGfojyjFY0vCAaVwgS0vXfno7WQyAXUz0Fv8Uy1q9nyF0RrkeA8BOk7S4ljE77ufX0rr2qL7kHW8pAkEAmI718EnQCKKJUjrQUl4iG/lYoNwW2QnxTGZmESyFwkS95PTt8K4GVHpICqRNP1JJBNxVSEVts/eA4zrxPAoBRQJBAJxxEsOQJwq1B/5yVGXqWABgyyYE4AGjgRBAFkMaM3Dx8ouLdMZOi+6qbnwuW0/u/Y4LNzkRd13GWybQsBMrwwECQEULptmavpG55kaWIcS1n+BjSK59DcYrDs+SJK2vJdaXwA4IoEvmpyzCrypJ1EBNYIjXo61y5sSlxuqQua9/o7UCQGYdM3/mF/FEC3wxdfQq0Pw/Pwn8RQxg1natRfoTyzOJDfE/YUYGjIEe2pQtDI1s+IRCwrXOB0cySbpaSHCjr5U=
    df723820 加密后的字符串为:HRMm2XsytNJjmnZgn+2pFZWyTn56tsp7/yII6jdo3Wb19uy8GFtFujMekcUWqwFsO9vbvUOyD21MgI85BOtD7tsHHlj5xdtPiFEHkY1qiWIHTPpxA+WICSlw9ZY4zY0IaoxhrMAb8c9ohsrbBbyGcmUSFFdZq8CuPfj99IDLLic=
    还原后的字符串为:df723820

    展开全文
  • RSA加密

    千次阅读 2019-06-27 11:56:11
    三、RSA加密 四、OpenSSL使用 一、概述 RSA是一种非对称加密算法,1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的,因此以三人姓氏的首字母...

    一、概述
    二、对称加密
    三、RSA加密
    四、OpenSSL使用

    一、概述

    RSA是一种非对称加密算法,1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的,因此以三人姓氏的首字母命名了该非对称加密算法,RSA算法。

    提到非对称加密,下面简单看一下对称加密流程:

    二、对称加密

    先举个栗子:
    1、天王盖地虎对宝塔镇河妖,我们都知道,所以你给我发天王盖地虎,我就翻译成宝塔镇河妖。因此对称加密也可以说是秘密交易者的暗号;

    2、战争片中的电报,发送方和接收方都有一个密码本,每一个字母都有与之对应的密文,发送时对照密码本发送密文,接收时拿密文在密码本上进行比对;

    3、开发中如同我告诉接收方我给你的数据都是用base64加密的,那么接收方就可以采用base64解密。

    综上所知,消息发送方与接收方均知道对数据的处理方式,那么我们称这种处理方式方法为秘钥(key),也就是上面暗号的上下句,密码本,base64。对数据加密解密都是由一个秘钥(key)来处理,消息发送端和消息接收端同时存有秘钥(key),因此也称之为单秘钥加密。第三方可以通过归纳总结或强行获取秘钥(key),如果第三方拿到了秘钥(key)那么消息也就会被第三方获取,所以对称加密安全性一般,适用与一般数据加密。如下图:

    symmetric.png

    三、RSA加密

    RSA非对称加密存在大量的取模运算,加密速度慢,只适用于对小数据量加密,所有在应用中经常结合对称加密使用,对对称加密的私钥进行加密。非对称加密应用有支付宝,微信等支付做签名验证,苹果开发证书签名等。
    欧拉函数
    在数论中,存在正整数 n,小于n并且与n互质的正整数的数目称为n的欧拉函数记着φ(n)。例如:
    φ(7) 7对应的比7小的与7互质的数有1、2、3、4、5、6共6个,因此φ(7)=6
    φ(8) 8对应的比8小的与8互质的数有1,3,5,7共4个,因此φ(8)=4
    φ(9) 9对应的比9小的与9互质的数有1,2,4,5,6,7,8共7个,,因此φ(9)=7

    **互质:**除了1没有其他公因数的两个整数,称为互质整数。
    通式:φ(x)=x∏(1-1/pi) 1=<x<n。(p1~pnx的所有质因数)
    m n互质:φ(n * m)=φ(n)* φ(m),如果n为质数那么φ(n)=n-1
    分解质因数求值:φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4

    欧拉定理
    如果两个正整数mn互质,那么mφ(n) 次方对n取余衡等于1m^φ(n)%n≡1

    费马小定理
    存在一个质数p,而整数a不是p的倍数,则存在a^(p-1)%p≡1。费马小定理是欧拉定理的特殊情况。因为φ(p)=p-1(任何数都与质数互质)。

    模反元素
    如果两个正整数ex互质,那么一定存在一个整数d,使得ed-1能够被x整除,则称dex的模反元素。e * d % x≡1,那么e * d ≡ k*x+1

    由以上定理得出以下几个公式:
    1、m^φ(n)%n≡1
    2、m^(k * φ(n))%n≡1 两端同乘以m
    3、m^(k * φ(n)+1)%n≡m
    4、e * d≡k * x+1
    5、m^e * d%n≡m 替换第3步k * φ(n)+1

    m^e*d%n≡m就是我们需要的一个非对称加密的公式。m为明文,ed分别对应的是公钥私钥。迪菲卡尔曼秘钥交换对公式拆分:
    m^e%n=c 加密
    c^d%n=m 解密
    其中c为通过e加密后的密文,然后通过d可以解出明文m。因此:
    公钥: en
    秘钥:dn
    明文:m
    密文:c

    RSA加密过程
    1、取两个质数p1p2
    2、确定n值,n=p1 * p2n值一般会很大长度一般为1024个二进制位;
    3、确定φ(n)φ(n)=(p1-1) * (p2-1)
    4、确定e值,1<e<φ(n)e为整数并且与φ(n)互质;
    5、确定d值,e*d%φ(n)=1
    6、加密 c=m^e%n
    7、解密m=c^d%n

    实际验证:
    1、p1=3p2=7
    2、n=p1 * p2=3 * 7=21
    3、φ(n)=(p1-1) * (p2-1)=2*6=12
    4、1<e<12e=5e12互质则取值{1,5,7,11}φ(12)=4个互质数,满足条件的有4个);
    5、e * d % φ(n)=5 * d % 12=1,得d=17
    6、设置明文m=3,则c = m^e % n = 3^5 % 21=12
    7、解密密文m=c^d % n=12^17 % 21=3

    数据传输过程:

    RSA.png

    四、OpenSSL

    OpenSSLMac系统内置的开源加密库,我们可以是用终端来获取私钥公钥,数据加密。
    主要命令:

    1、生成一个RSA私钥
    openssl genrsa -out private.pem 1024
    2、从私钥中提取公钥
    openssl rsa -in private.pem -pubout -out public.pem
    3、将私钥转换成明文
    openssl rsa -in private.pem -text -out private.txt
    4、通过公钥进行加密
    openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enmsg.txt
    5、通过私钥进行解密
    openssl rsautl -decrypt -in enmsg.txt -inkey private.pem -out demsg.txt
    6、通过私钥进行加密
    openssl rsautl -sign -in message.txt -inkey private.pem -out enmsg2.txt
    7、通过公钥进行解密
    openssl rsautl -verify -in enmsg2.txt -inkey public.pem -pubin -out demsg2.txt
    

    通过终端显示加密解密过程:
    1、创建私钥公钥:

    create.png

    2、查看私钥公钥:

    overview.png

    3、创建文本:

    message.png

    4、公钥对数据加密:

    encode1.png

    5、私钥解密:

    decode1.png

    6、私钥加密:

    encode2.png

    7、公钥解密:

    decode2.png

    来看看长什么样:

    cer.png

    这么看就很熟悉了,哈哈,可以用起来。

    展开全文
  • RSA加密算法

    万次阅读 多人点赞 2018-04-17 09:38:31
    公开密钥加密公开密钥加密(public-key cryptography),也成为非对称加密,是密码学的一种算法,他需要两个密钥,一个是公开密钥,另一个是私有密钥,一个用作加密的时候,另一个则用作解密。明文:需要加密的内容,...

    公开密钥加密

    公开密钥加密(public-key cryptography),也成为非对称加密,是密码学的一种算法,他需要两个密钥,一个是公开密钥,另一个是私有密钥,一个用作加密的时候,另一个则用作解密。

    • 明文:需要加密的内容,成为明文。
    • 密文:使用密钥把明文加密后的内容。只能用相应的另一个密钥才能解密得到原来的明文。甚至连最初用来加密的密钥也不能用作解密。

    对称加密&&非对称加密

    • 对称加密:加密和解密都是用同一个密钥的算法,称作对称加密。
    • 非对称加密:加密和解密需要不同的密钥。

    因为公钥加密的信息只用私钥才能解的开,所以只要私钥不泄露,通信就是安全的。

    今天这里只介绍RSA非对称加密。

    加密过程

    在数学上d(c(x))=x,来表示加密解密过程。

    这里我们使用典型的爱丽丝与鲍勃假设来解释(来自维基)。

    • 1.爱丽丝与鲍勃事先互不认识,也没有可靠安全的沟通渠道,但爱丽丝现在却要通过不安全的互联网向鲍勃发送消息。
    • 2.爱丽丝撰写好原文,原文在未加密的状态下称之为明文x。
    • 3.鲍勃使用密码学安全伪随机数生成器产生一对密钥,其中一个作为公钥c,另一个作为私钥d.
    • 4.鲍勃可以用任何方法发送公钥c给爱丽丝,即使伊夫在中间窃听到c也没关系。
    • 5.爱丽丝用公钥c把明文x进行加密,得到密文c(x).
    • 6.爱丽丝可以用任何方法传输密文c(x)给鲍勃,即使伊夫在中间窃听到密文c(x)也没问题。
    • 7.鲍勃收到密文,用自己的私钥d对密文进行解密d(c(x)),得到爱丽丝撰写的明文x.
    • 8.由于伊夫没有得到鲍勃的私钥d,所以无法得知明文x.
    • 9.如果爱丽丝丢失了她自己撰写的原文x,在没有得到鲍勃的私钥d的情况下,她的处境将等同伊夫,既无法通过鲍勃的公钥c和密文c(x)重新得到原文x.

    在正式介绍RSA之前,先介绍一些数学知识。

    互质关系

    如果两个正整数,除了1之外没有其他公因子,我们称这两个数是互质关系。比如15和32,说明不是质数也可以构成互质关系。

    关于互质关系,有以下结论:

    • 任意两个质数构成互质关系,比如13和61.
    • 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10.
    • 如果两个数中,较大的那个数是质数,则两者构成互质关系,比如97和57.
    • 1和任意一个自然数都是互质关系。
    • p是大于1的整数,则p和p-1构成互质关系,比如57和56.
    • p是大于1的奇数,则p和p-2构成互质关系,比如17和15.

    欧拉函数

    任意给定正整数n,计算在小于等于n的正整数之中,有多少个与n构成互质关系。计算这个值的方法叫做欧拉函数。以φ(n)表示。如φ(8)=4,应为在1到8之中,与8形成互质关系的有1,3,5,7。

    φ(n)的计算方法并不复杂,我们就分情况分析。

    第一种情况:

    如果n=1,则φ(1)=1。应为1与任何(包括自己)都构成互质关系。

    第二种情况:

    如果n是质数,则φ(n)=n-1。应为质数与每个小于他的数都构成互质关系。

    第三种情况:

    如果n是质数的某一个次方,即n=p^k(p为质数,k>=1),则


    如φ(8)=φ(2^3)=2^3-2^2=4。

    这是应为只有当一个数不包含质数p时,才能与n互质。而包含质数p的数一共有p^(k-1)个,即是1*p、2*p、...、p^(k-1)*p。

    上面的式子还可以写成:


    第四种情况:

    n可以分解成两个互质的整数之积。n = p1 * p2

    则 φ(n)=φ(p1p2)=φ(p1)φ(p2)

    即积的欧拉函数等于各个因子的欧拉函数之积。如:φ(56)=φ(7*8)=φ(7)*φ(8)=6*4=24

    第五种情况:

    因为任意大于1的整数,都可以写成一系列质数的积。


    根据第四条结论


    在根据第三条结论


    也就等于


    比如:

    φ(1323)=φ(3^2*7^2)=1323(1-1/3)(1-1/7)=756

    欧拉定理

    欧拉定理是指:如果两个正整数a和n互质,则n的欧拉函数φ(n)可以让下面的式子成立:



    即是a的φ(n)次方减去1,被n整除。比如,3和7互质,φ(7)=6,(3^6-1)/7=104

    如果正整数a与质数p互质,应为φ(p)=p-1,所以欧拉函数可写成:


    这个就是著名的费马小定理。

    模反元素

    如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除。


    比如:3和11互质,那么3的模反元素是4,应为3*4-1 可以被11整除。4加减11的整数倍数都是3的模反元素。

    欧拉定理可以用来证明模反元素必然存在:


    可以看到,a的φ(n)-1次方,就是a的模反元素。

    RSA算法

    RSA算法之一种非对称加密算法。具体的加密工程如下:

    依然使用Alice和他的小伙伴来举例子。

    假设Alice想通过一个不可靠的媒体接受Bob的一条私人消息,他可以用下面的方式产生一个公钥和私钥。

    • 1. 随意选择两个大的质数p和q,p不等于q,计算N = pq.
    • 2. 根据欧拉函数,求得r=φ(N)=φ(p)φ(q)=(p-1)(q-1)。
    • 3. 选择一个小于r的整数e,是e与r互质。并求得e关于r的模反元素,命名为d。(求d令ed≡1(mod r))。(模反元素存在,当且仅当e与r互质)
    • 4. 将p和q的记录销毁。

    其中(N,e)是公钥,(N,d)是私钥。

    举个例子:

    • 1. Alice随机选两个不相等的质数61和53,并计算两数的积N=61*53=3233,N的长度就是密钥长度。3233的二进制是110010100001,一共12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,总要的场合是2048位。
    • 2. 计算N的欧拉函数。 φ(N)=(p-1)(q-1)=60*52=3120.
    • 3. Alice 在1到3120上随机选择了一个随机数e=17。
    • 4. 计算e对φ(N)的模反元素d,即时,ed-1=kφ(N)。
    • 即使求解:17x+3120y=1.用扩展欧几里得算法求解。可以算出一组解(x,y)=(2753,-15),即d=2753。

    至此完成计算。

    其中N=3233,e=17,d=2753。所以公钥就是(N,e)=(3233,17),私钥(N,d)=(3233,2753)。实际应用中公钥和私钥都是采用ASN.1格式表达的。

    RSA的可靠性

    在RSA私钥和公钥生成的过程中,共出现过p,q,N,φ(N),e,d,其中(N,e组成公钥),其他的都不是公开的,一旦d泄露,就等于私钥泄露。那么能不能根据N,e推导出d呢?

    ed ≡ 1(mod φ(N))。只有知道e和φ(N),才能算出d
    φ(N)=(p-1)(q-1)。只有知道p和q,才能算出φ(N)
    n=pq,只有将n分解才能算出p和q

    所以,只有将n质因数分解,才能算出d。也就意味着私钥破译。

    但是,大整数的质因数分解是非常困难的。

    加密和解密

    加密

    加密要用到公钥(N,e)。

    假设Bob要向Alice发送加密信息m,他就要用Alice的公钥(N,e)对m进行加密。但m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

    所谓加密就是计算下式的c。

    m^e ≡ c (mod n)

    假设m=65,Alice的公钥(3233,17),所以等式如下:

    65^17≡2790(mod 3233)

    所以c等于2790,Bob就把2790发给Alice。

    解密

    Alice收到Bob发来的2790后,就用自己的私钥(3233,2755)进行解密。

     c^d ≡ m (mod n)

    也就是c的d次方除以n的余数就是m。

    2790^2753 ≡ 65 (mod 3233)

    因此得到原文65。

    证明

    记下来证明为什么用私钥就能解密。就是要证明这个式子:

     c^d ≡ m (mod n)

    因为加密规则是:

    m^e ≡ c (mod n)

    于是,c可以写成:

    c = m^e - kn

    将c代入要我们要证明的那个解密规则:

     (m^e - kn)^d ≡ m (mod n)

    等同于求证:

    m^ed ≡ m (mod n)
    因为:ed ≡ 1 (mod φ(n))
    所以: ed = hφ(n)+1
    将ed代入:
    m^(hφ(n)+1) ≡ m (mod n)
    

    接下来,分成两种情况证明上面这个式子。

    1. 当m与n互质

    根据欧拉定理,此时
    m^φ(n) ≡ 1 (mod n)
    得到:(m^φ(n))^h × m ≡ m (mod n)

    由此原始得到证明。

    2. 当m与n不是互质时

    此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

    以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

    (kp)^q-1 ≡ 1 (mod q)
    进一步得到:
    [(kp)^(q-1)]^(h(p-1))× kp ≡ kp (mod q)
    即:(kp)^ed ≡ kp (mod q)
    改写成:(kp)^ed = tq + kp

    上式t必然能被p整除,即t=t'p

    (kp)^ed = t'pq + kp

    因为m=kp,n=pq,所以:

    m^ed ≡ m (mod n)

    证明完毕。

    注:转载自阮一峰老师

    展开全文
  • python使用RSA加密算法

    万次阅读 多人点赞 2018-05-27 18:41:26
    最近换了工作,由于新公司是做个人和企业征信业务的,所以对数据的隐私性看的非常重要,所有涉及隐私的...基于我用python语言搞,那我这里就说说我是如何实现python对数据进行RSA加解密的吧。。 一、查找python支...
  • RSA 加密算法原理简述

    万次阅读 2018-07-23 22:32:42
    本文旨在说明RSA加密算法的原理及实现,而其相关的数学部分的证明则不是本文内容。 版权说明 著作权归作者所有。 商业转载请联系作者获得授权,非商业转载请注明出处。 作者:Q-WHai 发表日期: 2016年2月29...
  • 手把手教你 RSA加密

    千次阅读 2018-07-20 18:36:28
    RSA加解密java中的使用 好了废话不多说 上代码 使用环境:eclipse + maven,无maven猿友可自行下载这两个jar包:bcprov-jdk16-1.4.5.jar 和 commons-codec-1.6.jar maven的猿友添加如下依赖: &lt;...
  • 浅谈RSA加密

    千次阅读 2018-06-21 22:00:33
    银行和阿里的安全机制相对来说比较完善 说到加密,目前比较常见的有对称加密和非对称加密,那什么是对称加密和非对称加密呢,如图对称加密假如 一个人A想把信息m发给B 他不能直接把m给B,不然会被窃听到,所以A对...
  • 非对称加密算法--RSA加密原理

    万次阅读 多人点赞 2018-12-24 00:33:58
    在说RSA加密算法之前, 先说下密码学的发展史。其实密码学的诞生,就是为了运用在战场,在公元前,战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。...
  • RSA完整加密流程总结

    千次阅读 2019-10-21 23:32:17
    1.1-RSA加密介绍 1.RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。1987年7月首次在美国公布,当时他们三人都在麻省理工...
  • 条理清晰的入门:使用Java实现RSA加密解密 需要导入的头文件 生成公钥、私钥 进行加密解密 密钥的存储 密文的存储、读取
  • /// RSA ECC /// 可逆非对称加密 /// 非对称加密算法的优点是密钥管理很方便,缺点是速度慢。 /// </summary> public class RsaEncrypt { /// <summary> /// 获取加密/解密对 /// 给你一个,...
  • C++实现RSA加密解密

    万次阅读 2017-06-18 11:45:30
    RSA算法的描述
  • 只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。 RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易,但是想...
  • 2019-02-26日更新:源码更新至github上。 2017-12-04日更新:增加支持微信支付。...C#RSA加签解签加密比较常见,一般遇到的问题是非.NET代码的加签验签、加密解密。以下就是解决此类问题的。 一般情况下是【...
  • Android RSA加密解密demo

    千次下载 热门讨论 2014-08-23 14:37:48
    Android RSA加密解密demo,详情请参看博客:http://blog.csdn.net/bbld_/article/details/38777491
  • RSA加密的原理——为什么被公钥加密的可以被私钥解密? 目录 一,RSA 数学理论基础 二,RSA实现原理 三,RSA加密的过程 四,参考文献 引言 在密码学最开始,都是使用的普通加密模式 A 用加密...
  • RSA加密 Java实现

    2018-04-20 11:02:44
    RSA加密 Java实现,RSA加密 Java实现,RSA加密 Java实现
  • RSA加密算法详解

    万次阅读 多人点赞 2016-07-19 11:51:44
    本篇主要想详细介绍RSA加密算法的原理,经常听别人说,这里是自己想搞清楚,弄明白。首先介绍了基本的数学原理,然后给出一个具体的计算例子和相关的理论充分性证明。 皓眸大前端开发学习 转载请注明出处:...
  • php rsa加密算法

    2018-03-06 14:11:39
    python的rsa加密代码翻译成php import rsa def get_encrypted_pw(self,password,nonce,servertime,pub_key): rsa_e = 65537 #0x10001 pw_string = str(servertime) + '\t' + str(nonce) + '\n' + str(password) ...
  • javaRSA加密C++RSA解密

    2017-11-28 16:32:04
    JAVA也是通过包来实现加密和解密的,那么我的C++是通过OPENSSL的库来实现的。 重点来到了:RSA使用过程 1、C++随机生成一对公钥和私钥 2、JAVA用公钥给明文打包形成密文 3、C++用私钥解密密文
  • Java RSA 加密

    千次阅读 2018-11-23 19:38:50
    什么是Rsa加密? RSA算法是最流行的公钥密码算法,使用长度可以变化的密钥。RSA是第一个既能用于数据加密也能用于数字签名的算法。 RSA算法原理如下: 1.随机选择两个大质数p和q,p不等于q,计算N=pq;  ...
  • 使用Python实现RSA加密算法及详解RSA算法

    万次阅读 多人点赞 2018-03-07 21:35:23
    代码已经放上github : https://github.com/chroje/RSA一、非对称加密算法1、乙方生成两把密钥(公钥和...二、RSA算法1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法...
  • RSA加密算法原理

    千次阅读 2019-10-08 00:58:01
    一、什么是RSA加密算法: 二、RSA加密过程: 三、RAS解密过程: 四、生成密钥对: 五、实践: 六、Java进行 RSA 加解密时不得不考虑到的那些事儿: 一、什么是RSA加密算法: RSA加密算法是一种非对称加密算法...
  • python - RSA加密

    千次阅读 2018-07-31 22:47:35
    今天笔者想要分享的是另外一种加密,python中的RSA加密,当我们不用selenium和Chromedriver的时候模拟登录问题常常是我们的一大难关,因为登录的时候可能会遇到一些加单的账号或者密码加密,最常见的也就是md5加密了...
  • RSA加密算法的java实现

    万次阅读 多人点赞 2017-11-02 16:53:14
    最近有一个外部合作项目要求在数据传输过程中使用RSA加密算法对数据进行加密,所以需要编写一个加解密的工具类,因为对方不是java语言,所以是各自实现的这个工具,本文主要讨论实现以及双方调试过程中的一些插曲,...
  • js版rsa加密

    2019-01-17 12:55:06
    js版rsa加密,用法参考资源里面的index.html,服务器返回rsa参数,页面加密得到加密数据,不支持包含中文的加密
  • rsa加密算法c++实现

    热门讨论 2011-06-08 19:59:27
    如下式加密算法部分: void CRSAUtilDlg::OnButtonDecrypt() { UpdateData(); CBigNumber cipher; cipher.StringHexFrom(m_strMessageC); BYTE by[8192]; m_pbDE.SetRange(0, 100); DWORD dwTicks = ...
  • AES与RSA加密

    2019-07-03 18:52:13
    AES加密是一种对称式加密,即加密和解密所需秘钥是相同的,你可以生成一组秘钥,然后利用该秘钥加密...同时,相比RSA加密来说,好处是不会限制加密字符串的长度。 下面贴出AES加密代码 package dev.parking.u...
  • RSA加密算法的C语言实现

    千次下载 热门讨论 2008-01-10 11:26:01
    RSA加密算法的C语言实现

空空如也

1 2 3 4 5 ... 20
收藏数 277,021
精华内容 110,808
关键字:

rsa加密