程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言:rsa算法原理

C語言:rsa算法原理

編輯:關於C語言

1. 大數的運算原理
   
    RSA算法依賴於大數的運算,目前主流RSA算法都建立在512位到1024位的大數運算之上,所以我們首先需要掌握大數(比如1024位)的運算原理。
   
    大多數的編譯器只能支持到32位(或64位)的整數運算,即我們在運算中所使用的整數必須小於等於32位,即0xFFFFFFFF,這遠遠達不到RSA的需要,於是需要專門建立大數運算庫,來解決這一問題。
   
    最簡單的辦法是將大數當作字符串進行處理,也就是將大數用10進制字符數組進行表示,然後模擬人們手工進行"豎式計算"的過程編寫其加減乘除函數。但是這樣做效率很低。當然其優點是算法符合人們的日常習慣,易於理解。
   
    另一種思路是將大數當作一個二進制流進行處理,使用各種移位和邏輯操作來進行加減乘除運算,但是這樣做代碼設計非常復雜,可讀性很低,難以理解也難以調試。
   
    這裡我們采用了一種介於兩者之間的思路:將大數看作一個N進制數組,對於目前的32位系統而言,N可以取2的32次方,即 0x100000000,假如將一個1024位的大數轉化成0x10000000進制,它就變成了32位,而每一位的取值范圍是0- 0xFFFFFFFF.我們正好可以用一個無符號長整數來表示這一數值。所以1024位的大數就是一個有32個元素的unsigned long數組。而且0x100000000進制的數組排列與2進制流對於計算機來說,實際上是一回事,但是我們完全可以針對unsigned long數組進行"豎式計算",而循環規模被降低到了32次之內,並且算法很容易理解。
   
    但考慮到乘法和除法,都要進行擴展才能進行快速的計算(如果把除法變減法而不擴展,速度將慢的無法忍受)。所以我們將N取2的16次方的,即 0xFFFF.每一位用unsigned short來表示,當進行乘除運算時,將short擴展成long,這是編譯器所支持的,所以運算起來,比較快。
   
    2. 大數的各種運算
   
    這些運算都是常見的,同時也是常用的。要實現RSA算法,就必須先實現大數的這些運算。
   
    1) 大數的比較。兩個無符號或有符號的大數進行大小比較。大數和一般整數進行比較。大於,等於,小於,返回值各異,以區別比較結果。
   
    2) 大數的賦值。將一個大數的值,符號等,逐位賦給另一個大數。將一般整數的值,符號等賦給一個大數。
   
    3) 大數的加法。兩個大數從低位到高位逐位相加,要考慮到進位的問題。或大數與一般整數的相加。
   
    4) 大數的減法。兩個大數從低位到高位逐位相減,要考慮到借位的問題。或大數與一般整數的相減。
   
    5) 大數的乘法。兩個大數的乘法,從一個大數的低位到高位,逐位與另一個大數相乘,然後將結果低位對齊相加,要考慮進位,類似於普通的豎式乘法。或大數與一般整數的乘法。
   
    6) 大數的除法。兩個大數的除法,從一個大數的高位到低位,逐步與另一個大數相除,要考慮借位,類似於普通的豎式除法。或大數與一般整數的乘法。
   
    7) 大數的取余。兩個大數的取余,類似於大數的除法,只是當除到底時,返回的是余數而已,也存在借位的問題。或大數於一般整數的取余。
   
    8) 大數的歐氏算法。它是已知大數A、B,求滿足AX≡1 MOD B的X,是最大公約數算法的擴展,同樣用輾轉相除法。再遞歸的過程中,兩個參數都要用到,到要變化的。具體算法請參考源代碼。
   
    9) 大數的蒙氏算法。它是已知大數A、B和C,求X=A^B MOD C的值。要對指數進行逐漸降階,直到變成2次方,也就是轉換成乘法和取余運算。降階的方法和算法的具體過程,請參考相關書籍和源代碼。
   
    10) 大數的最大公約數。求兩個大數的最大公約數,用輾轉相除法。
   
    RSA算法的實現
   
    A. 生成密鑰函數
   
    gChar gGenerateKey(gBigInt *n,gBigInt *e,gBigInt *d);
   
    功能:該函數實現了產生密鑰的功能。先產生兩個隨機的大素數p和q,然後計算n=p×q,隨機產生(或固定)一個大數e,計算d,使得ed≡1 MOD (p-1)(q-1)。
   
    參數:
   
    n:兩個大數的乘積,和e或d聯合構成加密密鑰或解密密鑰。
   
    e:一個大數,作為加密密鑰。
   
    d:一個和e互異的大數,作為解密密鑰。
   
    返回值:1-成功,0-失敗。
   
    B. 數據加密函數
   
    char gEncRSA(unsigned char* indata, unsigned long inlen, gBigInt* e, gBigInt* n,\
   
    unsigned char *outdata, unsigned long* outlen, int flg);
   
    功能:把待加密的明文數據indata,用加密密鑰e和n進行分段加密。
   
    加密後的數據放到提前開辟好的內存outdata中,其長度outlen不得小於((inlen+k-12)/(k-11))*k,這裡k為n的位數。
   
    參數:
   
    indata:指向明文數據的指針。
   
    Inlen:傳入數據的長度,即明文數據的長度。
   
    e和n:兩個大數,作為加密密鑰。
   
    Outdata:存放加密後密文數據的指針。
   
    Outlen:傳入outdata的長度,傳出數據的長度,即密文數據的長度。
   
    Flg:公鑰加密或私鑰加密的標志,g_PUBLIC-公鑰,g_PRIVATE-私鑰。
   
    返回值:1-成功,0-失敗。
   
    C. 數據解密函數
   
    char gDecRSA(unsigned char* indata, unsigned long inlen, gBigInt* d, gBigInt* n,\
   
    unsigned char *outdata, unsigned long* outlen, int flg);
   
    功能:把待解密的密文數據indata,用解密密鑰e和n進行分段解密。
   
    解密後的數據放到提前開辟好的內存outdata中,其長度outlen不得小於(inlen)*k/(k-11),
   
    這裡k為n的位數。
   
    參數:
   
    indata:指向密文數據的指針。
   
    Inlen:傳入數據的長度,即密文數據的長度。
   
    d和n:兩個大數,作為加密密鑰。
   
    Outdata:存放解密後明文數據的指針。
   
    Outlen:傳入outdata的長度,傳出數據的長度,即明文數據的長度。
   
    Flg:公鑰加密或私鑰加密的標志,g_PUBLIC-公鑰,g_PRIVATE-私鑰。
   
    返回值:1-成功,0-失敗。
   
    D. 用小素數檢測
   
    gChar gIsNotPrime(gBigInt *p);
   
    功能:檢測隨機大數p能否被小素數整除。
   
    參數:
   
    p:待檢測的隨機大數。
   
    返回值:0-可能是素數,其它-為能整除p的小素數或1.
   
    E. Rabin-Miller檢測
   
    gChar gRabinMillerTest(gBigInt *p,int tNum);
   
    功能:用Rabin-Miller算法,對大數p進行tNum次檢測,判斷p是否可能為素數。
   
    參數:
   
    p:待檢測的隨機大數。
   
    tNum:檢測的次數,它可以決定該檢測的可信度。
   
    返回值:0-失敗或通不過,1-成功並通過,說明p可能是素數。
   
    F. 隨機產生大素數
   
    gChar gGeneratePrime(gBigInt *p);
   
    功能:隨機生成一個大素數。
   
    參數:
   
    p:隨機生成的大素數。
   
    返回值:0-失敗,1-成功。
   
    G. 順序搜索大素數
   
    gChar gGeneratePrimeEx(gBigInt *p, int flg);
   
    功能:根據標志flg,遞增或遞減地搜索p附近的大素數。
   
    參數:
   
    p:搜索到的大素數。
   
    Flg:方向標志,g_INCREASE-遞增,g_DECREASE-遞減。
   
    返回值:0-失敗,1-成功。
   
    H. 字符串與大數的轉換
   
    gChar gStr2BigInt(gBigInt *gbi,char *str,int flg);
   
    功能:根據標志flg,將表示成10進制或16進制形式的字符串str轉換成大數gbi.
   
    參數:
   
    gbi:轉換成的大數。
   
    Str:待轉換的字符串。
   
    Flg:標志,OCT_FLG-8進制,DEC_FLG-10進制,HEX_FLG-16進制。
   
    返回值:0-失敗,1-成功。
   
    gChar gBigInt2Str(char *str,gBigInt *gbi,int flg);
   
    功能:根據標志flg,將大數gbi轉換成10進制或16進制形式表示的字符串str.
   
    參數:
   
    Str:轉換成的字符串。
   
    gbi:待轉換的大數。
   
    Flg:標志,OCT_FLG-8進制,DEC_FLG-10進制,HEX_FLG-16進制。
   
    返回值:0-失敗,1-成功。
   
    I. 一般整數的乘除
   
    gUInt gIntMul(gUInt *a, gUInt b);
   
    功能:一般整數的乘法。在函數內部,對整數a和b進行擴展,然後與b相乘,把結果放在a中返回,進位作為返回值。
   
    參數:
   
    a:傳入一個整數,傳出相乘的結果。
   
    b:傳入一個整數,作乘數。
   
    返回值:兩個整數相乘的進位。失敗時,返回0.
   
    gUInt gIntDiv(gUInt *ah, gUInt *al, gUInt b);
   
    功能:一般整數的除法。在函數內部,將整數ah和al合並成一個擴展了的整數,然後除以整數b,把結果的高位放到ah中,低位放到al中返回,余數作為返回值。
   
    參數:
   
    ah:傳入一個整數,作為被除數的高位;傳出相除後的結果的高位。
   
    al:傳入一個整數,作為被除數的低位;傳出相除後的結果的低位。
   
    b:傳入一個整數,作除數。
   
    返回值:相除的余數。失敗時,返回0.
   
    J. 大數的比較
   
    gChar gCmp(gBigInt *a, gBigInt *b);
   
    功能:對大數a和大數b進行比較,不考慮它們的符號,只比較數值。
