ハイブリッド暗号化が使われる理由（暗号化・復号化速度比較）

公開鍵方式(RSA)による暗号化・復号化は時間がかかることが知られており、ハイブリッドな暗号化が利用される。プログラム(Python)で暗号化復号化する方法のメモを兼ねて、実際に暗号化、復号化の速度を測ってみた。

# 1. 暗号化の種類
## 1.1. 対称暗号(共通鍵)方式
暗号化、復号化に同じ鍵を利用する方式。

### AES （ブロック暗号）
ブロック長は128ビット固定、鍵長は128ビット・192ビット・256ビットの３つを利用可。

#### 暗号利用モード
ブロック暗号でブロック長よりも長い情報を暗号化するための方法。

* ECB (Electronic CodeBook) モード
単純にブロック分割して暗号化。同じ平文は同じ暗号文になってしまう。非推奨とされる。

* CBC (Cipher Block Chaining) モード
前のブロックの暗号文とXORして暗号化。最もよく利用される。順次暗号化するので暗号化時に並列処理できない。

* CTR (CounTeR) モード
ブロック毎にカウンターをインクリメントして暗号化、平文とXORしてブロック暗号を作る。

## 1.2. 非対称暗号（公開鍵）方式
公開鍵で暗号化、プライベート鍵で復号化する方式。

### RSA暗号
大きな数の離散対数や素因数分解が困難なことを利用した暗号。
`暗号文=(平文**E) % N`
の{E, N}の組が暗号化時の公開鍵となる。
`平文=(暗号文**D) % N`
の{D, N}の組が復号化時のプライベート鍵となる。
Nとして2048ビット以上の数を用いる。2031年以降新規利用する場合は4096bit以上(ref. NIST SP800-57)。
公開鍵暗号方式でも通信の送受信者の間に悪意のある者が入ると通信を妨害できてしまう(MITM (man-in-the-middle)攻撃)。これを防ぐために公開鍵の証明書が利用される。
RSA-OAEPでは乱数を用いて、同じ平文でも毎回暗号文として異なるものが生成される。

### 楕円曲線暗号
RSAに比べて短い鍵でも強い（224~225ビットの鍵の楕円曲線暗号は2048bitのRSAと同じ強さに相当）。

