rsa原理及其應用

rsa算法

0x01 原理

1.1 相關概念

RSA（Rivest-Shamir-Adleman）加密算法是一種基于數論的非實時加密算法，廣泛用于安全通信。RSA算法的核心依賴于大整數分解的困難性

1.2 非對稱加密

RSA是一種非加密加密算法，它使用公鑰進行加密，私鑰進行解密。非加密加密的優勢在于，公鑰可以公開（存儲于公鑰數據庫PKDB），而私鑰僅保留給接收者。這種設計使得消息安全傳輸，而消耗共享加密密鑰。

1.3 素數（素數）

RSA依賴于兩個大素數的乘積。素數是指只能被1和自身整除的整數。兩個大素數的乘積積極難以進行因數分解，而這一問題構成了RSA的安全基礎。

1.4 模運算（Modulo）

余數 RSA 中廣泛使用模破壞。模破壞是一種余數破壞，定義為一個整數除以另一個整數后得到的數。在 RSA 中，模破壞對加密和解密過程的避免可以在有限的數值范圍內進行，從而避免溢出和精度問題。

1.5歐幾里得函數

給定兩個非負整數 a 和 b（假設 a ≥ b），歐幾里得算法基于以下原理：

如果 a = b，那么結果就是 a（或 b）。
如果 a = 0，那么結果是 b，反之亦然。
如果 a ≠ b，那么可以用較小的那個數去除較大的那個數，然后用余數代替較大的數，重復此步驟直到余數為 0。

歐幾里得算法的步驟

計算 a mod b 得到余數 r。
如果 r = 0，那么 b 就是 a 和 b 的最大公約數。
如果 r ≠ 0，令 a = b，b = r，然后重復步驟 1。

示例

假設我們要找 48 和 18 的最大公約數：

48mod??18=1248mod18=12
18mod??12=618mod12=6
12mod??6=012mod6=0，此時余數為 0，所以最大公約數是 6。

擴展歐幾里得算法

擴展歐幾里得算法不僅可以找到 a 和 b 的最大公約數 d，還可以找到一對整數 x 和 y，使得 ax + by = d

1.6 歐拉函數φ(n)

歐拉函數（Euler's Totient Function），通常記作 φ(n)，是數論中的一個重要函數。它對于一個正整數 n 定義為小于或等于 n 的正整數中與 n 互質的數的數目。兩個數互質（coprime）指的是它們的最大公約數（GCD）為 1。

例如，φ(9) = 6，因為 1, 2, 4, 5, 7 和 8 與 9 互質；而 φ(8) = 4，因為只有 1, 3, 5 和 7 與 8 互質。

如果 n 是一個質數 p 的冪次 p^k，則有：

 φ(pk)=pk?pk?1=pk(1?1p)*φ*(*p**k*)=*p**k*?*p**k*?1=*p**k*(1?*p*1)

對于任意正整數 n，如果 n 可以分解為不同質數的乘積：

 n=p1k1?p2k2?pmkm*n*=*p*1*k*1?*p*2*k*2?*p**m**k**m*

那么根據歐拉函數的性質，我們可以計算出：

 φ(n)=φ(p1k1)?φ(p2k2)?φ(pmkm)*φ*(*n*)=*φ*(*p*1*k*1)?*φ*(*p*2*k*2)?*φ*(*p**m**k**m*) φ(n)=n?(1?1p1)?(1?1p2)?(1?1pm)*φ*(*n*)=*n*?(1?*p*11)?(1?*p*21)?(1?*p**m*1)

0x02 算法描述

1.1 密鑰計算步驟

1、生成兩個大素數p和q

2、計算兩個素數的乘積

n=p*q

3、計算歐拉函數

φ(n)=(p-1)*(q-1)

4、選擇一個整數e（1 < e < φ(n)），使得e與φ(n)互質（即最大公約數gcd(e, φ(n)) = 1）。通常情況下，e取一個較小的質數如65537 (2^16 + 1)，因為它使得加密過程更高效。

5、歐幾里得算法計算d(私鑰)

d（1 < d < φ(n)），使得

(d * e) mod φ(n) = 1
d = e^-1 mod φ(n)

換句話說，d是e在模φ(n)下的乘法逆元

6、公鑰：由(n, e)組成

? 私鑰：由(n, d)組成

7、加密

m（其中m必須小于n）使用公鑰(n, e)，加密公式為c = m^e mod n，這里c是密文

8、解密

c使用私鑰(n, d)，解密公式為m = c^d mod n，這樣就恢復了原始的消息m

1.2 小結

公鑰	（e,n）
私鑰	（d,n）
密鑰對	（e,n,d）
加密	c = m^e mod n
解密	m = c ^d mod n

n	p*q
φ(n)	*(p-1)(q-1)**
e	1<e< φ(n)
d	1<d< φ(n) *,ed mod φ(n) = 1**

0x03 RSA算法的實現

RSA算法的實現涉及到大數的冪模運算，這在計算機編程中通常通過特定的算法來優化，如平方-乘法算法。以下是RSA算法的一個簡化的Python實現示例：

import random
from math import gcd

def is_prime(num):
    """檢查num是否為素數"""
    if num < 2:
        return False
    for factor in range(2, int(num ** 0.5) + 1):
        if num % factor == 0:
            return False
    return True

