go语言rsa加解密 rs go
使用RSA公开密钥体制进行加密,若P=2,q=5,求公钥e,私钥d,给出明文m=2的加解密过程
n=P*q=10
创新互联主要从事网页设计、PC网站建设(电脑版网站建设)、wap网站建设(手机版网站建设)、成都响应式网站建设公司、程序开发、网站优化、微网站、小程序开发等,凭借多年来在互联网的打拼,我们在互联网网站建设行业积累了丰富的成都网站制作、成都网站建设、外贸营销网站建设、网站设计、网络营销经验,集策划、开发、设计、营销、管理等多方位专业化运作于一体。
n的欧拉值=(p-1)*(q-1)=4
e满足1en的欧拉值,且 gcd(n的欧拉值,e)=1 所以 e只能为3
d*e=1 mod n的欧拉值 即 d*3= 1 mod 4 所以d可以取3
{3,10}为公钥 {310}为密钥
加密:
c=m^e mod n =2^3 mod 10 =8
解密
m=c^d mod n =8^3mod 10 = 2
如何利用OpenSSL库进行RSA加密和解密
#includestdio.h
#includestdlib.h
#includestring.h
#includeopenssl/rsa.h
#includeopenssl/engine.h
int main(int argc, char* argv[])
{
printf("openssl_test begin\n");
RSA* rsa=NULL;
char originstr[]="hello\n"; //这是我们需要加密的原始数据
//allocate RSA structure,首先需要申请一个RSA结构题用于存放生成的公私钥,这里rsa就是这个结构体的指针
rsa = RSA_new();
if(rsa==NULL)
{
printf("RSA_new failed\n");
return -1;
}
//generate RSA keys
BIGNUM* exponent;
exponent = BN_new(); //生成RSA公私钥之前需要选择一个奇数(odd number)来用于生成公私钥
if(exponent ==NULL)
{
printf("BN_new failed\n");
goto FAIL1;
}
if(0==BN_set_word(exponent,65537)) //这里选择奇数65537
{
printf("BN_set_word failed\n");
goto FAIL1;
}
//这里modulus的长度选择4096,小于1024的modulus长度都是不安全的,容易被破解
if(0==RSA_generate_key_ex(rsa,4096,exponent,NULL))
{
printf("RSA_generate_key_ex failed\n");
goto FAIL;
}
char* cipherstr = NULL;
//分配一段空间用于存储加密后的数据,这个空间的大小由RSA_size函数根据rsa算出
cipherstr = malloc(RSA_size(rsa));
if(cipherstr==NULL)
{
printf("malloc cipherstr buf failed\n");
goto FAIL1;
}
//下面是实际的加密过程,最后一个参数padding type,有以下几种。
/*
RSA_PKCS1_PADDINGPKCS #1 v1.5 padding. This currently is the most widely used mode.
RSA_PKCS1_OAEP_PADDING
EME-OAEP as defined in PKCS #1 v2.0 with SHA-1, MGF1 and an empty encoding parameter. This mode is recommended for all new applications.
RSA_SSLV23_PADDING
PKCS #1 v1.5 padding with an SSL-specific modification that denotes that the server is SSL3 capable.
RSA_NO_PADDING
Raw RSA encryption. This mode should only be used to implement cryptographically sound padding modes in the application code. Encrypting user data directly with RSA is insecure.
*/
//这里首先用公钥进行加密,选择了RSA_PKCS1_PADDING
if(RSA_size(rsa)!=RSA_public_encrypt(strlen(originstr)+1,originstr,cipherstr,rsa,RSA_PKCS1_PADDING))
{
printf("encryption failure\n");
goto FAIL2;
}
printf("the original string is %s\n",originstr);
printf("the encrypted string is %s\n",cipherstr);
//Now, let's decrypt the string with private key
//下面来用私钥解密,首先需要一个buffer用于存储解密后的数据,这个buffer的长度要足够(小于RSA_size(rsa))
//这里分配一个长度为250的字符数组,应该是够用的。
char decrypted_str[250];
int decrypted_len;
if(-1=(decrypted_len=RSA_private_decrypt(256,cipherstr,decrypted_str,rsa,RSA_PKCS1_PADDING)))
{
printf("decryption failure\n");
goto FAIL2;
}
printf("decrypted string length is %d,decryped_str is %s\n",decrypted_len,decrypted_str);
FAIL2:
free(cipherstr);
FAIL1:
BN_free(exponent);
FAIL:
RSA_free(rsa);
return 0;
}
以上是源代码,下面使用下面的编译命令在源码所在路径下生成可执行文件
gcc *.c -o openssl_test -lcrypto -ldl -L/usr/local/ssl/lib -I/usr/local/ssl/include
其中,-lcrypto和-ldl是必须的,前者是OpenSSL中的加密算法库,后者是用于成功加载动态库。
rsa解密错误
RSA解密错误,可能是数据填充方面的问题。RSA是一种块加密的算法,所以对于明文需要将他们分成固定的块长度,考虑到输入的数据长度的问题,所以加解密的填充有好几种:1无填充,就是直接对明文进行加密2PKCS1。将数据长度分成密钥长度-11byte,比如密钥是1024bit,那么长度就是1024/8-11=117bytes,具体的格式:先填0,2,然后随机生成其他的byte,后面才是真正的数据3PKCS1_OAEP将数据长度分成密钥长度-41byte,比如密钥是1024bit,那么长度就是1024/8-41=77bytes,先填0,随机或者是固定的测试向量加20个bytes,然后加20个数字签名的数据,最后才是数据4SSLV23,将数据长度分成密钥长度-11byte,比如密钥是1024bit,那么长度就是1024/8-11=117bytes,具体的格式:先填0,2,填入8个3,填入一个'\0',最后才是真正的数据。
CTF常见RSA相关问题的解决(复现)
本文参考 为对其知识进行掌握,写此文章来梳理和加深记忆
前言:理解基本概念,本文将每种攻击方式实现方法提炼成了一个函数,便于理解原理也可以直接调用。
基础:
RSA概要:
在开始前可以通过 《RSA算法详解》 这篇文章了解关于RSA的基础知识,包括加解密方法,算法原理和可行性证明等。(特详细)
应用流程:
1.选取两个较大的互不相等的质数p和q 计算n =p q。
2.计算phi =(p-1) (q-1)。
3.选取任意的e,使得e满足1ephi 且 gcd(e,phi) ==1 .
4.计算e关于phi的模逆元d,即d满足(e*d)%phi ==1.
5.加解密:c=(m^e)%n ,m =(c^d)%n.其中m为明文,c为密文 (n,e)为公钥,d为私钥,要求0=mn.
求模逆可直接利用gmpy2库。如 import gmpy2 print gmpy2.invert(47,30) 可求得47模30的逆为23。
扩展欧几里得算法基于欧几里得算法,能够求出使得 ax+by=gcd(a,b) 的一组x,y。
常见攻击方式实践
准备工具
python gmpy2库 libnum库
yafu
RSATool2v17.exe
RSA解密
若已知私钥d,则可以直接解密:m=pow(c,d,n).
若已知质数p和q,则通过依次计算欧拉函数值phi、私钥d可解密。简易实现如下:
在选取加密指数e时要求phi,e互质,也就是gcd(phi,e)==1 ,如果不满足是无法直接解密的。
SCTF2018的Crypto - a number problem,题目是: x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259 tell me the smallest answer of x
其中n=3436415358139016629092568198745009225773259 可以直接分解得到p,q,出phi=(p-1)*(q-1) ,然后惊奇地发现gcd(phi,33)==3 。这时如果对加密过程比较熟悉的话,就可以想到实际上公钥e=11 ,明文是m=x^3 ,应该先求出m。然后再爆破x。
n2,n3已知,利用共模攻击得到n1,由gcd(n1,n2)==p1 分解n1,n2,就可解密得到两部分msg,拼接即可。
小明文攻击
适用情况:e较小,一般为3。
公钥e很小,明文m也不大的话,于是 m^e=k*n+m 中的的k值很小甚至为0,爆破k或直接开三次方即可。Python实现:
例子:Extremely hard RSA
题目提供的n是4096位的,e=3。
Rabin加密中的N可被分解
适用情况:e==2
Rabin加密是RSA的衍生算法,e==2是Rabin加密典型特征,可以百度或阅读 以了解到详细的说明,这里只关注解密方法。一般先通过其他方法分解得到p,q,然后解密。
Python实现:
函数返回四个数,这其中只有一个是我们想要的明文,需要通过其他方式验证,当然CTF中显然就是flag字眼了。
Wiener’s Attack
适用情况:e过大或过小。
工具:
在e过大或过小的情况下,可使用算法从e中快速推断出d的值。详细的算法原理可以阅读: 低解密指数攻击 。
例子:2018强网杯nextrsa-Level2
**私钥文件修复
适用情况:提供破损的私钥文件。 **
参考 修复存储私钥的文件,得到p和q。
**私钥修复
Python 脚本:**
从缺失的私钥中,我们可以分析出各部分数据代表的数字。
改动原脚本中的各部分内容即可恢复出私钥,大致算法为:
**LSB Oracle Attack
适用情况:可以选择密文并泄露最低位。 **
在一次RSA加密中,明文为m,模数为n,加密指数为e,密文为c。我们可以构造出 c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n , 因为m的两倍可能大于n,所以经过解密得到的明文是 m'=(2*m)%n 。我们还能够知道 m' 的最低位 lsb 是1还是0。 因为n是奇数,而 2*m 是偶数,所以如果 lsb 是0,说明 (2*m)%n 是偶数,没有超过n,即 mn/2.0 ,反之则 mn/2.0 。举个例子就能明白 2%3=2 是偶数,而 4%3=1 是奇数。以此类推,构造密文 c"=(4^e)*c)%n 使其解密后为 m"=(4*m)%n ,判断 m" 的奇偶性可以知道 m 和 n/4 的大小关系。所以我们就有了一个二分算法,可以在对数时间内将m的范围逼近到一个足够狭窄的空间。
更多信息可参考: RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。
Python实现:
分享题目:go语言rsa加解密 rs go
文章地址:http://myzitong.com/article/hjgdhc.html