信息计算2019级2班6号李靓

李靓 · 发表于 2022-5-31 11:29:10

本帖最后由李靓于 2022-5-31 11:34 编辑

RSA加密、解密以及签名

1.RSA加解密
秘钥生成：选择两个互异的大素数 $p$ 和 $q$ ，二者保密。计算 $n=pq$ ，公开 $n$ 。 $\phi(n) = (p-1)(q-1)$ ， $\phi(n)$ 保密，选择一个公开的随机数 $e(0< e < \phi(n))$ ，满足 $gcd(e, \phi(n))=1$ ，计算 $d=e^{-1}mod \phi(n)$ ， $d$ 保密。此时，公钥为 $(e,n)$ ，私钥为 $(d,n)或(d,p,q)$ 。
加密：加密结果 $C=M^emodn$ ，已知条件 $M < n$ ，公钥 $(e,n)$ 。
解密：解密结果 $M=C^dmodn$ ，已知条件 $C$ ，私钥 $(d,n)$ 。

2.RSA签名验签

选取整数 $n=pq$ ，消息空间与签名空间均为整数空间，即 $M=A=Z_n$ ，定义秘钥集合 $K=\{ (n,e),(p,q,d)|n=pd,d\times e \equiv 1mod \phi(n)\}$ 。

对 $x \in M$ ，Bob要对 $x$ 签名，取 $k \in K$ ， $sig_k(x)=x^dmodn=y$ ，于是验证等式 $x=y^emodn$ 是否成立。

3.源代码

package InformationScience;
import java.security.*;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.PKCS8EncodedKeySpec;
import java.security.spec.X509EncodedKeySpec;
import java.util.Base64;
/**
* @ClassName TestSignature
* @Author king
* @Date 2020/3/27 10:09
* @Version V1.0
**/
public class TestSignature {
public static void main(String[] args) throws Exception {
KeyPair keyPair = generateKeyPair();
String privateKey = Base64.getEncoder().encodeToString(keyPair.getPrivate().getEncoded());
String publicKey = Base64.getEncoder().encodeToString(keyPair.getPublic().getEncoded());
String data = "data will be signature";
String signatureData = signature(data, privateKey);
boolean verify = verify(signatureData, data, publicKey);
System.out.println(verify);
}
/**
* @return java.security.KeyPair
* @Description 生成秘钥对
* @Date 2020/3/27 10:12
**/
public static KeyPair generateKeyPair() throws NoSuchAlgorithmException {
KeyPairGenerator rsa = KeyPairGenerator.getInstance("RSA");
rsa.initialize(2048);
return rsa.generateKeyPair();
}
/**
* @return String
* @Author wangwei
* @Description 加签
* @Date 2020/3/27 10:18
**/
public static String signature(String data, String privateKey) throws Exception {
Signature signature = Signature.getInstance("MD5withRSA");
signature.initSign(generatePrivateKey(privateKey));
signature.update(data.getBytes());
byte[] sign = signature.sign();
return Base64.getEncoder().encodeToString(sign);
}
/**
* @return java.security.PrivateKey
* @Description 根据String生成privateKey
* @Date 2020/3/27 10:30
* @Param [string]
**/
public static PrivateKey generatePrivateKey(String string) throws NoSuchAlgorithmException, InvalidKeySpecException {
KeyFactory keyFactory = KeyFactory.getInstance("RSA");
byte[] decode = Base64.getDecoder().decode(string.getBytes());
PKCS8EncodedKeySpec pkcs8EncodedKeySpec = new PKCS8EncodedKeySpec(decode);
return keyFactory.generatePrivate(pkcs8EncodedKeySpec);
}
/**
* @return java.security.PublicKey
* @Description 根据String生成PublicKey
* @Date 2020/3/27 10:42
* @Param [string]
**/
public static PublicKey generatePublicKey(String string) throws NoSuchAlgorithmException, InvalidKeySpecException {
KeyFactory keyFactory = KeyFactory.getInstance("RSA");
byte[] decode = Base64.getDecoder().decode(string.getBytes());
X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(decode);
return keyFactory.generatePublic(x509EncodedKeySpec);
}
/**
* @return boolean
* @Description 校验数据是否正确
* @Date 2020/3/27 10:42
* @Param [signatureData, data, publicKey]
**/
public static boolean verify(String signatureData, String data, String publicKey) throws InvalidKeySpecException, NoSuchAlgorithmException, InvalidKeyException, SignatureException {
PublicKey publicKey1 = generatePublicKey(publicKey);
Signature signature = Signature.getInstance("MD5withRSA");
signature.initVerify(publicKey1);
signature.update(data.getBytes());
return signature.verify(Base64.getDecoder().decode(signatureData));
}
}

