go語(yǔ)言rsa加解密 rs go

使用RSA公開(kāi)密鑰體制進(jìn)行加密,若P=2,q=5,求公鑰e,私鑰d,給出明文m=2的加解密過(guò)程

n=P*q=10

創(chuàng)新互聯(lián)主要從事網(wǎng)頁(yè)設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、成都響應(yīng)式網(wǎng)站建設(shè)公司、程序開(kāi)發(fā)、網(wǎng)站優(yōu)化、微網(wǎng)站、小程序開(kāi)發(fā)等，憑借多年來(lái)在互聯(lián)網(wǎng)的打拼，我們?cè)诨ヂ?lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營(yíng)銷(xiāo)經(jīng)驗(yàn)，集策劃、開(kāi)發(fā)、設(shè)計(jì)、營(yíng)銷(xiāo)、管理等多方位專(zhuān)業(yè)化運(yùn)作于一體。

n的歐拉值=(p-1)*(q-1)=4

e滿(mǎn)足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庫(kù)進(jìn)行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";???//這是我們需要加密的原始數(shù)據(jù)

//allocate?RSA?structure，首先需要申請(qǐng)一個(gè)RSA結(jié)構(gòu)題用于存放生成的公私鑰，這里rsa就是這個(gè)結(jié)構(gòu)體的指針

rsa?=?RSA_new();

if(rsa==NULL)

{

printf("RSA_new?failed\n");??????????

return?-1;

}

//generate?RSA?keys

BIGNUM*?exponent;

exponent?=?BN_new();????????//生成RSA公私鑰之前需要選擇一個(gè)奇數(shù)（odd?number）來(lái)用于生成公私鑰

if(exponent?==NULL)

{

printf("BN_new?failed\n");?

goto?FAIL1;

}

if(0==BN_set_word(exponent,65537))????//這里選擇奇數(shù)65537

{

printf("BN_set_word?failed\n");?

goto?FAIL1;

}

//這里modulus的長(zhǎng)度選擇4096，小于1024的modulus長(zhǎng)度都是不安全的，容易被破解

if(0==RSA_generate_key_ex(rsa,4096,exponent,NULL))??

{

printf("RSA_generate_key_ex?failed\n");?

goto?FAIL;??????

}

char*?cipherstr?=?NULL;

//分配一段空間用于存儲(chǔ)加密后的數(shù)據(jù)，這個(gè)空間的大小由RSA_size函數(shù)根據(jù)rsa算出

cipherstr?=?malloc(RSA_size(rsa));?

if(cipherstr==NULL)

{

printf("malloc?cipherstr?buf?failed\n");

goto?FAIL1;

}

//下面是實(shí)際的加密過(guò)程，最后一個(gè)參數(shù)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.

*/??

//這里首先用公鑰進(jìn)行加密，選擇了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

//下面來(lái)用私鑰解密，首先需要一個(gè)buffer用于存儲(chǔ)解密后的數(shù)據(jù)，這個(gè)buffer的長(zhǎng)度要足夠（小于RSA_size(rsa)）

//這里分配一個(gè)長(zhǎng)度為250的字符數(shù)組，應(yīng)該是夠用的。

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;

}

以上是源代碼，下面使用下面的編譯命令在源碼所在路徑下生成可執(zhí)行文件

gcc *.c -o openssl_test -lcrypto -ldl -L/usr/local/ssl/lib -I/usr/local/ssl/include

其中，-lcrypto和-ldl是必須的，前者是OpenSSL中的加密算法庫(kù)，后者是用于成功加載動(dòng)態(tài)庫(kù)。

rsa解密錯(cuò)誤

RSA解密錯(cuò)誤,可能是數(shù)據(jù)填充方面的問(wèn)題。RSA是一種塊加密的算法，所以對(duì)于明文需要將他們分成固定的塊長(zhǎng)度，考慮到輸入的數(shù)據(jù)長(zhǎng)度的問(wèn)題，所以加解密的填充有好幾種：1無(wú)填充，就是直接對(duì)明文進(jìn)行加密2PKCS1。將數(shù)據(jù)長(zhǎng)度分成密鑰長(zhǎng)度-11byte，比如密鑰是1024bit，那么長(zhǎng)度就是1024/8-11=117bytes，具體的格式：先填0，2，然后隨機(jī)生成其他的byte，后面才是真正的數(shù)據(jù)3PKCS1_OAEP將數(shù)據(jù)長(zhǎng)度分成密鑰長(zhǎng)度-41byte，比如密鑰是1024bit，那么長(zhǎng)度就是1024/8-41=77bytes，先填0，隨機(jī)或者是固定的測(cè)試向量加20個(gè)bytes，然后加20個(gè)數(shù)字簽名的數(shù)據(jù)，最后才是數(shù)據(jù)4SSLV23，將數(shù)據(jù)長(zhǎng)度分成密鑰長(zhǎng)度-11byte，比如密鑰是1024bit，那么長(zhǎng)度就是1024/8-11=117bytes，具體的格式：先填0，2，填入8個(gè)3，填入一個(gè)'\0'，最后才是真正的數(shù)據(jù)。

CTF常見(jiàn)RSA相關(guān)問(wèn)題的解決（復(fù)現(xiàn)）

本文參考 為對(duì)其知識(shí)進(jìn)行掌握，寫(xiě)此文章來(lái)梳理和加深記憶

前言：理解基本概念，本文將每種攻擊方式實(shí)現(xiàn)方法提煉成了一個(gè)函數(shù)，便于理解原理也可以直接調(diào)用。

基礎(chǔ)：

RSA概要：

