小程序RSA加密、解密、加签、验签

npm install  wxapp_rsa

var RSA = require('/wxapp_rsa.js')

// RSA加签

    var sign_rsa = new RSA.RSAKey()

//privateKey_pkcs1需要是-----BEGIN PRIVATE KEY-----开头的私钥

    sign_rsa = RSA.KEYUTIL.getKey(privateKey_pkcs1)

    console.log('签名RSA:')

    console.log(sign_rsa)

    var hashAlg = 'MD5withRSA'

    var hSig = sign_rsa.signString("12345678901234567890", hashAlg)

    hSig = RSA.hex2b64(hSig)// hex 转 b64

    console.log("签名结果：" + hSig)

    // RSA 验签

    var verify_rsa = new RSA.RSAKey()

    verify_rsa = RSA.KEYUTIL.getKey(publicKey_pkcs1)

    console.log('验签RSA:')

    console.log(verify_rsa)

    hSig = RSA.b64tohex(hSig)

    var ver = verify_rsa.verifyString("12345678901234567890", hSig)

    console.log('验签结果：' + ver)

//  RSA加密 【加密字段长度不大于117】

    var encrypt_rsa = new RSA.RSAKey()

    encrypt_rsa = RSA.KEYUTIL.getKey(rsa_public_key)

    console.log('加密RSA:')

    console.log(encrypt_rsa)

    var encStr = encrypt_rsa.encrypt('1234567890')

    console.log(encStr)

    encStr = RSA.hex2b64(encStr)

    console.log("加密结果：" + encStr)

    // RSA 解密

    var decrypt_rsa = new RSA.RSAKey()

    decrypt_rsa = RSA.KEYUTIL.getKey(rsa_public_key_private)

    console.log('解密RSA:')

    console.log(decrypt_rsa)

    encStr = RSA.b64tohex(encStr)

    var decStr = decrypt_rsa.decrypt(encStr)

    console.log("解密结果：" + decStr)

分类: 电脑/网络 >>程序设计 >>其他编程语言

问题描述:

用RSA对下列数据实现加密和解密:

a. p=3,q=11,e=7M=5

b. p=7,q=11,e=3M=9

解析:

拜托:老大,你的家庭作业也来问?

你自己学吧:下面是课文^

RSA加密算法

该算法于1977年由美国麻省理工学院MIT(Massachusetts Institute of Technology)的Ronal Rivest，Adi Shamir和Len Adleman三位年轻教授提出，并以三人的姓氏Rivest，Shamir和Adlernan命名为RSA算法。该算法利用了数论领域的一个事实，那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情，但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题，至今没有任何高效的分解方法。与Diffie-Hellman算法相比，RSA算法具有明显的优越性，因为它无须收发双方同时参与加密过程，且非常适合于电子函件系统的加密。

RSA算法可以表述如下：

(1) 密钥配制。假设m是想要传送的报文，现任选两个很大的质数p与q，使得：

(12-1)；

选择正整数e，使得e与(p－1)(q－1)互质；这里(p－1)(q－1)表示二者相乘。再利用辗转相除法，求得d，使得：

(12-2)；

其中x mod y是整数求余运算，其结果是x整除以y后剩余的余数，如5 mod 3 = 2。

这样得：

(e，n)，是用于加密的公共密钥，可以公开出去；以及

(d，n)，是用于解密的专用钥匙，必须保密。

(2) 加密过程。使用(e，n)对明文m进行加密，算法为：

(12-3)；

这里的c即是m加密后的密文。

(3) 解密过程。使用(d，n)对密文c进行解密，算法为：

(12-4)；

求得的m即为对应于密文c的明文。

RSA算法实现起来十分简捷，据说英国的一位程序员只用了3行Perl程序便实现了加密和解密运算。

RSA算法建立在正整数求余运算基础之上，同时还保持了指数运算的性质，这一点我们不难证明。例如：

(12-5)；

(12-6)。

