計算機(jī)網(wǎng)絡(luò)安全實(shí)驗(yàn)報告--非對稱密碼算法RSA

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)實(shí)驗(yàn)二 非對稱密碼算法RSA一、實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)際編程了解非對稱密碼算法RSA的加密和解密過程，加深對非對稱密碼算法的認(rèn)識。二、實(shí)驗(yàn)環(huán)境運(yùn)行Windows或Linux操作系統(tǒng)的PC機(jī)，具有g(shù)cc(Linux)、VC(Windows)等C語言編譯環(huán)境。三、實(shí)驗(yàn)內(nèi)容和步驟1)編寫一個程序，隨機(jī)選擇3個較大的數(shù)x、e、n，然后計算xe mod n，記錄程序運(yùn)行時間。實(shí)際中應(yīng)用的素數(shù)為512位，n也就為1024位。這樣的大數(shù)在計算機(jī)上如何表示、如何進(jìn)行運(yùn)算，查閱資料給出簡單說明。RSA依賴大數(shù)運(yùn)算，目前主流RSA算法都建立在512位到1024位的大數(shù)運(yùn)算之上，所

2、以我們在現(xiàn)階段首先需要掌握1024位的大數(shù)運(yùn)算原理。大多數(shù)的編譯器只能支持到64位的整數(shù)運(yùn)算，即我們在運(yùn)算中所使用的整數(shù)必須小于等于64位，即：0xffffffffffffffff也就是，這遠(yuǎn)遠(yuǎn)達(dá)不到RSA的需要，于是需要專門建立大數(shù)運(yùn)算庫來解決這一問題。最簡單的辦法是將大數(shù)當(dāng)作字符串進(jìn)行處理，也就是將大數(shù)用10進(jìn)制字符數(shù)組進(jìn)行表示，然后模擬人們手工進(jìn)行“豎式計算”的過程編寫其加減乘除函數(shù)。但是這樣做效率很低，因?yàn)?024位的大數(shù)其10進(jìn)制數(shù)字個數(shù)就有數(shù)百個，對于任何一種運(yùn)算，都需要在兩個有數(shù)百個元素的數(shù)組空間上做多重循環(huán)，還需要許多額外的空間存放計算的進(jìn)位退位標(biāo)志及中間結(jié)果。當(dāng)然其優(yōu)點(diǎn)是算法

