摘要：算法公鑰加密算法是年由羅納德李維斯特阿迪薩莫爾和倫納德阿德曼一起提出的。是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

上篇文章介紹了對稱加密的原理，但是它的最大問題就是加密和解密的密鑰是相同的，并且不能保證密鑰能安全的送到雙方手里，即使安全的送到雙方手里，免不了內(nèi)部會(huì)有"臥底"的存在

既然有對稱加密，那么自然會(huì)聯(lián)想到非對稱加密。非對稱加密的核心在于加密和解密使用的是不同的密鑰，如何做到使用不同的密鑰呢？
比如我有一個(gè)只能用鑰匙打開的存錢罐，平時(shí)大家只能把零錢放到儲(chǔ)錢罐中，但是只有我才有取錢的鑰匙。放到儲(chǔ)錢罐的硬幣可以看成加密后的內(nèi)容，而只有用鑰匙才能將"加密"后的硬幣取出來。
這樣我們就可以把用來加密的密鑰(公鑰)給了任何人，我們只要自己保存好解密的密鑰(私鑰)就可以安全的保護(hù)我們的數(shù)據(jù)。
非對稱算法有很多:RSA、Elgamal、背包算法、Rabin、D-H、ECC等，下面我們來簡單介紹一下RSA算法。

RSA公鑰加密算法是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的(啥時(shí)候以我名字命名一個(gè)呢)。
RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。

//注意：明文為數(shù)字，實(shí)際計(jì)算過程我們可以通過ASCII碼轉(zhuǎn)換
密文 = (明文 ^ E) % N; //其中的E和N就是我們的公鑰

明文 = (密文 ^ D) % N; //其中的D和N就是我們的私鑰

公鑰和私鑰不是隨便弄幾個(gè)數(shù)字就可以的，是經(jīng)過嚴(yán)格的數(shù)學(xué)公式計(jì)算出來的。

N = P * Q;

L = (P - 1) * (Q - 1); //圖解密碼技術(shù)中說需要計(jì)算乘積之后的最小公倍數(shù)，但是經(jīng)過代碼測試并不準(zhǔn)確，哪位大俠了解麻煩留言告知一下~

//E需要同時(shí)滿足下面兩個(gè)條件
1. 1 < E < L
2. E和L的最大公約數(shù)為一(歐幾里得算法，這些惡魔啊，E和L必須互質(zhì)，這樣才能保證一定可以計(jì)算出私鑰D)

//D需要滿足下面公式
(E * D) % L = 1; //想要保證結(jié)果為1，E和L必須互質(zhì)!!!

上面就是整個(gè)計(jì)算過程，為了保證數(shù)據(jù)的安全現(xiàn)實(shí)中，P和Q會(huì)選用特別大的數(shù)(1024比特或者更大)

上面已經(jīng)提到過加密和解密的方法，我們用具體的數(shù)字實(shí)踐一下，加深理解吧。

假設(shè):P = 7、Q = 11(均為質(zhì)數(shù))
那么:N = P * Q = 7 * 11 = 77

L = (P - 1) * (Q - 1) = 6 * 10 = 60

1 < E < 60
E和L的最大公約數(shù)為一，我們假設(shè)E=23

(23 * D) % 60 = 1;
D = 47;

那么我就得到了公鑰(E=23,N=77),私鑰(D=47,N=77)

我們假設(shè)需要加密數(shù)字:12
公式:密文 = (明文 ^ E) % N;
12 ^ 23 % 77 = 6624737266949237011120128 % 77 = 45;
這個(gè)45就是我們加密后的密文

解密
公式:明文 = (密文 ^ D) % N;
45 ^ 47 % 77 = 502328880013965819626664594350710696732674427522624682751484215259552001953125 % 77 = 12;
得出原文:12

下面是我用PHP實(shí)現(xiàn)的加密&解密示例，供大家參考(因?yàn)橹笖?shù)運(yùn)算的結(jié)果集會(huì)很大，我們必須使用PHP中提供的BC Math系列函數(shù)計(jì)算)

/**
 * 冒牌RSA算法
 * @author zhjx922
 */