复制代码

4.运行结果：

李靓 · 发表于 2022-5-31 14:47:59

本帖最后由李靓于 2022-5-31 14:51 编辑

ECC椭圆曲线上公钥密码

1.ECC公私钥对生成
（1）选择一个椭圆曲线 E:y2 =x3 +ax+b(mod p), 构造一个椭圆群Ep(a ，b)
（2）在Ep(a,b) 中挑选生成元点G=(x1 ，y1) ，G 应使得满足nG ＝ O 的最小的n 是一个非常大的素数.
（3）选择一个小于n 的整数nA 作为其私钥，然后产生其公钥PA＝nAG ；
注：公开的信息： (E，G，n，PA)
|Ep|表示椭圆群Ep(a，b)的元素个数，n是|Ep|的素因子。

2.ECC加密算法
2.1发送方签名
1)选择一个随机的key kE 0<kE<n
2)计算 R = kE A
3)令 r ≡ x R (mod p) ,即 r为R的x坐标对p求模
4)计算 s ≡ ( h ( x ) + d ⋅ r ) k E^ − 1 ( mod q)
则生成的 ( r , s ) 就是数字签名。之后发送方将 (s,(r, s)) 发送给接收方

2.2接收方验证
1)计算 u 1 ≡ s^−1⋅h(x)(mod q)
2)计算 u 2 ≡ s−1⋅r(mod q)
3)计算 P = u 1 A + u 2 B
4)进行验证
x P = {≡ r (mod q ) → 签名有效
/≡ r (mod q) → 签名无效
}
这里的− 1 表示在模运算中求逆，在Zp中，一个数a与它的逆 a^−1满足 a⋅a−1≡1(mod p)

3.源代码

