1.加密算法原則

其實(shí)任何加密算法都有1個(gè)原則， 就是正向運(yùn)算簡(jiǎn)單， 反向推算很難。

我們假設(shè) x 是原數(shù)據(jù)， y是加密后的數(shù)據(jù)， f()是加密算法.

那么f()必須滿足 $y=f(x)$ ， 而且f的運(yùn)算要相對(duì)于簡(jiǎn)單。

而對(duì)應(yīng)的反函數(shù) $y=f^{?1}(x)$ 則要求很復(fù)雜.

例如 $f(x)=x^7$ 是不適和作為加密算法的.
因?yàn)閷?duì)應(yīng)的反函數(shù) $f(x)=\sqrt[7]{x}$ 對(duì)于計(jì)算機(jī)來講并不復(fù)雜， 這意味這么加密后的數(shù)據(jù)很容易破解.

在當(dāng)今數(shù)學(xué)中， 什么最難， 數(shù)論肯定是候選的答案之一， 而數(shù)論是主要研究質(zhì)數(shù)的， 也就是講我們可以利用質(zhì)數(shù)難以逆運(yùn)算的特性來獲得一些加密算法

看看下面這個(gè)算法, 下面出現(xiàn)的字符 x y e n 等都是整數(shù), 而 e, n 是已知的常量, 且都是質(zhì)數(shù)

$y=f(x)=x^e\mathrm{mod}n$
這個(gè)算法的正向算法是不復(fù)雜的， 只不過是求 x 的 e次方 后再除以 n 后的余數(shù) 就是y

但是反過來已知y的話， 反推 x 的值就不簡(jiǎn)單了，特別是如果 y , e 與 n都是1個(gè)相當(dāng)大的質(zhì)數(shù)的時(shí)候(1024/2048 bit)

2.引入key令解密可行

問題來了， 上面的算法既然反運(yùn)算這么困難， 那么如何解密呢

所以這就是RSA神奇的地方， 其實(shí)下數(shù)學(xué)式中， y表示加密后的值， x是原來的值， 而e 和 n的組合[e, n] 就是公鑰public key
$y=f(x)=x^e\mathrm{mod}n$

假設(shè)存在另1個(gè)private key [d, n]， 如果已知加密后的y值的話， 可以用相同的公式
$x=g(y)=y^d\mathrm{mod}n$ 來求出x 完成解密

那么[d, n]就是所謂的私鑰.

也就是講， 雖然這個(gè)算法逆運(yùn)算很難， 但是我們可以通過1些規(guī)則生成一對(duì) 公鑰 和 私鑰 .
利用 公鑰可以 1個(gè)相當(dāng)簡(jiǎn)單的數(shù)學(xué)式求得 加密值
而且 也可以 利用 私鑰 和相同的數(shù)學(xué)式 來求得 加密錢的值.

其實(shí)這就是RSA的基本原理了.

而本質(zhì)就是我們用質(zhì)數(shù)去求積是很簡(jiǎn)單的， 但是反過來大質(zhì)數(shù)分解就相當(dāng)困難。

注：
大質(zhì)數(shù)分解是指將一個(gè)大的合數(shù)分解成它的質(zhì)因數(shù)的乘積的過程。在密碼學(xué)中，大質(zhì)數(shù)分解是一種重要的數(shù)學(xué)問題，因?yàn)樵S多加密算法的安全性都基于這個(gè)問題的困難性。

具體來說，假設(shè)有一個(gè)大的合數(shù)n，它是兩個(gè)大的質(zhì)數(shù)p和q的乘積，即n = p * q。如果p和q都非常大，那么將n分解成p和q的乘積是非常困難的。這是因?yàn)槟壳耙阎淖詈玫姆纸馑惴ㄐ枰笖?shù)級(jí)的時(shí)間和計(jì)算資源，隨著p和q的位數(shù)增加，算法的時(shí)間和資源需求呈指數(shù)級(jí)增長。