RSA公共密钥加密算法的核心是欧拉(Euler)函数ψ。对于正整数n，ψ(n)定义为小于n且与n互质的正整数的个数。例如ψ(6) = 2，这是因为小于6且与6互质的数有1和5共两个数；再如ψ(7) = 6，这是因为互质数有1，2，3，5，6共6个。

欧拉在公元前300多年就发现了ψ函数的一个十分有趣的性质，那就是对于任意小于n且与n互质的正整数m，总有mψ(n) mod n = 1。例如，5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。也就是说，在对n求余的运算下，ψ(n)指数具有周期性。

当n很小时，计算ψ(n)并不难，使用穷举法即可求出；但当n很大时，计算ψ(n)就十分困难了，其运算量与判断n是否为质数的情况相当。不过在特殊情况下，利用ψ函数的两个性质，可以极大地减少运算量。

性质1：如果p是质数，则ψ(p) = (p－1)。

性质2：如果p与q均为质数，则ψ(p·q) = ψ(p)·ψ(q) = (p－1)(q－1)。

RSA算法正是注意到这两条性质来设计公共密钥加密系统的，p与q的乘积n可以作为公共密钥公布出来，而n的因子p和q则包含在专用密钥中，可以用来解密。如果解密需要用到ψ(n)，收信方由于知道因子p和q，可以方便地算出ψ(n) = (p－1)(q－1)。如果窃听者窃得了n，但由于不知道它的因子p与q，则很难求出ψ(n)。这时，窃听者要么强行算出ψ(n)，要么对n进行因数分解求得p与q。然而，我们知道，在大数范围内作合数分解是十分困难的，因此窃密者很难成功。

有了关于ψ函数的认识，我们再来分析RSA算法的工作原理：

(1) 密钥配制。设m是要加密的信息，任选两个大质数p与q，使得 ；选择正整数e，使得e与ψ(n) = (p－1)(q－1)互质。

利用辗转相除法，计算d，使得ed mod ψ(n) = ，即ed = kψ(n) +1，其中k为某一正整数。

公共密钥为(e，n)，其中没有包含任何有关n的因子p和q的信息。

专用密钥为(d，n)，其中d隐含有因子p和q的信息。

(2) 加密过程。使用公式(12-3)对明文m进行加密，得密文c。

(3) 解密过程。使用(d，n)对密文c进行解密，计算过程为：

cd mod n = (me mod n)d mod n

= med mod n

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n)·(m mod n)

= m

m即为从密文c中恢复出来的明文。

例如，假设我们需要加密的明文代码信息为m = 14，则：

选择e = 3，p = 5，q = 11；

计算出n = p·q = 55，(p－1)(q－1) = 40，d = 27；

可以验证：(e·d) mod (p－1)(q－1) = 81 mod 40 = 1；

加密：c = me mod n = 143 mod 55 = 49；

解密：m = cd mod n = 4927 mod 55 = 14。

关于RSA算法，还有几点需要进一步说明：

(1) 之所以要求e与(p－1)(q－1)互质，是为了保证 ed mod (p－1)(q－1)有解。

(2) 实际 *** 作时，通常先选定e，再找出并确定质数p和q，使得计算出d后它们能满足公式(12-3)。常用的e有3和65537，这两个数都是费马序列中的数。费马序列是以17世纪法国数学家费马命名的序列。

(3) 破密者主要通过将n分解成p·q的办法来解密，不过目前还没有办法证明这是唯一的办法，也可能有更有效的方法，因为因数分解问题毕竟是一个不断发展的领域，自从RSA算法发明以来，人们已经发现了不少有效的因数分解方法，在一定程度上降低了破译RSA算法的难度，但至今还没有出现动摇RSA算法根基的方法。

(4) 在RSA算法中，n的长度是控制该算法可靠性的重要因素。目前129位、甚至155位的RSA加密勉强可解，但目前大多数加密程序均采用231、308甚至616位的RSA算法，因此RSA加密还是相当安全的。

