信息计算2019级1班3号刘丹丹

2019-1刘丹丹 · 发表于 2022-5-2 22:05:11

大数RSA算法的实现
一.原理：RSA算法的具体描述如下：
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)是私钥。用到了求模逆，互质关系，欧拉函数等数学知识

二.源程序：

import java.math.*;
import java.util.*;
public class Test1 {
public static BigInteger Prime(BigInteger N)
{
boolean f1 = true;
boolean f2 = true;
BigInteger E = null;
while (f1)
{
int e = (int) (Math.random() * 1000000000 + 2);
E = new BigInteger(String.valueOf(e));
BigInteger a = BigInteger.ZERO;
while (f2) {
a = E.mod(N);
if (a.equals(BigInteger.ZERO))
break;
else
E = N;
N = a;
if (N.equals(BigInteger.ONE)) {
f1 = false;
f2 = false;
E = new BigInteger(String.valueOf(e));
}
}
}
return E;
}
public static void main(String[] args){
Random rad = new Random();
BigInteger P = BigInteger.probablePrime(100, rad);
BigInteger Q = BigInteger.probablePrime(100, rad);
P = new BigInteger("1422190779664435130578574872464189487159269521438844277069165347989379651477195077278520918544216091165328330" +
"37439126553885228505041962156920856757540374980634188741118614578251050137701249084108411224753759631562279017912889888838823830260852615022162119976454139351863355473841839316049016083961001571120119");
Q = new BigInteger("1154063353988317882630621327580284079361812526326427928762763251614128450514432787184549821060375619085643258410" +
"08562548113013126674531705009431442852270585480837050915675733690296476470166027390822965804009765817418751368137319529407681332211027693672973572001086145050157986459263311606907760630228706795319");
BigInteger N = P.multiply(Q);
BigInteger M = (P.subtract(BigInteger.ONE)).multiply((Q.subtract(BigInteger.ONE)));
BigInteger E = Prime(N);
//E = BigInteger.probablePrime(100,rad);
//E = new BigInteger("13");
BigInteger D = oula(E,M);
// 加密
String mingwen = "";
System.out.println("明文：");
Scanner scanner1 = new Scanner(System.in);
if(scanner1.hasNext())
{
mingwen = scanner1.nextLine();
}
byte[] bytes = new byte[mingwen.length()];
for (int i = 0;i < mingwen.length();i++)
{
bytes[i] = Byte.valueOf((byte) mingwen.charAt(i));
}
BigInteger a = new BigInteger(1,bytes);
BigInteger b = a.modPow(E,N);
System.out.println("密文为： " + b);
// 解密
String miwen = null;
System.out.println("输入密文：");
Scanner scanner2 = new Scanner(System.in);
if(scanner2.hasNext())
{
miwen = scanner2.nextLine();
}
BigInteger c = new BigInteger(miwen);
BigInteger d = c.modPow(D,N);
byte[] bytes2 = new byte[miwen.length()];
bytes2 = d.toByteArray();
System.out.print("密文为： ");
for (int i = 0; i < bytes2.length; ++i)
System.out.print((char) bytes2[i]);
}
public static BigInteger oula(BigInteger E, BigInteger M){
boolean f = true;
BigInteger a = new BigInteger("1");
BigInteger b = new BigInteger("0");
BigInteger c = M;
BigInteger d = E;
BigInteger temp, s;
while (f)
{
temp = c.remainder(d);
if (temp.compareTo(BigInteger.ZERO) == 0)
f = false;
s = c.divide(d);
c = d;
d = temp;
temp = b.subtract(a.multiply(s));
b = a;
if (f)
a = temp;
}
if (a.compareTo(BigInteger.ZERO) < 0)
return a.add(M);
else
return b;
}
}

复制代码

三.程序截图：

2019-1刘丹丹 · 发表于 2022-5-30 22:11:29

本帖最后由 2019-1刘丹丹于 2022-5-30 22:16 编辑

RSA大数算法改进版

