帮我解释一下RSA算法的原理-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

帮我解释一下RSA算法的原理

知与谁同 2018-07-15 18:44:07 870
帮我解释一下RSA算法的原理
rsa算法 rsa算法原理
分享到
取消 提交回答
全部回答(3)
  • 寒凝雪
    2019-07-17 22:56:18
    给你个java的代码你,希望对你有帮助
    package standard.system;

    import java.io.UnsupportedEncodingException;
    import java.net.URLDecoder;
    import java.net.URLEncoder;
    import java.util.Random;

    public class RSACrypt {
    private static int _PrivateKey = 32823; // 私钥

    private static int _PublicKey = 20643; // 公钥

    private static int _Modulus = 29893; // 模数

    // 对数字进行加密解密运算,根据key为公钥或是私钥来判断对数字进行加密或解密操作
    private static int Crypt(int number, int key) {
    int mod;
    int i;
    int result = 0;

    try {
    mod = number * number % _Modulus;
    if (key % 2 == 0) {
    result = 1;
    for (i = 0; i < key / 2; i++) {
    result = mod * result % _Modulus;
    }
    } else {
    result = number;
    for (i = 0; i < key / 2; i++) {
    result = mod * result % _Modulus;
    }
    }
    } catch (Exception e) {
    }
    return result;
    }

    // 根据字符位置将字符的ASCII数值进行偏移,并得到密文
    public static String Encode(String message) {
    int length = message.length(); // 明文的长度
    int ascCode; // ASCII码
    int cryptCode; // 密码
    int rndCode; // 随机码
    int index;
    String encodeString = ""; // 密文

    if (length == 0) {
    return null;
    }

    // 产生随机码
    Random rnd = new Random();
    rndCode = 1 + rnd.nextInt(99);

    for (index = 0; index < length; index++) {
    // 获取单字符的ASCII码
    ascCode = (int) message.charAt(index);
    // 同一字符根据随机码偏移保证每次不同
    ascCode += rndCode;
    // 同一字符在不同位置保证不同
    ascCode += index + 1; // 因索引值与domino不同(domino起始为1),所以此处加1
    // 同一字符在字符串长度变化时保证不同
    ascCode += length;
    ascCode = ascCode % 128;

    // 加密为密码
    cryptCode = Crypt(ascCode, _PublicKey);
    // 将密码转换为4位16进制字符串
    encodeString += DecimalToHex(cryptCode, 4);
    }

    // 最后附上随机码的2位16进制字符串
    encodeString += DecimalToHex(rndCode, 2);

    return encodeString;
    }

    // 将密文转换为明文,再对明文进行字位偏移,最终得到原文
    public static String Decode(String message) {
    int length = message.length() - 2; // 剥离随机码后的密文长度
    int ascCode; // ASCII码
    int cryptCode; // 密码
    int rndCode; // 随机码
    int index;
    String decodeString = ""; // 明文
    // 获取随机码的10进制数字
    rndCode = HexToDecimal(message.substring(length));
    for (index = 0; index < length; index += 4) {
    // 将4位16进制字符串转换为10进制密码
    cryptCode = HexToDecimal(message.substring(index, index + 4));
    // 解密为明码
    ascCode = Crypt(cryptCode, _PrivateKey);

    // 还原随机码偏移
    ascCode -= rndCode;
    // 还原字位偏移
    ascCode += (length / 4 % 128 + 1) * 128 - (index + 1) / 4 - 1; // 因索引值与domino不同(domino起始为1),所以此处加1
    // 还原字符串长度偏移
    ascCode += (length / 4 % 128 + 1) * 128 - length / 4;
    ascCode = ascCode % 128;

    // 将ASCII码转换为字符
    decodeString += (char) ascCode;
    }

    return decodeString;
    }

    // 10进制数字转16进制字符串
    private static String DecimalToHex(int decNumber, int hexWidth) {
    String hexString = Integer.toHexString(decNumber);
    while (hexString.length() < hexWidth)
    hexString = "0" + hexString;
    return hexString;
    }

    // 16进制字符串转10进制数字
    private static int HexToDecimal(String hexString) {
    return Integer.parseInt(hexString, 16);
    }

    public static void main(String[] args) throws UnsupportedEncodingException {
    String str = "测试158228&&2008-10-23_15:39:58";
    System.out.println(str);
    str = URLEncoder.encode(str, "UTF-8");
    System.out.println(str);
    for (int i = 0; i < 10; i++) {
    String r = RSACrypt.Encode(str);
    System.out.println(r);
    System.out.println(URLDecoder.decode(RSACrypt.Decode(r), "UTF-8"));
    }

    }
    }
    0 0
  • boxti
    2019-07-17 22:56:17
    RSA算法非常简单,概述如下:
    找两素数p和q
    取n=p*q
    取t=(p-1)*(q-1)
    取任何一个数e,要求满足e<t并且e与t互素(就是最大公因数为1)
    取d*e%t==1

    这样最终得到三个数: n d e

    设消息为数M (M <n)
    设c=(M**d)%n就得到了加密后的消息c
    设m=(c**e)%n则 m == M,从而完成对c的解密。
    注:**表示次方,上面两式中的d和e可以互换。

    在对称加密中:
    n d两个数构成公钥,可以告诉别人;
    n e两个数构成私钥,e自己保留,不让任何人知道。
    给别人发送的信息使用e加密,只要别人能用d解开就证明信息是由你发送的,构成了签名机制。
    别人给你发送信息时使用d加密,这样只有拥有e的你能够对其解密。

    rsa的安全性在于对于一个大数n,没有有效的方法能够将其分解
    从而在已知n d的情况下无法获得e;同样在已知n e的情况下无法
    求得d。

    RSA简洁幽雅,但计算速度比较慢,通常加密中并不是直接使用RSA 来对所有的信息进行加密,
    最常见的情况是随机产生一个对称加密的密钥,然后使用对称加密算法对信息加密,之后用
    RSA对刚才的加密密钥进行加密。

    最后需要说明的是,当前小于1024位的N已经被证明是不安全的
    自己使用中不要使用小于1024位的RSA,最好使用2048位的。
    0 0
  • 一键天涯
    2019-07-17 22:56:17
    首先, 找出三个数, p, q, r,
    其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数
    p, q, r 这三个数便是 private key

    接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1
    这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了
    再来, 计算 n = pq
    m, n 这两个数便是 public key

    编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a < n
    如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t),
    则每一位数均小於 n, 然後分段编码
    接下来, 计算 b == a^m mod n, (0 <= b < n),
    b 就是编码後的资料

    解码的过程是, 计算 c == b^r mod pq (0 <= c < pq),
    於是乎, 解码完毕.等会会证明 c 和 a 其实是相等的 :)

    如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b
    他如果要解码的话, 必须想办法得到 r所以, 他必须先对 n 作质因数分解.
    要防止他分解, 最有效的方法是找两个非常的大质数 p, q,
    使第三者作因数分解时发生困难
    <定理>
    若 p, q 是相异质数, rm == 1 mod (p-1)(q-1),
    a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq,
    则 c == a mod pq

    证明的过程, 会用到费马小定理, 叙述如下:
    m 是任一质数, n 是任一整数, 则 n^m == n mod m
    (换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m)
    运用一些基本的群论的知识, 就可以很容易地证出费马小定理的
    <证明>
    因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数
    因为在 modulo 中是 preserve 乘法的
    (x == y mod z and u == v mod z => xu == yv mod z),
    所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq

    1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时,
    则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p
    a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q
    所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
    即 a^(k(p-1)(q-1)) == 1 mod pq
    => c == a^(k(p-1)(q-1)+1) == a mod pq

    2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,
    则 a^(q-1) == 1 mod q (费马小定理)
    => a^(k(p-1)(q-1)) == 1 mod q
    => c == a^(k(p-1)(q-1)+1) == a mod q
    => q | c - a
    因 p | a
    => c == a^(k(p-1)(q-1)+1) == 0 mod p
    => p | c - a
    所以, pq | c - a => c == a mod pq

    3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上

    4. 如果 a 同时是 p 和 q 的倍数时,
    则 pq | a
    => c == a^(k(p-1)(q-1)+1) == 0 mod pq
    => pq | c - a
    => c == a mod pq
    Q.E.D.

    这个定理说明 a 经过编码为 b 再经过解码为 c 时, a == c mod n (n = pq)
    但我们在做编码解码时, 限制 0 <= a < n, 0 <= c < n,
    所以这就是说 a 等於 c, 所以这个过程确实能做到编码解码的功能
    0 0
添加回答
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

相似问题
最新问题