參數:
   
    a:傳入一個大數。
   
    b:傳入另一個大數。
   
    返回值:-1-大數a小於大數b,0-大數a等於大數b,+1-大數a大於大數b.
   
    gChar gCmpEx(gBigInt *a, gBigInt *b);
   
    功能:對大數a和大數b進行比較,考慮它們的符號,整數大於負數。
   
    參數:
   
    a:傳入一個大數。
   
    b:傳入另一個大數。
   
    返回值:-1-大數a小於大數b,0-大數a等於大數b,+1-大數a大於大數b.
   
    gChar gCmpInt(gBigInt *a, gUInt b);
   
    功能:大數與整數的比較。對大數a和一般整數b進行比較,不考慮它們的符號。
   
    參數:
   
    a:傳入一個大數。
   
    b:傳入一個一般整數。
   
    返回值:-1-大數a小於b,0-大數a等於b,+1-大數a大於b.
   
    K. 大數的賦值
   
    gChar gMov(gBigInt *a, gBigInt *b);
   
    功能:將大數b的值,賦給大數a,考慮它們的符號。
   
    參數:
   
    a:傳出賦值的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gMovInt(gBigInt *a, gUInt b);
   
    功能:將整數b的值,賦給大數a,考慮它們的符號。
   
    參數:
   
    a:傳出賦值的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    L. 大數的加法
   
    gChar gAdd(gBigInt *a, gBigInt *b);//加
   
    功能:對大數a和大數b進行加法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相加的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gAddInt(gBigInt *a, gSInt b);
   
    功能:對大數a和整數b進行加法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相加的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    M. 大數的減法
   
    gChar gSub(gBigInt *a, gBigInt *b);//減
   
    功能:對大數a和大數b進行減法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相減的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gSubInt(gBigInt *a, gSInt b);
   
    功能:對大數a和整數b進行減法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相減的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    N. 大數的乘法
   
    gChar gMul(gBigInt *a, gBigInt *b);//乘
   
    功能:對大數a和大數b進行乘法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相乘的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gMulInt(gBigInt *a, gSInt b);
   
    功能:對大數a和整數b進行乘法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相乘的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    O. 大數的除法
   
    gChar gDiv(gBigInt *a, gBigInt *b);//除
   
    功能:對大數a和大數b進行除法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相除的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gDivInt(gBigInt *a, gSInt b);
   
    功能:對大數a和整數b進行除法運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出相除的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    P. 大數的取余
   
    gChar gMod(gBigInt *a, gBigInt *b);//取余
   
    功能:對大數a和大數b進行取余運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出取余的結果。
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。
   
    gChar gModInt(gBigInt *a, gSInt b);
   
    功能:對大數a和整數b進行取余運算,考慮它們的符號。
   
    參數:
   
    a:傳入一個大數,傳出取余的結果。
   
    b:傳入一個一般整數。
   
    返回值:0-失敗,1-成功。
   
    Q. 歐幾裡德算法
   
    gChar gEuc(gBigInt *a,gBigInt *b);//歐幾裡德算法
   
    功能:對大數a和大數b執行歐幾裡德算法,結果放到a中。即用輾轉相除的思想,求滿足aX≡1 MOD b的X的值,也即求滿足aX-bY=1的較小的大數X和Y的值。
   
    其中用到了遞歸的思想,運算後,大數a和大數b,都改變了。
   
    參數:
   
    a:傳入一個大數,傳出滿足aX-bY=1的X的值。
   
    b:傳入另一個大數,傳出滿足aX-bY=1的Y的值
   
    返回值:0-失敗,1-成功。
   
    R. 蒙格馬利算法
   
    gChar gMon(gBigInt *a, gBigInt *b, gBigInt *c);//蒙格馬利算法
   
    功能:對大數a,大數b和大數c執行蒙格馬利算法,結果放到a中。
   
    即用指數降階的思想,求算式a^b MOD c的值。至於降階的原理,請參考相關書籍。
   
    參數:
   
    a:傳入一個大數,傳出運算的結果。
   
    b:傳入另一個大數。
   
    c:傳入第三個大數。
   
    返回值:0-失敗,1-成功。
   
    S. 最大公約數
   
    gChar gGcd(gBigInt *a, gBigInt *b);//最大公約數
   
    功能:用輾轉相除法,求大數a和大數b的最大公約數。
   
    參數:
   
    a:傳入一個大數,傳出a和b的最大公約數
   
    b:傳入另一個大數。
   
    返回值:0-失敗,1-成功。


摘自 脈凌網絡

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved