RSA公開金鑰加密技術與數位簽章實作

RSA演算法作為一種非對稱加密技術，在保障資訊安全方面扮演著關鍵角色。理解其運作原理，包含金鑰生成、加密、解密以及數位簽章等環節，對於開發安全的網路應用至關重要。本文除了介紹RSA的數學基礎，也著重於Python程式碼的實作細節，例如訊息的區塊化處理、大整數運算以及ASCII編碼的應用，讓讀者能更具體地掌握RSA演算法的實際應用。

公鑰密碼學與RSA密碼學

公鑰密碼學是一種重要的密碼學技術，不僅能夠提供加密功能，還能夠實作數位簽章。RSA密碼學是其中一種最廣泛使用的公鑰密碼學演算法。

數位簽章

數位簽章是一種用於驗證訊息真實性和完整性的技術。假設Alice寄了一封電子郵件給Bob，內容是承諾以一百萬美元購買Bob的舊筆記型電腦。Bob收到郵件後很高興，但如果Alice後來聲稱這封郵件是Bob偽造的，那麼Bob該怎麼辦？

傳統上，人們會使用手寫簽名來驗證檔案的真實性。但是在數位世界中，手寫簽名很容易被偽造。幸運的是，RSA密碼學提供了一種數位簽章的解決方案。

數位簽章的工作原理

Alice可以使用她的私鑰對訊息進行「加密」，產生一段「密鑰」。由於只有Alice擁有她的私鑰，因此只有她才能產生這段密鑰。其他人可以使用Alice的公鑰對這段密鑰進行「解密」，驗證訊息的真實性。

def digital_signature(message, private_key):
    # 使用私鑰對訊息進行「加密」
    signature = encrypt(message, private_key)
    return signature

def verify_signature(signature, public_key, original_message):
    # 使用公鑰對簽章進行「解密」
    decrypted_message = decrypt(signature, public_key)
    # 驗證解密後的訊息是否與原始訊息一致
    if decrypted_message == original_message:
        print("簽章驗證成功！")
    else:
        print("簽章驗證失敗！")

內容解密：

1. digital_signature函式使用私鑰對訊息進行加密，產生數位簽章。
2. verify_signature函式使用公鑰對數位簽章進行解密，並驗證解密後的訊息是否與原始訊息一致。
3. 如果驗證成功，表示數位簽章是有效的，訊息來自聲稱的傳送者。

RSA密碼學程式的工作原理

RSA密碼學程式使用公鑰和私鑰對訊息進行加密和解密。下面是程式的主要步驟：

1. 設定預設的區塊大小和位元組大小。
2. 如果模式是encrypt，則使用公鑰對訊息進行加密，並將加密後的訊息寫入檔案。
3. 如果模式是decrypt，則使用私鑰對檔案中的加密訊息進行解密，並輸出解密後的訊息。

程式碼範例

# 設定預設的區塊大小和位元組大小
DEFAULT_BLOCK_SIZE = 128
BYTE_SIZE = 256

def main():
    filename = 'encrypted_file.txt'
    mode = 'encrypt'

    if mode == 'encrypt':
        message = '''"Journalists belong in the gutter because that is where the ruling classes throw their guilty secrets." -Gerald Priestland "The Founding Fathers gave the free press the protection it must have to bare the secrets of government and inform the people." -Hugo Black'''
        pubKeyFilename = 'al_sweigart_pubkey.txt'
        encryptedText = encryptAndWriteToFile(filename, pubKeyFilename, message)
        print('Encrypted text:')
        print(encryptedText)
    elif mode == 'decrypt':
        privKeyFilename = 'al_sweigart_privkey.txt'
        decryptedText = readFromFileAndDecrypt(filename, privKeyFilename)
        print('Decrypted text:')
        print(decryptedText)

內容解密：

1. 程式首先設定預設的區塊大小和位元組大小。
2. 根據模式的不同，程式會呼叫不同的函式進行加密或解密。
3. 加密時，程式使用公鑰對訊息進行加密，並將加密後的訊息寫入檔案。
4. 解密時，程式使用私鑰對檔案中的加密訊息進行解密，並輸出解密後的訊息。

公鑰密碼學與RSA加密演算法的技術深度解析

ASCII：使用數字表示字元的基礎

在電腦中，所有資料都以數字的形式儲存。美國資訊交換標準碼（ASCII）是一種將數字對應到字元的編碼系統。ASCII使用單一位元組（8位元）來表示一個字元，這意味著它可以表示0到255之間的數字，總共256個不同的值。例如，字串 ‘Hello’ 在電腦中實際上是以數字72、101、108、108和111來儲存的，這些數字佔用了5個位元組的記憶體空間。

chr() 和 ord() 函式的使用

在Python中，chr() 函式可以將一個整數ASCII碼轉換為對應的字元，而 ord() 函式則可以將一個字元轉換為其對應的整數ASCII碼。這兩個函式是處理字元和數字之間轉換的基本工具。