在之前的基础上，对RSA大数算法进行改进，重写，程序为：

package 密码学RSA;
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
public class RSA大数版本 {
public static BigInteger Mod_ni(BigInteger a, BigInteger b) {
BigInteger zero = new BigInteger("0");
a = a.subtract(b.multiply(a.divide(b))); // a = a - b * (a / b)
int i = 0;
BigInteger bb = b;
BigInteger s[] = new BigInteger[1024];
while (a.compareTo(zero) != 0) { // a != 0
s[i] = b.divide(a); // s[i] = b / a
BigInteger t = b;
b = a;
a = t.mod(a); // t % a
i++;
}
BigInteger y[] = new BigInteger[i];
y[0] = new BigInteger("1");
y[1] = s[0];
for (int j = 2; j < i; j++)
y[j] = (y[j - 1].multiply(s[j - 1])).add(y[j - 2]); // y[j] = y[j - 1] * s[j - 1] + y[j - 2]
if ((i - 1) % 2 == 1)
y[i - 1] = bb.subtract(y[i - 1]); // y[i - 1] = bb - y[i - 1]
return y[i - 1];
}
public static void main(String args[]) {
BigInteger one = new BigInteger("1");
Random rnd = new Random();
BigInteger p = new BigInteger("1");
BigInteger q = new BigInteger("1");
p = BigInteger.probablePrime(1024, rnd);
q = BigInteger.probablePrime(1024, rnd);
BigInteger n = p.multiply(q); // n = p * q
BigInteger f = (p.subtract(one).multiply(q.subtract(one))); // f = (p - 1) * (q - 1)
BigInteger e = new BigInteger("65537");
while (true) {
e = BigInteger.probablePrime(1024, rnd);
if (e.compareTo(f) <= 1)
break;
}
BigInteger d = Mod_ni(e, f);
System.out.println("n = " + n);
System.out.println("公钥：" + e);
System.out.println("私钥：" + d);
BigInteger xx, yy;
while (true) {
System.out.println("请选择功能： \n0.退出 \n1.加密\n2.解密");
Scanner scan1 = new Scanner(System.in);
int ch = scan1.nextInt();
if (ch == 1) {
System.out.println("请输入明文：");
String mingwen = new String();
Scanner scan2 = new Scanner(System.in);
mingwen = scan2.nextLine();
byte x[] = new byte[mingwen.length()];
for (int i = 0; i < mingwen.length(); i++)
x[i] = Byte.valueOf((byte) mingwen.charAt(i));
xx = new BigInteger(x); // 字节数组转大整型
xx = xx.modPow(e, n); // xx^e mod n
System.out.println("密文为：" + xx);
} else if (ch == 2) {
System.out.println("请输入密文：");
String miwen = new String();
Scanner scan3 = new Scanner(System.in);
miwen = scan3.nextLine();
yy = new BigInteger(miwen);
yy = yy.modPow(d, n); // yy^d mod n
byte[] y = yy.toByteArray(); // 大整型转字节数组
System.out.print("明文为:");
for (int i = 0; i < y.length; ++i)
System.out.print((char) y[i]);
System.out.print('\n');
} else
break;
}
}
}

复制代码

2019-1刘丹丹 · 发表于 2022-5-30 23:07:45

本帖最后由 2019-1刘丹丹于 2022-5-31 11:22 编辑

                                                                                                     RSA签名
一.简介
  (1)签名就是在这份资料后面增加一段强而有力的证明，以此证明这段信息的发布者和这段信息的有效性完整性。
  （2）RSA签名常用的就是将这份信息进行hash，得到一个hash值，再将hash值加密作为签名，后缀在信息的末尾。
  （3）哈希的好处：更安全，签名更快，解除了签名长度的限制。

