RSA原理和實踐

RSA實現步驟

選擇大素數

任意選擇兩個素數p q,這兩個素數應是保密的。一般情況下選擇100~200位的十進制數。令n = p×q,再計算n的歐拉函數ψ(n)=(p-1)×(q-1)。這幾個數中,n可以公開。

生成公鑰私鑰密鑰對

隨機選擇一個與ψ(n)互素的整數e作為公鑰(Public key),再根據算式e × d = 1 (mod ψ(n)),計算出d作為私鑰(Private key)。這是一個求乘法逆元的過程。私鑰是保密的,公鑰是公開的。

發佈密鑰

私鑰(d, n)保密,公鑰(e, n)公開即可。

加密與解密

加密時,先將明文比特串分組,使每個分組的十進制數小於n(即比特串分組長度小於log2(n)),然後對每個明文分組m加密運算:

c = m^e mod n

解密同理,對密文分組進行解密運算:

m = c^d mod n

數學證明

∵c = m^e mod n
∴c^d mod n = m^(ed) mod n
∵ed = 1 (mod ψ(n))
∴ed = kψ(n) + 1
∴c^d mod n = m^(kψ(n) + 1) mod n

①当m n互素時

由歐拉定理可得:
m^(ψ(n)) mod n = 1
∴m^(kψ(n)) mod n = 1
∴m^(kψ(n) + 1) mod n = m
即m^(ed) mod n = m
證得

①当m n不互素情況概率小於1/p + 1/q,故可以不做考慮。(本身也可以證明,不過較為繁瑣)

閱讀全文»

RSA基礎知識

簡介

RSA公開密鑰密碼體制於1978年提出,名字來源於提出者名字縮寫。這種密碼體制由數論構造,是迄今為止理論上最為成熟完善的密碼體制,安全性能目前看來依然良好,並且應用十分廣泛。密碼體制一般基於數學難題,RSA也不例外。
RSA是基於大整數分解的難題。給定整數e和c,尋找滿足條件的m,使得c = m^e mod N。

基礎知識

RSA基於以下數論內容

  • 歐拉函數
  • 同餘
  • 擴展歐幾裡德算法
  • 一次同餘式及其求解
  • 費馬小定理(或歐拉定理)

算法

求最大公約數(Greatest Common Divisor)

通過類輾轉相除法

long int gcd(long int a, long int b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

快速指數算法

由模運算性質

[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) × (b mod n)] mod n = (a × b) mod n

可以簡化運算。

例如求 3^19 mod 7
= 3×3^18 mod 7
= 3×(3^2)^9 mod 7
= 3×(9 mod 7)^9 mod 7
= 3×2^9 mod 7
= 6×2^8 mod 7
= 6×4^4 mod 7
= 6×(16 mod 7)^2 mod 7
...
= 3

long int fastModel(long int base, long int power, long int model){
    long int temp = 1;
    long int result = 0;

    while(power != 1){
        if(power % 2 == 0){
            power /= 2;
            base = base * base % model;
        }
        else if(power % 2 != 0){
            power -= 1;
            temp = temp * base % model;
        }
    }
    result = temp * base % model;
    if (result <= 0){
        result += model;
    }
    return (long int)result;
}

計算乘法逆元(解一次同餘式)

已知a,n,ax ≡ 1 (mod n),求x。
①定義X1,X2,X3,Y1,Y2,Y3。令(X1,X2,X3)=(1,0,n);(Y1,Y2,Y3)=(0,1,a)。
②令Q = X3/Y3(不留小數點)
③令(T1,T2,T3)=(X1-Q×Y1,X2-Q×Y2,X3-Q×Y3);(X1,X2,X3)=(Y1,Y2,Y3);(Y1,Y2,Y3)=(T1,T2,T3)
④迴圈這一步,直到Y3 = 1或0。如果為0,則無解;如果為1,則解為Y2。

閱讀全文»

關於EasyPass

簡介

很久以前有一個想法,只用一個密碼,通過hash的方式生成所有網站的密碼。具體是通過一個原密碼+一些任意字符串,生成不同的字符串結果。
於是就寫了這個EasyPass,Demo在http://pw.nya.pm/
下面記錄下自己實現的過程

生成密碼表

閱讀全文»

Modafinil的使用建議

Modafinil可以使人長期保持興奮狀態,其作用機理與咖啡因類似,與咖啡因共同使用可以互相增強效果。

副作用目前看來較少,明顯的有口渴,心悸,亢奮,易怒。如果一次使用劑量小,副作用相對也會減少。
心悸在使用後一段時間就會緩解。

半衰期較長,12-15h,所以建議在清晨使用。可以稍微早一些起床,使用之後睡一個回籠覺。這樣心悸會好很多。

初次可以從100mg開始試用,可以提前幾天少量使用觀察情況。可能出現耐藥性,因人而異。

VMWare配置Debian8

Windows的PHP又出問題了,所以弄了一個VMWare來跑Debian,並且打算作為開發環境。

VMWare和Debian ISO

我使用的是VMWare Workstation 12,可以直接讀出debian的ISO。系統ISO在中科大的鏡像https://mirrors.ustc.edu.cn/可以下載到。

安裝Debian

直接新建虛擬機器,掛載ISO,使用Graphical install安裝即可。
VMWare設置中使用NAT網路橋接。
不需要使用網路鏡像。

初始化

安裝中文字體

apt-get install ttf-wqy-*

更改默認源到中科大源

vi /etc/apt/sources.list

添加或者替換為

deb http://mirrors.ustc.edu.cn/debian stable main contrib non-free
deb-src http://mirrors.ustc.edu.cn/debian stable main contrib non-free
deb http://mirrors.ustc.edu.cn/debian stable-proposed-updates main contrib non-free
deb-src http://mirrors.ustc.edu.cn/debian stable-proposed-updates main contrib non-free

詳見https://lug.ustc.edu.cn/wiki/mirrors/help/debian

更新軟體,安裝常用軟體

apt-get update
apt-get upgrade
apt-get install vnstat vim git curl sudo #...此處隨意

安裝桌面環境

閱讀全文»