/**
 * 判斷數(shù)字是否為質(zhì)數(shù)
 * @param $num
 * @return bool
 */
function isPrimeNumber($num) {
    $k = 0;//定義次數(shù)變量
    for ($i = 1; $i <= $num; $i++) {
        if (bcmod($num, $i) == 0) {
            $k++;//如果取模等于0，次數(shù)k自加
        }
    }

    if ($k == 2) {
        return true;
    }
    return false;
}

//求最小公倍數(shù)
function minMultiple($a, $b)
{
    if($b==0)     //一定要考慮除數(shù)不能為零
    {
        return $b;
    } else {
        $m = bccomp($a, $b) == 1 ? $a : $b;
        $n = bccomp($b, $a) == 1 ? $b : $a;

        for($i=2; ; $i++)
        {
            $mul = bcmul($m, $i);
            if(bcmod($mul, $n) == 0)
            {
                return $mul;
            }
        }
    }
    return bcmul($a, $b);
}

//求最大公約數(shù)
function maxDivisor($a,$b)
{
    $n = bccomp($a, $b) == 1 ? $b : $a;
    for($i = $n; $i>1; $i--)
    {
        if(bcmod($a, $i) == 0 && bcmod($b, $i) == 0)
        {
            return $i;   //此處如果用echo $i;則輸出結(jié)果為432；故應(yīng)區(qū)分echo、return的區(qū)別
        }
    }
    return 1;
}


do{
    //隨機(jī)一個(gè)質(zhì)數(shù)P
    $p = mt_rand(101, 197);
} while(!isPrimeNumber($p));

do{
    //隨機(jī)一個(gè)質(zhì)數(shù)Q
    $q = mt_rand(101, 197);
} while(!isPrimeNumber($q));


$n = bcmul($p, $q);

//$l = minMultiple($p - 1, $q - 1); //經(jīng)測試不可用
$l = bcmul($p - 1, $q - 1);

do {
    $e = mt_rand(2, $l - 1);
}while(maxDivisor($e, $l) != 1);


$d = 1;
while(bcmod(bcmul($e,++$d), $l) != 1) {

}

echo "p:" . $p . PHP_EOL;
echo "q:" . $q . PHP_EOL;
echo "n:" . $n . PHP_EOL;
echo "l:" . $l . PHP_EOL;
echo "e:" . $e . PHP_EOL;
echo "d:" . $d . PHP_EOL;

echo "公鑰:e={$e},n={$n}" . PHP_EOL;
echo "私鑰:d={$d},n={$n}" . PHP_EOL;

//加密
function encode($e, $n, $string) {
    $enString = "";
    $len = strlen($string);
    for($i = 0; $i < $len; $i++) {
        $pow = bcpow(ord($string{$i}), $e);
        $mod = bcmod($pow, $n);
        $enString .= pack("L", $mod);
    }
    return $enString;
}


//解密
function decode($d, $n, $string) {
    $deString = "";
    $string = unpack("L*", $string);
    $len = count($string);
    for($i = 1; $i <= $len; $i++) {
        $pow = bcpow($string[$i], $d);
        $mod = bcmod($pow, $n);
        $deString .= chr($mod);
    }
    return $deString;
}


$startTime = microtime(true);

$string = "歡迎關(guān)注"假裝是個(gè)程序員"公眾號(hào)";
echo "原文:" . $string . PHP_EOL;

$encodeString = encode($e, $n, $string);
echo "密文:" . $encodeString . PHP_EOL;

$decodeString = decode($d, $n, $encodeString);
echo "解密后:" . $decodeString . PHP_EOL;


$endTime = microtime(true);

echo "Total:" . ($endTime - $startTime) . "s." . PHP_EOL;

沒有什么加密方式能一直保持絕對的安全，尤其常用的MD5，如果你的數(shù)據(jù)庫中密碼還是使用MD5的哈希結(jié)果不要笑話人家直接用明文存密碼的人，五十步笑百步而已。。。
最近谷歌宣布破解了SHA-1，隨著計(jì)算能力的提高，SHA-256，RSA等等也是遲早的事兒。。

歡迎關(guān)注我的公眾號(hào)，一起交流學(xué)習(xí)~