>>> chr(65)
'A'
>>> ord('A')
65
>>> chr(73)
'I'
>>> chr(65+8)
'I'
>>> chr(52)
'4'
>>> chr(ord('F'))
'F'
>>> ord(chr(68))
68

內容解密：

1. chr(65) 傳回字元 ‘A’，因為65是 ‘A’ 的ASCII碼。
2. ord('A') 傳回65，表示 ‘A’ 的ASCII碼是65。
3. chr(73) 傳回 ‘I’，因為73是 ‘I’ 的ASCII碼。
4. chr(65+8) 等於 chr(73)，所以傳回 ‘I’。
5. chr(52) 傳回 ‘4’，因為52是 ‘4’ 的ASCII碼。
6. chr(ord('F')) 先計算 ord('F') 得到70，然後 chr(70) 傳回 ‘F’。
7. ord(chr(68)) 先計算 chr(68) 得到 ‘D’，然後 ord('D') 傳回68。

區塊加密的概念

在密碼學中，一個「區塊」是指固定長度的一串位元。在RSA加密演算法中，一個區塊被表示為一個整數。我們將區塊大小設定為128位元組，即1024位元。這意味著我們的訊息字串將被轉換成多個整數值（即多個區塊）。

# 區塊大小設定為128位元組
block_size = 128

內容解密：

1. 區塊大小的選擇直接影響到RSA加密演算法的安全性和效率。
2. 在本例中，我們設定區塊大小為128位元組，以確保有足夠的安全性。

將字串轉換為大整數的方法

為了將字串轉換為可以用於RSA加密的大整數，我們需要將多個小整數（即字元的ASCII碼）合併成一個大整數。這可以透過以下公式實作：將每個字元的ASCII碼乘以256的相應次方，然後將所有這些乘積加起來。

例如，對於字串 ‘Hello world!’，我們可以按照以下步驟計算其對應的大整數：

def string_to_large_integer(s):
    result = 0
    for i, char in enumerate(s):
        result += ord(char) * (256 ** i)
    return result

# 示例
large_integer = string_to_large_integer('Hello world!')
print(large_integer)

內容解密：

1. string_to_large_integer 函式將輸入的字串轉換為一個大整數。
2. 對字串中的每個字元，計算其ASCII碼並乘以256的相應次方，然後累加到結果中。
3. 最終傳回的大整數代表了原始字串。

公鑰密碼學與RSA加密演算法

公鑰密碼學是一種重要的密碼學技術，允許在不安全的通道上進行安全的資訊傳輸。RSA加密演算法是公鑰密碼學中最著名和最廣泛使用的一種演算法。

將字串轉換為區塊

在RSA加密演算法中，明文首先被轉換為一系列的整數區塊。每個區塊代表了一段固定長度的字串。這個轉換過程是透過將字串中的每個字元轉換為其ASCII值，然後將這些值組合成一個大整數來實作的。

表24-2：將字串編碼為區塊

程式碼範例：將字串轉換為區塊

def getBlocksFromText(message, blockSize=128):
    # 將字串訊息轉換為區塊整數列表
    messageBytes = message.encode('ascii') 
    blockInts = []
    for blockStart in range(0, len(messageBytes), blockSize):
        blockInt = 0
        for i in range(blockStart, min(blockStart + blockSize, len(messageBytes))):
            blockInt += messageBytes[i] * (256 ** (i % blockSize))
        blockInts.append(blockInt)
    return blockInts

#### 內容解密：

此函式getBlocksFromText用於將輸入的字串訊息轉換為一列表的整數區塊，每個整數代表128（或設定的區塊大小）個字元。函式首先將字串編碼為位元組物件messageBytes，然後遍歷這些位元組，將它們分組為固定大小的區塊，並計算每個區塊對應的整數值。最後，將這些整數值新增到列表blockInts中並傳回。

字串與位元組之間的轉換

在處理字串和位元組之間的轉換時，我們使用了encode()方法和decode()方法。encode()方法將字串轉換為位元組物件，而decode()方法則將位元組物件轉換回字串。

程式碼範例：字串與位元組之間的轉換

# 將字串轉換為位元組
spam = 'hello'.encode('ascii')
print(spam)  # b'hello'
print(list(spam))  # [104, 101, 108, 108, 111]

# 將位元組轉換為字串
spamBytes = bytes([104, 101, 108, 108, 111])
print(spamBytes.decode('ascii'))  # hello

#### 內容解密：

這段程式碼展示瞭如何使用encode()方法將字串轉換為位元組物件，以及如何使用decode()方法將位元組物件轉換回字串。位元組物件可以被視為一個整數列表，每個整數代表一個位元組的值。list()函式可以用來將位元組物件轉換為整數列表，而bytes()函式則可以用來從整數列表建立位元組物件。

