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公開密鑰密碼體制於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。

阅读全文»

Vnet是一個充滿黑科技的雲服務提供商。我們可以用它中轉加速SSH，FTP等協議的傳輸，甚至可以加速shadowsocks

什麼時候需要用

訪問國外的vps或者虛擬主機的時候丟包嚴重或者延遲高，或者作為shadowsocks的國內中轉節點。

目前Vnet的服務有

• OneNet(國外翻進來)
• vxDNS
• DB Service
• vDog(服務器監視)
• vxTrans(轉發數據包)
• vxGG(加速遊戲)

我們需要的服務

vxTrans

vxTrans國內有CN2和阿里雲兩個入口，國外有日本KDDI和新加坡GMO節點。最近又上線了香港和新加坡阿里雲，都可以試試

首先註冊一個賬號。如果您願意的話，通過我的邀請鏈接註冊，可以獲得5G的流量。

阅读全文»

信息最初從新浪微博@ringzero 傳播開
強烈譴責這位仁兄！為何要發送 '我是一隻豬' 啊魂淡！((

漏洞已經被封上啦！新浪這次反應速度挺快的嘛

接口調用方法

http://supports.jiaju.sina.com.cn/api/weibo.php?action=send&type=1&content=你需要的文字信息&callback=jsonp1446827400881  

這或許只是其中的一小個接口。也許背後還有不計其數新浪遺留下來的漏洞。

上面的接口能做什麼呢？

從已登陸賬號的新浪微博手機客戶端 或者擁有sina.com.cn cookie記錄的瀏覽器 中打開這個網站，就會返回一系列賬號信息並且 自動發送一條由網址自定義的微博

阅读全文»

這個接口已經被封鎖

偶然发现的一个有趣的接口

http://msg.mail.163.com/cgi/mc?funcid=getusrnewmsgcnt&fid=1&addSubFdrs=1&language=0&style=0&template=newmsgres_setcookie.htm&df=ydweb&callback=&username=admin@163.com  

阅读全文»