3、符合人們的日常習(xí)慣，易于理解。另一種思路是將大數(shù)當(dāng)作一個二進(jìn)制流進(jìn)行處理，使用各種移位和邏輯操作來進(jìn)行加減乘除運(yùn)算，但是這樣做代碼設(shè)計非常復(fù)雜，可讀性很低，難以理解也難以調(diào)試。(2)計算機(jī)在生成一個隨機(jī)數(shù)時，并不一定就是素數(shù)，因此要進(jìn)行素性檢測。是否有確定的方法判定一個大數(shù)是素數(shù)，要查閱資料，找出目前實(shí)際可行的素數(shù)判定法則，并且比較各自的優(yōu)缺點(diǎn)。所謂素數(shù)，是指除了能被1和它本身整除而不能被其他任何數(shù)整除的數(shù)。根據(jù)素數(shù)的定義，只需用2到N-1去除N，如果都除不盡則N是素數(shù)，結(jié)束知其循環(huán)。由此得算法1。（1） flay=0,i=2. /*flay為標(biāo)志，其初值為0，只要有一個數(shù)除盡，其值變?yōu)?.（

4、2） If n mod i=0 then flay=l else i=i+1/* n mod i是n除以i的余數(shù).（3） If flay=0 and I<=n-1 then(2) else go (4)（4） If flay=0 then write“n是素數(shù)?！眅lse write“不是素數(shù)”最壞的情形下，即N是素數(shù)時，算法1需要執(zhí)行N-2次除法，時間復(fù)雜性太大。假設(shè)N桶分解成iXj(i,j是小于N的整數(shù))，則必存在一個因子（1<=i<=int(n)）,這樣只需用2到int(n)去除N即可，于是循環(huán)次數(shù)可以大減小，由此得出算法2算法2（改進(jìn)算法）（1） flag=0,i=2

5、（2） if n mod i then flag=1else i=i+1（3） if flag=0 and i<=int(n) then go(2) else go(4)（4） if flah=0 then write”n是素數(shù)”else write “n不是素數(shù)“。最壞的情形下，即當(dāng)N是紗數(shù)時1需要執(zhí)行int(n)-1次除法。雖然算法2比算法1確是快了不小，但有重復(fù)計算，如果用2去除N時若不盡則用2的倍數(shù)去除N也除不盡，于是只要2除不盡，2的倍數(shù)就不用去除，這樣可以減少除法次數(shù)，由此得出算法3（1）for(i=2;int(n);i+)marki=0/*mark是標(biāo)記其初值為0，只要它的

6、因子除不盡其值變?yōu)?。（2）i=2,flag=0(3)while(flag=0and i<=int(n) If marki=0Then If n mod i=0 Then flag=1 Else S=i+i While s<int(n) Marks=1 S=s+ii=i+1(4)if flag=0 then write”n是素數(shù)。Else write “N不是素數(shù)?！霸撍惴ǖ貜?fù)次數(shù)仍為int(n)次，但是篩法算法在執(zhí)行過程中，每次都篩去許多數(shù)，使下一次迭代時不用再除法而只做比較，比較比除法運(yùn)算要簡單得多，因此實(shí)際執(zhí)行速度比算法1，算法2要得多。當(dāng)然，對于素數(shù)的判定還有別的方法，

7、如用概率算法求素數(shù)，但其理論太難，一般情況下很少用。關(guān)于素數(shù)的判定問題還有待發(fā)現(xiàn)簡單更高效的方法。(3)附件中給出了一個密碼算法庫，其中包括各種對稱加密算法、非對稱加密算法、Hash算法和數(shù)字簽名算法。找出其中關(guān)于RSA算法的部分，并且基于標(biāo)準(zhǔn)輸入輸出寫一段用RSA加密文件的程序。程序代碼：#include<iostream>#include "mycrypt.h"using namespace std;int main(void)int err, hash_idx, prng_idx, res;unsigned long l1,l2;unsigned char

8、 pt2128,out1024;rsa_key key;/* register prng/Hash */if (register_prng(&sprng_desc) =-1) printf("Error registering sprng");return EXIT_FAILURE;if (register_hash(&sha1_desc) =-1) printf("Error registering sha1");return EXIT_FAILURE;hash_idx = find_hash("sha1");prn

9、g_idx = find_prng("sprng");/* make an RSA-1024 key */if (err = rsa_make_key(NULL, /* PRNG state */prng_idx,/* PRNG idx */1024/8, /* 1024-bit key */65537,/* we like e=65537 */&key)/* where to store the key */) != CRYPT_OK) printf("rsa_make_key %s", error_to_string(err);return

10、EXIT_FAILURE;FILE *fd1;FILE *fd2;FILE *fd3; fd1=fopen("plaintext1.txt","rb");fd2=fopen("cipertext.txt","wb");int count=0;unsigned char p_buf16;unsigned char tt="TestApp"l1 = sizeof(out);while(true)count=fread(p_buf,sizeof(unsigned char),16,fd1); for(

11、int j=0;j<count;j+)cout<<p_bufj;if (err = rsa_encrypt_key(p_buf,/* data we wish to encrypt */count,/* data is 16 bytes long */out, /* where to store ciphertext */&l1, /* length of ciphertext */tt,/* our lparam for this program */7,/* lparam is 7 bytes long */NULL,/* PRNG state */prng_id

12、x,/* ping idx */hash_idx,/* Hash idx */&key)/* our RSA key */) != CRYPT_OK) printf("rsa_encrypt_key %s", error_to_string(err);return EXIT_FAILURE;fwrite(out,sizeof(unsigned char),l1,fd2);if(count<16)break;count=0; fclose(fd1);fclose(fd2);fd2=fopen("cipertext.txt","rb&

13、quot;);fd3=fopen("plaintext2.txt","wb");unsigned char c_buf128;long l3=sizeof(c_buf); while(true)count=fread(c_buf,sizeof(unsigned char),128,fd2);if(count=0)break;l2=sizeof(pt2);if(err=rsa_decrypt_key(c_buf,/*encrypted data*/l3,/*length of ciphertext*/pt2,/*where to put plaintext*/&l2,/*plaintext length*/tt,/*lparam for this program*/7,/*lparam is 7 bytes long*/NULL,/*PRNG state*/prng_idx,/*prng idx*/hash_idx,/*hash idx*/&res,/*validity of data*/&key)/*our RSA key*/) != CRYPT_OK)printf("err=rsa_decrypt_key %s",error_to_string(err);return EX