二.具体实现过程
RSA数字签名算法的过程为：A对明文m用解密变换作: (公钥用来加密，私钥用来解密，数字签名是用私钥完成的，所以称为解密变换，这与onu sdk中一致)sº Dk (m)=md mod n,其中d，n为A的私人密钥，只有A才知道它；B收到Ａ的签名后，用A的公钥和加密变换得到明文，因: Ek(s)= Ek(Dk (m))= (md)e mod n,又 deº1 mod j(n)即de=lj(n)+1,根据欧拉定理mj(n)=1 mod n，所以Ek(s)=mlj(n)+1=[mj(n)]em=m mod n。若明文m和签名s一起送给用户B,B可以确信信息确实是A发送的。同时A也不能否认送给这个信息，因为除了A本人外，其他任何人都无法由明文m产生s.因此RSA数字签名方案是可行的。

1 签名算法：签名算法包括消息摘要计算，RSA加密。

(1) 消息摘要计算。消息在签名前首先通过MD5计算，生成128位的消息摘要 digest。

(2) 对摘要作RSA计算。用加密算法，采用签名者的私钥加密消息摘要，得到加密后的字符串。加密算法中使用的加密块为01类型。

2 验证签名算法

验证签名算法包括两步：RSA解密得签名者的消息摘要，验证者对原消息计算摘要，比较两个消息摘要。验证签名的过程输入为消息，签名者的公钥，签名；输出为验证的结果，即是否是正确的签名。

(1) RSA解密。签名实际是加密的字符串。用3.5所述的解密算法，采用签名者的公钥对这个加密的字符串解密。解密的结果应为128位的消息摘要。在解密过程中，若出现得到的加密块的类型不是01，则解密失败。签名不正确。

(2) 消息摘要计算和比较。验证者对消息用MD5算法重新计算，得到验证者自己的消息摘要。验证者比较解密得到的消息摘要和自己的消息摘要，如果两者相同，则验证成功，可以确认消息的完整性及签名确实为签名者的；否则，验证失败。

三.源代码：

import random
import hashlib
def judge(m, s, n, e):
return m == ''.join([chr(kuaisumi(i, e, n)) for i in s])
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
def kuaisumi(a, n, p):
c = 1
str = bin(n)[2:][::-1]
for item in str:
if item == '1':
c = (c * a) % p
a = (a ** 2) % p
elif item == '0':
a = (a ** 2) % p
return c
def dasushu(w):
while True:
number = random.randint(2 ** (w - 1), 2 ** w - 1) | 1
for i in range(50):
if not ceshisushu(number):
break
if i == 49:
return number
def key():
p = dasushu(512)
q = dasushu(512)
n = p * q
_n = (p - 1) * (q - 1)
while True:
e = random.randint(2, _n - 1)
if gcd(e, _n) == 1:
break
d = euclid(e, _n)
return n, e, d
def ceshisushu(num):
s = num - 1
k = 0
while s % 2 == 0:
s = s // 2
k = k + 1
a = random.randint(2, num)
b = kuaisumi(a, s, num)
if b == 1:
return True
for i in range(k):
if b == num - 1:
return True
else:
b = b * b % num
return False
def euclid(x, n):
r0 = n
r1 = x % n
if r1 == 1:
y = 1
else:
s0 = 1
s1 = 0
t0 = 0
t1 = 1
while r0 % r1 != 0:
q = r0 // r1
r = r0 % r1
r0 = r1
r1 = r
s = s0 - q * s1
s0 = s1
s1 = s
t = t0 - q * t1
t0 = t1
t1 = t
if r == 1:
y = (t + n) % n
return y
def sign(m, n, d):
s = [kuaisumi(ord(i), d, n) for i in m]
return m, s
if __name__ == '__main__':
message = input('请输入原文：').encode('utf-8')
m = hashlib.sha512(message).hexdigest()
n, e, d = key()
m, s = sign(m, n, d)
print('长度：', len(s))
with open('sign.txt', 'w') as f:
f.write(str(s).replace('[', '').replace(']', '').replace(',', '\n').replace(' ', ''))
print('是否成功？', judge(m, s, n, e))

复制代码

四.运行截图：

		自动登录	找回密码
密码			立即注册

信息计算2019级1班3号刘丹丹

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

浏览过的版块