因此，大質(zhì)數(shù)分解被認(rèn)為是一種“困難問題”，即在可接受的時(shí)間內(nèi)無法解決的問題。這個(gè)問題的困難性是許多加密算法的基礎(chǔ)，包括RSA算法、Rabin加密算法、Goldwasser-Micali加密算法等。這些算法的安全性基于假設(shè)，即在合理的時(shí)間內(nèi)無法分解大的合數(shù)。

需要注意的是，雖然大質(zhì)數(shù)分解被認(rèn)為是困難問題，但這并不意味著它在未來永遠(yuǎn)無法被解決。隨著計(jì)算技術(shù)的不斷進(jìn)步和新的算法的發(fā)展，有可能會(huì)出現(xiàn)更快速的分解算法，從而導(dǎo)致這些加密算法的不安全性。因此，密鑰的長度需要根據(jù)當(dāng)前計(jì)算技術(shù)的發(fā)展和安全需求的變化而不斷調(diào)整。

3. 1個(gè)RSA算法加解密的例子

現(xiàn)在我們已經(jīng)通過一些規(guī)則（下面介紹）， 獲得了RSA算法的一對(duì) public key 和 private key
分別是
public key = [3, 51] 則 e = 3, n = 51
private key = [11, 51] 則 d = 11, n = 51
它們都是質(zhì)數(shù)

加密

下面我們用RSA算法和public key [3, 51] 來加密 1個(gè)數(shù)字21, 則 x = 21
所以 $y=x^e\mathrm{mod}n=21^3\mathrm{mod}51=9261\mathrm{mod}51=30$

也就是 先求 $21^3=9261$ 然后求9261 除以 51 的余數(shù)， 因?yàn)?81 * 51 + 30 = 9261， 所以余數(shù)是30
也就是 加密后的值 y = 30

解密

下面我們用RSA算法和private key [11, 51] 來解密上面加密后的值30
所以 $x=y^d\mathrm{mod}n=30^{1}1\mathrm{mod}51=17714700000000000\mathrm{mod}51=21$

也就是 先求 $30^{11}=17714700000000000$ 然后求 17714700000000000 除以 51 的余數(shù)， 因?yàn)?47347058823529 * 51 + 21 = 17714700000000000， 所以余數(shù)是 21
也就是 求得加密前的值 x = 21

是不是很神奇， 但是實(shí)際上 e d 和 n都是非常大的質(zhì)數(shù)， 即使使用超級(jí)計(jì)算在不知道d 的值情況下 去窮舉也很難求得 用e 加密后值的原來值的.

4. 如何計(jì)算出一對(duì)可用的RSA 公鑰和私鑰

對(duì)關(guān)鍵上面的[3, 51], [11,51] 這對(duì)keys 是如何獲得的呢？

這個(gè)就是RSA算法的核心了， 它用到了歐拉定理。

包含下面5個(gè)規(guī)則

上面例子是 我們選擇 兩個(gè)質(zhì)數(shù)3 和 17 則p=3 q=17

第2步 , n = 51
第3步 , t = (3-1) * (17 - 1) = 32
第4步， 選擇 e = 3 1 < 3 < 32 且 3 不是32 的因數(shù)
第5步，選擇 d = 11 3 * 11 除以 32 的余數(shù)正好是1

所以 得到 公鑰 = [e, d] = [3, 51]
私鑰 = [d, n] = [11, 51]

5.1如何用python 寫代碼實(shí)現(xiàn)上功能

我們先寫1個(gè) 類 KeyGenerator 用于生成 公鑰和私鑰

KeyGenerator.py

from sympy import isprime

from src.common.annotation.ToString import to_string