# 2. ハイブリッド暗号化（公開鍵方式と共通鍵方式の併用）
数MB以上の大きなファイルを暗号化する場合、公開鍵方式では非常に暗号化、復号化に時間がかかることから共通鍵方式が用いられる。この際に利用する共通鍵を通信するために、公開鍵方式が利用される。両者の暗号強度は同程度が好ましいとされており、[NIST Special Publication 800-57 Part 1
Revision 4、「鍵管理における推奨事項」](https://www.ipa.go.jp/files/000055490.pdf)の表２に参考となるセキュリティ強度が記載されている。

| セキュリティ強度  |  秘密鍵（共通鍵）アルゴリズム | IFC（例．RSA） |
|:-------------------:|:--------------------:|:-----------------------:|
| 128 | AES-128 | k = 3072 |
| 192 | AES-192 | k = 7680 |
| 256 | AES-256 | k = 15360 |

# 3. 実際の処理時間比較
AES-256とRSA-2048の処理時間を比較した。(強度が違うけど...)

## 動作環境
* MacBook Pro, Intel Core i5 3.1 GHz, macOS 10.13.6
* Python 3.7.4
* 必要なパッケージをインストール
  `pip install pycrypto pyOpenSSL`

## 3.1 対称暗号方式(AES-256)での暗号化、復号化
[こちらのサイト](https://stackoverflow.com/questions/39128855/is-it-necessary-to-divide-a-file-into-chunks-for-encryption)を参考に以下のAES256.pyのように実装（実際にファイルの暗号化・復号化に利用するときはパディングを削除する必要がある）。

以下に示したAES256.pyを実行すると、

```bash

$ python3 AES256.py 
File size =  10.0 [MB]
Encode:
AES_encrypt_time:0.12138915061950684[sec]
Decode:
AES_decrypt_time:0.12209415435791016[sec]
```

のような結果が得られる。
10MBのファイルを暗号化、復号化するのに約0.12秒かかることがわかる。

```python:AES256.py
import sys,struct,random
from Crypto.Cipher import AES
from hashlib import sha256
import time
import os

def generate_salt(digit_num):
    DIGITS_AND_ALPHABETS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    return "".join(random.sample(DIGITS_AND_ALPHABETS, digit_num))

# AES-256
def derive_key_and_iv(password, salt, bs):
    salted = ''.encode()
    dx = ''.encode()
    # パスワードからAES-256用のkeyとCBC用の初期ベクトル(iv)を生成
    while len(salted) < 48: # 48 = AES256キー長(32byte)+IVの長さ(16byte)
        hash = dx + password.encode() + salt.encode()
        dx = sha256(hash).digest()
        salted = salted + dx
    key = salted[0:32] # 32byte -> AES-256のキーの長さ
    iv = salted[32:48] # 16byte (AES.block_sizeと同じサイズ, AESでは128bit(=16byte)固定)
    return key, iv

# 暗号化
def encrypt(in_file, out_file, password):
    bs = AES.block_size
    #salt = generate_salt() #Random.new().read(bs - len('Salted__'))
    salt = generate_salt(AES.block_size)
    key, iv = derive_key_and_iv(password, salt, bs)

    cipher = AES.new(key, AES.MODE_CBC, iv) # CBCモードを設定。AESCipherクラスを取得。 
    out_file.write(('Salted__' + salt).encode()) # saltは暗号化ファイルに書き込む
    finished = False
    while not finished:
        chunk = in_file.read(1024 * bs)
        orgChunkLen = len(chunk)
        if len(chunk) == 0 or len(chunk) % bs != 0:
            padding_length = (bs - len(chunk) % bs) or bs
            padding = padding_length * chr(padding_length)
            chunk += padding.encode()
            finished = True
        if len(chunk) > 0:
            out_file.write(cipher.encrypt(chunk))

# 復号化
def decrypt(in_file, out_file, password):
    bs = AES.block_size
    in_file.seek(len('Salted__'))
    salt = in_file.read(16).decode()
    # saltとパスワードからkey, ivを得る。
    key, iv = derive_key_and_iv(password, salt, bs)

    cipher = AES.new(key, AES.MODE_CBC, iv) # CBCモードを設定。AESCipherクラスを取得。
    finished = False

    while not finished:
        chunk = in_file.read(1024 * bs)
        orgChunkLen = len(chunk)
        if orgChunkLen == 0 or orgChunkLen % bs != 0:
            padding_length = (bs - orgChunkLen % bs) or bs
            padding = padding_length * chr(padding_length)
            chunk += padding.encode()
            finished = True
        if orgChunkLen > 0:
            out_file.write(cipher.decrypt(chunk)[0:orgChunkLen])

def main(filename):
    infile = open(filename, "rb")
    outfile = open(filename+"_AES.bin", "wb")

    print("File size = ", os.path.getsize(filename) /1024/1024, "[MB]")
    print("Encode:")
    start = time.time()
    encrypt(infile,outfile,"password")
    # openssl enc -e -aes-256-cbc -salt -k "password" -in practice.bin -out practice_aes.bin
    elapsed_time = time.time() - start
    print ("AES_encrypt_time:{0}".format(elapsed_time) + "[sec]")

    infile.close()
    outfile.close()

    print("Decode:")

    outinfile = open(filename+"_AES.bin", "rb")
    outfile2 = open(filename+"_dec_AES.bin", "wb")

    start = time.time()
    decrypt(outinfile,outfile2,"password")
    elapsed_time = time.time() - start
    print ("AES_decrypt_time:{0}".format(elapsed_time) + "[sec]")

    outinfile.close()
    outfile2.close()

if __name__== "__main__":
  filename = "practice.bin"
  main(filename)
```

## 3.2. 非対称暗号（公開鍵）方式(RSA)での暗号化、復号化
基本的にRSAは大きなサイズのデータを暗号化するために利用されることを想定していない。速度測定のためにチャンクに分けて実装したが、一般に推奨されるものではない。大きなサイズのデータはAESなど対称暗号を利用して暗号化する。

[こちらのサイト](https://stackoverflow.com/questions/51228645/how-can-i-encrypt-with-a-rsa-private-key-in-python)を参考にコード改変し、196byteのチャンク単位で暗号化するようにした。

以下に示したRSA2048.pyを実行すると、

```bash

$ python3 RSA2048.py 
max_data_len= 196
Generate Key:
privatePem len =  1674
publicPem len =  450
Load Key:
File size =  10.0 [MB]
Encode:
RSA_encrypt_time:46.78378772735596[sec]
Decode:
RSA_decrypt_time:123.22586274147034[sec]
```

のような結果が得られる。
10MBのファイルを暗号化するのに約47秒、復号化するのに約123秒かかることがわかる。
AESではそれぞれ約0.12秒だったため、RSAは暗号化で約400倍遅く、復号化では約1000倍遅いことがわかる。

```python:RSA2048.py

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import base64
import time
import os

modulus_length = 2048 # bit
max_data_len = int((int(modulus_length/8.0) - 11 )*0.8)  # RSAで暗号化できる最大サイズはキーサイズより小さい。パディングに何を使うかに依存。
print("max_data_len=",max_data_len)

def generate_keys():
    key = RSA.generate(modulus_length)
    pub_key = key.publickey()
    return key, pub_key

def encrypt_private_key(a_message, private_key):
    encryptor = PKCS1_OAEP.new(private_key)
    encrypted_msg = encryptor.encrypt(a_message)
    encoded_encrypted_msg = base64.b64encode(encrypted_msg)
    return encoded_encrypted_msg

def decrypt_public_key(encoded_encrypted_msg, public_key):
    encryptor = PKCS1_OAEP.new(public_key)
    decoded_encrypted_msg = base64.b64decode(encoded_encrypted_msg)
    decoded_decrypted_msg = encryptor.decrypt(decoded_encrypted_msg)
    return decoded_decrypted_msg

def encrypt_file(in_file, out_file, key):
    finished =False
    while not finished:
        chunk = in_file.read(max_data_len)
        if len(chunk) == 0 or len(chunk)%max_data_len:
            finished = True
        encdata = encrypt_private_key(chunk, key)
        a_number = len(encdata)
        out_file.write(a_number.to_bytes(4, byteorder='little'))
        out_file.write(encdata)
    out_file.close()

def decrypt_file(in_file, out_file, key):
    finished =False
    while not finished:
        bnum = in_file.read(4)
        inum = int.from_bytes(bnum, byteorder='little')
        chunk = in_file.read(inum)
        if len(chunk) == 0 or len(chunk)%inum:
            finished = True
        if len(chunk) != 0:
          decdata = decrypt_public_key(chunk, key)
          out_file.write(decdata[0:len(chunk)])
    out_file.close()

def main(filename):
    print("Generate Key:")
    private, public = generate_keys()
    privateFile = open("private.pem","wb")
    privatePem = private.exportKey(format='PEM')
    print("privatePem len = ", len(privatePem))
    privateFile.write(privatePem)
    privateFile.close()
    publicFile = open("public.pem","wb")
    publicPem = public.exportKey(format='PEM')
    print("publicPem len = ", len(publicPem))
    publicFile.write(publicPem)
    publicFile.close()
    #print (private)
    #message = b'AES password or key'
    #print(message)
    #encoded = encrypt_private_key(message, public)
    #decrypt_public_key(encoded, private)

    print("Load Key:")
    privateFile = open("private.pem","rb")
    private_pem = privateFile.read()
    privateFile.close()
    private_key = RSA.importKey(private_pem)
    publicFile = open("public.pem","rb")
    public_pem = publicFile.read()
    publicFile.close()
    public_key = RSA.importKey(public_pem)

    print("File size = ", os.path.getsize(filename) /1024/1024, "[MB]")

    print("Encode:")
    infile = open(filename, "rb")
    outfile = open(filename+"_RSA.bin", "wb")
    start = time.time()
    encrypt_file(infile,outfile,public_key)
    elapsed_time = time.time() - start
    print ("RSA_encrypt_time:{0}".format(elapsed_time) + "[sec]")
    infile.close()
    outfile.close()

    print("Decode:")
    infile = open(filename+"_RSA.bin", "rb")
    outfile = open(filename+"_dec_RSA.bin", "wb")
    start = time.time()
    decrypt_file(infile,outfile,private_key)
    elapsed_time = time.time() - start
    print ("RSA_decrypt_time:{0}".format(elapsed_time) + "[sec]")
    infile.close()
    outfile.close()


if __name__== "__main__":
    filename = "practice.bin"
    main(filename)
```

# 4. まとめ
　実際のTSLやPGP(GnuPG)では公開鍵方式で対称暗号方式の鍵（に相当するデータ）をやりとりし、実際のデータは対称暗号が使われるが、これは処理速度に大きな違いがあり、公開鍵方式の暗号化・復号化は時間がかかるためとされる。
　ここでは実際にどの程度処理速度に違いがあるのかをオーダーレベルで確認するため、対称暗号方式(AES)と公開鍵方式(RSA)に関してPythonのテストコードを作成して比較した。
　実測の結果、10MBのファイルを暗号化・復号化するのに、AESでは約0.12秒だったのに対して、RSAは暗号化するのに約47秒で約400倍遅く、復号化は約123秒で約1000倍遅いことがわかった。

# 参考図書
* 暗号技術入門　第３版、結城浩、SBクリエイティブ, 2015