def generate_prime(start, end):
    """在[start, end]區間內生成一個素數"""
    prime = random.randint(start, end)
    while not is_prime(prime):
        prime = random.randint(start, end)
    return prime

def multiplicative_inverse(e, phi):
    """計算e相對于phi的模逆"""
    d = 1
    while d * e % phi != 1:
        d += 1
    return d

def generate_keypair(p, q):
    """生成公鑰和私鑰"""
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # 選擇e
    e = random.randrange(2, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(2, phi)
        g = gcd(e, phi)
        
    # 計算d
    d = multiplicative_inverse(e, phi)
    
    # 返回公鑰和私鑰
    return ((e, n), (d, n))

def encrypt_rsa(public_key, plaintext):
    """使用公鑰public_key對明文plaintext進行加密"""
    e, n = public_key
    # 將每個漢字轉換成Unicode碼并加密
    encrypted = [pow(ord(char), e, n) for char in plaintext]
    return encrypted

def decrypt_rsa(private_key, ciphertext):
    """使用私鑰private_key對密文ciphertext進行解密"""
    d, n = private_key
    # 對每個數字解密并轉換回字符
    decrypted = [chr(pow(char, d, n)) for char in ciphertext]
    return ''.join(decrypted)

# 示例代碼
if __name__ == '__main__':
    # 生成兩個較小的素數（為了簡化示例）
    p = generate_prime(65537, 65537 * 2)
    q = generate_prime(65537, 65537 * 2)
    
    # 生成公鑰和私鑰
    public, private = generate_keypair(p, q)
    
    # 中文明文
    message = "你好世界！"
    
    # 加密
    encrypted_msg = encrypt_rsa(public, message)
    print("加密后的消息:", encrypted_msg)
    
    # 解密
    decrypted_msg = decrypt_rsa(private, encrypted_msg)
    print("解密后的消息:", decrypted_msg)

0x04 安全性和應用

RSA算法的安全性取決于密鑰的長度，目前推薦的密鑰長度至少為2048位。RSA算法廣泛應用于數字簽名、安全通信等領域。然而，隨著計算能力的提升和量子計算的發展，RSA算法的安全性面臨挑戰，因此密鑰長度和算法的實現需要不斷更新以保持安全。

rsa安全三種模式：

4.1 加密模式

公鑰加密，私鑰解密

發方：A先查PKDB，查到公開的公鑰KeB——>A用KeB加密明文M——>得到密文：C=E(M,KeB)——>A發送密文C給B

收方：B接受C——>B用主機的私鑰KdB解密密文C——>得到密文M=D（M，KdB）

4.2 認證模式

私鑰加密，公鑰解密

發方：A用主機的私鑰KdA加密密文M——>得到密文C=E（M,KdA）

收方：B接受C——>B查PKDB——>查到A的KeA——>用KdA解密C——>得到明文M=D（C,KeA）

4.3機密認證混合模式

同時保證數據的秘密性和真實性

發方：A用自己的私鑰KdD加密消息M——>得到中間密文S=E（M，KdA）——>A查詢PKDB——>得到B的公鑰KeB——>用公鑰KeB加密S得到——>最終密文C=(M，KeB)——>A發送給B

收方：B接受C——>B用自己的私鑰KdB解密密文C——>得到中級密文S=D（C，KdB）——> B查找PKDB找到A的公鑰KeA——>解密消息S——>得到明文M=（S，KeA）

4.4 應用

RSA算法的應用包括但不限于以下幾個方面：
1. 數據加密：
  - RSA可以用于保護數據在傳輸過程中的安全，比如在互聯網上的通信。
  - 它被廣泛應用于HTTPS協議中，確保網站與用戶之間的通信安全。
2. 數字簽名：
  - RSA還用于創建數字簽名，這可以驗證數據來源的真實性以及數據是否未被篡改。
  - 數字簽名可以用來確認文件或電子文檔的發布者身份，并保證文件的完整性。
3. 密鑰交換：
  - 在一些場景下，RSA用于在通信雙方之間安全地交換對稱加密所需的密鑰。
4. 身份驗證：
  - RSA可用于實現身份驗證機制，如在登錄過程中使用公鑰/私鑰對來驗證用戶的身份。
5. 軟件保護：
  - 軟件開發商可能會使用RSA來保護他們的軟件不受非法復制。
6. 電子郵件加密：
  - 使用PGP（Pretty Good Privacy）等協議時，RSA用于加密郵件內容或創建郵件簽名。
7. 其他安全協議：
  - RSA也是許多其他安全協議的一部分，如TLS/SSL、SSH、IPsec等。
RSA算法雖然強大，但由于其計算密集型的特點，在處理大量數據時可能效率較低。因此，在實際應用中，通常會結合使用RSA和其他更高效的對稱加密算法。例如，使用RSA加密一個對稱密鑰，然后用這個對稱密鑰來加密實際的數據。這樣既保證了數據的安全性，又提高了加密解密的速度。

posted @ 2024-10-17 16:57 有一大盒閱讀(355) 評論(0) 收藏舉報

刷新頁面返回頂部

凌冬的雪終會飄落

和光同塵，與時倦舒