公鑰密碼學與RSA加密演算法的實作細節

在探討公鑰密碼學及RSA加密演算法的實作時，我們首先需要了解其背後的數學原理以及如何將這些原理轉化為可執行的程式碼。RSA演算法是一種非對稱加密演算法，廣泛應用於安全資料傳輸。

區塊整數的計算

在RSA加密演算法的實作中，將明文訊息轉換為一串大型整數（區塊整數）是關鍵步驟之一。這個過程涉及將訊息按固定大小（例如128位元組）分成區塊，每個區塊再被轉換成一個大型整數。

程式碼解析

blockInts = []
for blockStart in range(0, len(messageBytes), blockSize):
    blockInt = 0
    for i in range(blockStart, min(blockStart + blockSize, len(messageBytes))):
        blockInt += messageBytes[i] * (BYTE_SIZE ** (i % blockSize))
    blockInts.append(blockInt)
return blockInts

內容解密：

1. 區塊整數列表初始化：首先，建立一個空列表blockInts用於存放計算出的區塊整數。
2. 迴圈遍歷訊息位元組：使用for迴圈遍歷messageBytes，步長為blockSize（預設128位元組），以此劃分訊息區塊。
3. 計算區塊整數：對於每個區塊，透過內層for迴圈計算區塊整數blockInt。這涉及到將每個字元的ASCII值乘以BYTE_SIZE（256）對應索引的冪，並累加到blockInt。
4. 相對索引的計算：由於i代表的是在整個訊息中的索引，因此使用i % blockSize來取得相對於當前區塊的索引，以正確計算每個字元對區塊整數的貢獻值。
5. 儲存區塊整數：計算完成後，將blockInt新增到blockInts列表中。
6. 傳回結果：最終傳回包含所有區塊整數的列表。

min()和max()函式的使用

在上述程式碼中，min()函式被用來確定內層迴圈的結束索引，確保不會超出messageBytes的範圍。min()函式傳回其引數中的最小值，可以用於數字或列表/元組中的元素。

例子

>>> min(13, 32, 13, 15, 17, 39)
13
>>> min([31, 26, 20, 13, 12, 36])
12

類別似地，max()函式用於找出引數中的最大值。

RSA 密碼學與公開金鑰加密技術

解碼區塊整數為原始訊息

getTextFromBlocks() 函式的作用是將一串區塊整數轉換回原始的訊息字串。這個函式需要原始訊息的長度，以正確地從最後一個區塊整數中還原出完整的字串。

函式實作

def getTextFromBlocks(blockInts, messageLength, blockSize=DEFAULT_BLOCK_SIZE):
    message = []
    for blockInt in blockInts:
        blockMessage = []
        for i in range(blockSize - 1, -1, -1):
            if len(message) + i < messageLength:
                asciiNumber = blockInt // (BYTE_SIZE ** i)
                blockInt = blockInt % (BYTE_SIZE ** i)
                blockMessage.insert(0, chr(asciiNumber))
        message.extend(blockMessage)
    return ''.join(message)

內容解密：

1. 訊息初始化：message 列表用於儲存從區塊整數計算出的字元字串。
2. 區塊處理迴圈：對於每個 blockInt，計算其代表的字元，並將它們儲存在 blockMessage 列表中。
3. 字元提取：使用迴圈從 blockSize - 1 到 0，計算每個字元的 ASCII 值，並將其插入到 blockMessage 的開頭。
4. 條件檢查：確保不會超出原始訊息的長度。
5. 區塊合併：將 blockMessage 中的字元新增到 message 列表中。
6. 最終結果：將 message 列表中的所有字元連線成一個字串並傳回。

RSA 加密與解密的數學原理

使用公鑰和私鑰中的 e、d 和 n，對區塊整數進行加密和解密的數學運算可以總結如下：

• 加密區塊 = 明文區塊 ^ e mod n
• 解密區塊 = 密鑰區塊 ^ d mod n

加密訊息函式

def encryptMessage(message, key, blockSize=DEFAULT_BLOCK_SIZE):
    encryptedBlocks = []
    n, e = key
    # 省略後續實作

內容解密：

1. 函式目的：將明文字串加密成一串整數區塊。
2. key 處理：將公鑰的兩個整數指定給 n 和 e。
3. pow() 函式：用於高效計算大整數的指數模運算。

重點解析

• getTextFromBlocks() 函式展示瞭如何從區塊整數還原始訊息，需要注意的是訊息長度的正確傳遞。
• encryptMessage() 函式開始展示如何使用公鑰進行加密，重點在於使用 pow() 函式進行高效的模冪運算。

與技術選型分析

RSA 密碼學依賴於大數質因數分解的難題，未來可探討更高效的演算法或新的密碼學體系，如橢圓曲線密碼學，以提升安全性與效率。