#include <stdio.h>
#include <math.h>
int xy[22];
#define N 23
#define A 1
//#define M 29
#define a1 1
#define b1 4
typedef struct point{
int x;
int y;
}Point;
typedef struct ecc{
struct point p[100];
int len;
}ECCPoint;
typedef struct generator{
Point p;
int p_class;
}GENE_SET;
ECCPoint eccPoint;
Point mul(Point p1,Point p2);
Point add_two_points(Point p1,Point p2);
GENE_SET geneSet[100];
int geneLen;
//判断平方根是否为整数
int int_sqrt(int s)
{
int temp;
temp=(int)sqrt(s);//转为整型
if(temp*temp==s)
{
return temp;
}else{
return -1;
}
}
//取模函数
int mod_p(int s)
{
int i; //保存s/p的倍数
int result; //模运算的结果
i = s / N;
result = s - i * N;
if (result >= 0)
{
return result;
}
else
{
return result + N;
}
}
//打印点集
void print()
{
int i;
int len=eccPoint.len;
printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n",len+1);
for(i=0;i<len;i++)
{
if(i % 8==0)
{
printf("\n");
}
printf("(%2d,%2d)\t",eccPoint.p[i].x,eccPoint.p[i].y);
}
printf("\n");
}
//task1:求出椭圆曲线上所有点
void get_all_points()
{
int i=0;
int j=0;
int s,y=0;
int n=0,q=0;
int modsqrt=0;
int flag=0;
if ( a1 * a1 * a1 + b1 * b1+4 != 0)
{
for(i=0;i<=N-1;i++)
{
flag=0;
n=1;
y=0;
s= i * i * i + a1 * i + b1;
while(s<0)
{
s+=N;
}
s=mod_p(s);
modsqrt=int_sqrt(s);
if(modsqrt!=-1)
{
flag=1;
y=modsqrt;
}else{
while(n<=N-1)
{
q=s+n*N;
modsqrt=int_sqrt(q);
if(modsqrt!=-1)
{
y=modsqrt;
flag=1;
break;
}
flag=0;
n++;
}
}
if(flag==1)
{
eccPoint.p[j].x=i;
eccPoint.p[j].y=y;
j++;
if(y!=0)
{
eccPoint.p[j].x=i;
eccPoint.p[j].y=(N-y) % N;
j++;
}
}
}
eccPoint.len=j;//点集个数
print(); //打印点集
}
}
//task3:求生成元以及阶
void get_generetor_class()
{
int i,j=0;
int count=1;
Point p1,p2;
get_all_points();
printf("\n**********************************输出生成元以及阶：*************************************\n");
for(i=0;i<eccPoint.len;i++)
{
count=1;
p1.x=p2.x=eccPoint.p[i].x;
p1.y=p2.y=eccPoint.p[i].y;
while(1)
{
p2=add_two_points(p1,p2);
if(p2.x==-1 && p2.y==-1)
{
break;
}
count++;
if(p2.x==p1.x)
{
break;
}
}
count++;
if(count<=eccPoint.len+1)
{
geneSet[j].p.x=p1.x;
geneSet[j].p.y=p1.y;
geneSet[j].p_class=count;
printf("(%d,%d)--->>%d\t",geneSet[j].p.x,geneSet[j].p.y,geneSet[j].p_class);
j++;
if(j % 6 ==0){
printf("\n");
}
}
geneLen=j;
}
}
// 求 a mod b 的逆元
void exGcd(int a, int b) {
if (b == 0) {
xy[0] = 1;
xy[1] = 0;
} else {
exGcd(b, a % b);
int x = xy[0];
xy[0] = xy[1];
xy[1] = x - (a / b) * xy[1];
}
}
int calculate3(int y,int k,int p){
int l=1;
for(int i = 0;i<k;i++){
l=l*y;
l=l%p;
}
return l;
}
Point eccmutiply(int n,Point p){
int a,b,l,k,m;
a=p.x;
b=p.y;
for(int i = 0;i<n-1;i++){
if(a==p.x&&b==p.y){
exGcd(2*p.y,N);
k=xy[0];
if(k<0)k=k+N;
printf("逆元=%d\n",k);
l=(3*p.x*p.x+A)*k;
l=calculate3(l,1,N);
if(l<0){
l=l+N;
}
}else{
exGcd(a-p.x+N,N);
k=xy[0];
if(k<0)k=k+N;
printf("else逆元=%d\n",k);
l=(b-p.y)*k;
l=calculate3(l,1,N);
if(l<0){
l=l+N;
}
printf("l=%d\n",l);
}
m=p.x;
a=l*l-a-p.x;
a=calculate3(a,1,N);
if(a<0){
a=a+N;
}
b=l*(m-a)-p.y;
b=calculate3(b,1,N);
if(b<0){
b=b+N;
}
printf("%d(a,b)=(%d,%d)\n",i+2,a,b);
//if(a==4&&b==5)break;
}
Point p3;
p3.x=a;
p3.y=b;
return p3;
}
Point mul(Point p1,Point p2){
int k,l;
exGcd(p2.x-p1.x+N,N);
k=xy[0];
if(k<0)k=k+N;
//printf("else逆元=%d\n",k);
l=(p2.y-p1.y)*k;
l=calculate3(l,1,N);
if(l<0){
l=l+N;
}
//printf("l=%d\n",l);
Point p3;
p3.x=l*l-p1.x-p2.x;
p3.x=calculate3(p3.x,1,N);
if(p3.x<0)p3.x=p3.x+N;
p3.y=l*(p1.x-p3.x)-p1.y;
p3.y=calculate3(p3.y,1,N);
if(p3.y<0)p3.y=p3.y+N;
return p3;
}
//求b关于n的逆元
int inverse(int n,int b)
{
int q,r,r1=n,r2=b,t,t1=0,t2=1,i=1;
while(r2>0)
{
q=r1/r2;
r=r1%r2;
r1=r2;
r2=r;
t=t1-q*t2;
t1=t2;
t2=t;
}
if(t1>=0)
return t1%n;
else{
while((t1+i*n)<0)
i++;
return t1+i*n;
}
}
//两点的加法运算
Point add_two_points(Point p1,Point p2)
{
long t;
int x1=p1.x;
int y1=p1.y;
int x2=p2.x;
int y2=p2.y;
int tx,ty;
int x3,y3;
int flag=0;
//求
if((x2==x1)&& (y2==y1) )
{
//相同点相加
if(y1==0)
{
flag=1;
}else{
t=(3*x1*x1+a1)*inverse(N,2*y1) % N;
}
//printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
}else{
//不同点相加
ty=y2-y1;
tx=x2-x1;
while(ty<0)
{
ty+=N;
}
while(tx<0)
{
tx+=N;
}
if(tx==0 && ty !=0)
{
flag=1;
}else{
t=ty*inverse(N,tx) % N;
}
}
if(flag==1)
{
p2.x=-1;
p2.y=-1;
}else{
x3=(t*t-x1-x2) % N;
y3=(t*(x1-x3)-y1) % N;
//使结果在有限域GF(P)上
while(x3<0)
{
x3+=N;
}
while(y3<0)
{
y3+=N;
}
p2.x=x3;
p2.y=y3;
}
return p2;
}
//task2:倍点运算的递归算法
Point timesPiont(int k,Point p0)
{
if(k==1){
return p0;
}
else if(k==2){
return add_two_points(p0,p0);
}else{
return add_two_points(p0,timesPiont(k-1,p0));
}
}
main(){
get_generetor_class();
Point p1,p2,p,p4,p5,p6,p7,p8,p9,p10;
int na,k,h,r,s,u1,u2;
printf("\n选择生成元:");
scanf("%d%d",&p1.x,&p1.y);
int j=0;
while(j<N){
if(geneSet[j].p.x==p1.x&&geneSet[j].p.y==p1.y){
break;
}
printf("j=%d\n",j);
++j;
}
int M = geneSet[j].p_class;
printf("M=%d",M);
// p1.x=0;
// p1.y=2;
//p.x=20;
//p.y=1;
printf("\n请输入私钥:");
scanf("%d",&na);
p2=eccmutiply(na,p1);
printf("\n公钥为（%d,%d)",p2.x,p2.y);
//p2=mul(p,p1);
//printf("(%d,%d)",p2.x,p2.y);
//签名过程
printf("\n\n输入随机数k:");
scanf("%d",&k);
printf("输入hash:");
scanf("%d",&h);
p4=eccmutiply(k,p1);
r=calculate3(p4.x,1,N);
if(r<0)r=r+N;
s=inverse(M,k)*(h+na*r)%M;
if(s<0)s=s+N;
printf("签名为(%d,%d)\n",r,s);
printf("========================");
//验证过程
u1=h*inverse(M,s)%M;
if(u1<0)u1=u1+M;
u2=r*inverse(M,s)%M;
if(u2<0)u2=u2+M;
printf("u1u2=%d,%d\n",u1,u2);
p5=eccmutiply(u1,p1);
printf("sG=(%d,%d)\n",p5.x,p5.y);
p6=eccmutiply(u2,p2);
printf("HP=(%d,%d)\n",p6.x,p6.y);
p7=add_two_points(p5,p6);
printf("sG+HP=(%d,%d)\n",p7.x,p7.y);
if(calculate3(p7.x,1,N)==r){
printf("通过");
}else{
printf("失败");
}
}

复制代码

4.运行结果

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

信息计算2019级2班6号李靓

本帖子中包含更多资源

本帖子中包含更多资源

浏览过的版块