在開(kāi)始前可以通過(guò) 《RSA算法詳解》 這篇文章了解關(guān)于RSA的基礎(chǔ)知識(shí)，包括加解密方法，算法原理和可行性證明等。（特詳細(xì)）

應(yīng)用流程：

1.選取兩個(gè)較大的互不相等的質(zhì)數(shù)p和q 計(jì)算n =p q。

2.計(jì)算phi =（p-1） （q-1）。

3.選取任意的e，使得e滿(mǎn)足1ephi 且 gcd(e,phi) ==1 .

4.計(jì)算e關(guān)于phi的模逆元d，即d滿(mǎn)足（e*d）%phi ==1.

5.加解密：c=(m^e)%n ,m =(c^d)%n.其中m為明文，c為密文 （n,e）為公鑰，d為私鑰，要求0=mn.

求模逆可直接利用gmpy2庫(kù)。如 import gmpy2 print gmpy2.invert(47,30) 可求得47模30的逆為23。

擴(kuò)展歐幾里得算法基于歐幾里得算法，能夠求出使得 ax+by=gcd(a,b) 的一組x,y。

常見(jiàn)攻擊方式實(shí)踐

準(zhǔn)備工具

python gmpy2庫(kù) libnum庫(kù)

yafu

RSATool2v17.exe

RSA解密

若已知私鑰d，則可以直接解密：m=pow(c,d,n).

若已知質(zhì)數(shù)p和q,則通過(guò)依次計(jì)算歐拉函數(shù)值phi、私鑰d可解密。簡(jiǎn)易實(shí)現(xiàn)如下：

在選取加密指數(shù)e時(shí)要求phi，e互質(zhì)，也就是gcd(phi,e)==1 ，如果不滿(mǎn)足是無(wú)法直接解密的。

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) ，然后驚奇地發(fā)現(xiàn)gcd(phi,33)==3 。這時(shí)如果對(duì)加密過(guò)程比較熟悉的話(huà)，就可以想到實(shí)際上公鑰e=11 ，明文是m=x^3 ，應(yīng)該先求出m。然后再爆破x。

n2，n3已知，利用共模攻擊得到n1，由gcd(n1,n2)==p1 分解n1，n2，就可解密得到兩部分msg，拼接即可。

小明文攻擊

適用情況：e較小，一般為3。

公鑰e很小，明文m也不大的話(huà)，于是 m^e=k*n+m 中的的k值很小甚至為0，爆破k或直接開(kāi)三次方即可。Python實(shí)現(xiàn)：

例子：Extremely hard RSA

題目提供的n是4096位的，e=3。

Rabin加密中的N可被分解

適用情況：e==2

Rabin加密是RSA的衍生算法，e==2是Rabin加密典型特征，可以百度或閱讀 以了解到詳細(xì)的說(shuō)明，這里只關(guān)注解密方法。一般先通過(guò)其他方法分解得到p，q，然后解密。

Python實(shí)現(xiàn)：

函數(shù)返回四個(gè)數(shù)，這其中只有一個(gè)是我們想要的明文，需要通過(guò)其他方式驗(yàn)證，當(dāng)然CTF中顯然就是flag字眼了。

Wiener’s Attack

適用情況：e過(guò)大或過(guò)小。

工具：

在e過(guò)大或過(guò)小的情況下，可使用算法從e中快速推斷出d的值。詳細(xì)的算法原理可以閱讀： 低解密指數(shù)攻擊 。

例子：2018強(qiáng)網(wǎng)杯nextrsa-Level2

**私鑰文件修復(fù)

適用情況：提供破損的私鑰文件。 **

參考 修復(fù)存儲(chǔ)私鑰的文件，得到p和q。

**私鑰修復(fù)

Python 腳本：**

從缺失的私鑰中，我們可以分析出各部分?jǐn)?shù)據(jù)代表的數(shù)字。

改動(dòng)原腳本中的各部分內(nèi)容即可恢復(fù)出私鑰，大致算法為：

**LSB Oracle Attack

適用情況：可以選擇密文并泄露最低位。 **

在一次RSA加密中，明文為m，模數(shù)為n，加密指數(shù)為e，密文為c。我們可以構(gòu)造出 c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n ， 因?yàn)閙的兩倍可能大于n，所以經(jīng)過(guò)解密得到的明文是 m'=(2*m)%n 。我們還能夠知道 m' 的最低位 lsb 是1還是0。 因?yàn)閚是奇數(shù)，而 2*m 是偶數(shù)，所以如果 lsb 是0，說(shuō)明 (2*m)%n 是偶數(shù)，沒(méi)有超過(guò)n，即 mn/2.0 ，反之則 mn/2.0 。舉個(gè)例子就能明白 2%3=2 是偶數(shù)，而 4%3=1 是奇數(shù)。以此類(lèi)推，構(gòu)造密文 c"=(4^e)*c)%n 使其解密后為 m"=(4*m)%n ，判斷 m" 的奇偶性可以知道 m 和 n/4 的大小關(guān)系。所以我們就有了一個(gè)二分算法，可以在對(duì)數(shù)時(shí)間內(nèi)將m的范圍逼近到一個(gè)足夠狹窄的空間。

更多信息可參考： RSA Least-Significant-Bit Oracle Attack 和 RSA least significant bit oracle attack 。

Python實(shí)現(xiàn)：

網(wǎng)站欄目：go語(yǔ)言rsa加解密 rs go
本文來(lái)源：http://m.kartarina.com/article42/hjgdhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、域名注冊(cè)、用戶(hù)體驗(yàn)、商城網(wǎng)站、網(wǎng)站導(dǎo)航、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)