'''
   這個(gè)類是用于demo 生成 一對(duì) 公鑰 私鑰

   步驟：
   1. 選擇兩個(gè)質(zhì)數(shù) p q
   2. 求得中間參數(shù) n = p * q
   3. 求得中間參數(shù) t =（p-1) * (q-1)
   4. 選擇1個(gè)質(zhì)數(shù)e,  1 < e < t， 而且 e 與 t互質(zhì)
   5. 計(jì)算e的模數(shù)反元素d， 即是滿足 ed mod t = 1
   
   則公鑰是 [e, n], 私鑰是 [e, d]
   
   ====================
   下面內(nèi)容不在這個(gè)類中
   加密時(shí)，將明文m轉(zhuǎn)換為整數(shù)，使用公鑰加密，即 c ≡ m^e (mod n)
   解密時(shí)，使用私鑰解密，即 m ≡ c^d (mod n)

'''


@to_string
class KeyGenerator:
    def __init__(self, p, q):
        self._p = p
        self._q = q
        self.__validate_prams()

    @property
    def p(self):
        return self._p

    @property
    def q(self):
        return self._q

    def __validate_prams(self):
        """
        verfiy p q, both of them must be prime
        """
        if not isprime(self.p) or not isprime(self.q):
            raise ValueError("p and q must be primes!")

    def get_n_pram(self):
        """
        step 2, n = pq
        """
        return self.p * self.q

    def get_t_pram(self):
        """
        step 3, t = (p-1)(q-l)
        """
        p = self.p
        q = self.q
        return (p - 1) * (q - 1)

    def get_pub_key(self):
        """
        step 4, choose a prime e,  e must meet below 3 conditions
        1. e is a prime
        2. 1 < e < t
        3. e is not a factor of t
        then public key is [e, n]
        """
        n = self.get_n_pram()
        t = self.get_t_pram()
        e = -1
        for i in range(2, t):
            if isprime(i) and t % i != 0:
                e = i
                break

        if e < 0:
            raise ValueError("cannot find a prime for pub key, please adjust the p q")
        return [e, n]

    def get_pri_key(self, pub_key):
        """
        step 5, choose a prime d
        de mod t = 1 and d != e
        then private key is [d, n]
        """
        n = self.get_n_pram()
        t = self.get_t_pram()
        e = pub_key[0]
        d = 1
        while (d * e) % t != 1 or d == e:
            d = d + 1
        return [d, n]

下面測(cè)試代碼用于生成一對(duì)公鑰私鑰

p = 3
q = 17

key_generator = KeyGenerator(p, q)
public_key = key_generator.get_pub_key()
private_key = key_generator.get_pri_key(public_key)

print("public key is " + str(public_key))
print("private key is " + str(private_key))

輸出

public key is [3, 51]
private key is [11, 51]

我們?cè)賹憙蓚€(gè)類， 1個(gè)用于加密， 1個(gè)用于解密

加密類

class RsaEncryptor:

    def __init__(self, pub_key):
        self._pub_key = pub_key

    @property
    def pub_key(self):
        return self._pub_key

    @pub_key.setter
    def pub_key(self, value):
        self._pub_key = value

    def encrypt(self, num):

        """
        假設(shè)公鑰是[e, n]
        則 加密時(shí)，將明文m轉(zhuǎn)換為整數(shù)，使用公鑰加密，即 c ≡ m^e (mod n)
        """

        e = self.pub_key[0]
        n = self.pub_key[1]

        return num ** e % n

解密類

class RsaDecrypter:

    def __init__(self, pri_key):
        self._pri_key = pri_key

    @property
    def pri_key(self):
        return self._pri_key

    @pri_key.setter
    def pri_key(self, value):
        self._pri_key = value

    def decrypt(self, num):
        """
        假設(shè)私鑰是[d, n]
        則 解密時(shí)， 使用的算法是   m ≡ c^d (mod n)， 與加密是同樣算法
        """

        d = self.pri_key[0]
        n = self.pri_key[1]

        return num ** d % n

測(cè)試代碼：

num = 21

public_key = [3, 51]
private_key = [11, 51]

encryptor = RsaEncryptor(public_key)
decrypter = RsaDecrypter(private_key)

encrypted_num = encryptor.encrypt(num)
decrypter_num = decrypter.decrypt(encrypted_num)

print("original number is " + str(num))
print("encrypted number is " + str(encrypted_num))
print("decrypted number is " + str(decrypter_num))