据专家测算，攻破512位密钥RSA算法大约需要8个月时间；而一个768位密钥RSA算法在2004年之前无法攻破。现在，在技术上还无法预测攻破具有2048位密钥的RSA加密算法需要多少时间。美国Lotus公司悬赏1亿美元，奖励能破译其Domino产品中1024位密钥的RSA算法的人。从这个意义上说，遵照SET协议开发的电子商务系统是绝对安全的。

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <time.h>

#define PRIME_MAX 200   // 生成素数范围

#define EXPONENT_MAX 200 // 生成指数e范围

#define Element_Max 127    // 加密单元的最大值，这里为一个char, 即1Byte

char str_read[100]="hello world !"  // 待加密的原文

int str_encrypt[100]                // 加密后的内容

char str_decrypt[100]              // 解密出来的内容

int str_read_len                    // str_read 的长度

int prime1, prime2                  // 随机生成的两个质数

int mod, eular                      // 模数和欧拉数

int pubKey, priKey                  // 公钥指数和私钥指数

// 生成随机素数，实际应用中，这两个质数越大，就越难破解。

int randPrime()

{

int prime, prime2, i

next:

prime = rand() % PRIME_MAX   // 随机产生数

if (prime <= 1) goto next      // 不是质数，生成下一个随机数

if (prime == 2 || prime == 3) return prime

prime2 = prime / 2              // prime>=4, prime2 的平方必定大于 prime , 因此只检查小于等于prime2的数

for (i = 2i <= prime2i++)   // 判断是否为素数

{

if (i * i >prime) return prime

if (prime % i == 0) goto next  // 不是质数，生成下一个随机数

}

}

// 欧几里德算法，判断a,b互质

int gcd(int a, int b)

{

int temp

while (b != 0) {

temp = b

b = a % b

a = temp

}

return a

}

//生成公钥指数，条件是 1<e <欧拉数，且与欧拉数互质。

int randExponent()

{

int e

while (1)

{

e = rand() % eularif (e <EXPONENT_MAX) break

}

while (1)

{

if (gcd(e, eular) == 1) return ee = (e + 1) % eularif (e == 0 || e >EXPONENT_MAX) e = 2

}

}

//生成私钥指数

int inverse()

{

int d, x

while (1)

{

d = rand() % eular

x = pubKey * d % eular

if (x == 1)

{

return d

}

}

}

//加密函数

void jiami()           

{

str_read_len = strlen(str_read)      //从参数表示的地址往后找，找到第一个'\0'，即串尾。计算'\0'至首地址的“距离”，即隔了几个字符，从而得出长度。

printf("密文是：")

for (int i = 0i <str_read_leni++)

{

int C = 1int a = str_read[i], b = a % mod

for (int j = 0j <pubKeyj++) //实现加密

{

C = (C*b) % mod

}

str_encrypt[i] = C

printf("%d ", str_encrypt[i])

}

printf("\n")

}

//解密函数

void jiemi()         

{

int i=0  for (i = 0i <str_read_leni++)

{

int C = 1int a = str_encrypt[i], b=a%mod

for (int j = 0j <priKeyj++)

{

C = (C * b) % mod

}

str_decrypt[i] = C

}

str_decrypt[i] = '\0'printf("解密文是：%s \n", str_decrypt)

}

int main()

{

srand(time(NULL))

while (1)

{

prime1 = randPrime()prime2 = randPrime()printf("随机产生两个素数：prime1 = %d , prime2 = %d ", prime1, prime2)

mod = prime1 * prime2printf("模数：mod = prime1 * prime2 = %d \n", mod)if (mod >Element_Max) break// 模数要大于每个加密单元的值

}

eular = (prime1 - 1) * (prime2 - 1)  printf("欧拉数：eular=(prime1-1)*(prime2-1) = %d \n", eular)

pubKey = randExponent()printf("公钥指数：pubKey = %d\n", pubKey)

priKey = inverse()printf("私钥指数：priKey = %d\n私钥为 (%d, %d)\n", priKey, priKey, mod)

jiami()jiemi()

return 0

}

---