BLOG
投稿日：2023/08/16

ChatGPTを使ってのコード実装: RSA暗号を例に

小西です。皆さんはChatGPTを有効に使えているでしょうか？既にバリバリ活用されている方もいれば、何となく話には聞いているものの使えていない、使ってみたけど仕事に活用しきれていない方もいらっしゃるかと思います。
ChatGPTは日常や仕事での作文以外に、プログラムのコード生成でも有効に用いる事ができます。このブログ記事では、RSA暗号を例にしてChatGPTのコード作成での活用の方法をまとめました。ここではアルゴリズムやコードの書き方について分からない部分をChatGPTに聞き、ChatGPTが出力するコードを活用する事でコーディングを進めています。
本記事ではプログラム言語としてPython, ChatGPTについては3.5（2023/8現在で課金が必要ないもの）を用いています。

アカデメイアBlogでは、本記事以外にもこちらにGPTに関するものが掲載されていますので合わせてご参照ください。

RSAの概要

本記事ではRSAの暗号アルゴリズムを実装します。RSAのアルゴリズムについて簡単に解説します。

RSA暗号は、Rivest, Shamir, Adlemanによって1977年に開発された公開鍵暗号です[1]。公開鍵暗号は、暗号化と復号化で別の鍵を用いる形式の暗号で、公開鍵と呼ばれる鍵を用いて暗号化し、秘密鍵で復号化する手順をとります。秘密鍵を鍵の作成者のみが持つようにしていれば、暗号化された情報を誰も復号出来ないので安全に通信が可能、という事です。

RSA暗号は桁数の大きい数の素因数分解は難しい、という事を用いた暗号となっています。なので、高速な素因数分解が可能となるShorのアルゴリズム[2]が使えるような大規模な量子コンピュータが出来ると危ないのではとも言われています。2023年現在から見てそんな近い将来には実現しないのではとは思いますが。。現状では非常に強固な暗号として様々な場所で活用されています。（本記事の実装では小さい素数しか用いないので暗号としては弱いものとなります。現実には数百桁の素数が用いられているようです。）　特許も2000年に切れているので誰でも自由に利用できます。

このRSA暗号のアルゴリズムは下記の内容からなります。（ここの説明は下でChatGPTが答える内容と被っています）
  • 鍵生成
    • 素数p, qを選択
    • p, qの積nを計算
    • φ関数を計算（φ = (p-1)*(q-1)）
  • 公開鍵の生成
    • 公開鍵指数eとして、φと互いに素な数を選ぶ
    • 公開鍵は(e, n)
  • 秘密鍵の生成
    • (d*e)%φ ＝ 1 となるような秘密鍵指数dを求める
    • 秘密鍵は(d, n)
  • 暗号化
    • メッセージの各文字を数値化
    • 各数値Mに対して C = (M**e)%nで暗号化する
  • 復号化
    • 暗号化された各数値Cに対して M = (C**d)%nで復号化する
    • 復号化された各数値を文字列に変換する
以上となります。
これだけ書くと割と簡単そうですが、筆者は下記で詰まりました。
  • (d*e)%φ ＝ 1となるようなdってどう求めるんだっけ？
  • C = (M**e)%nてどう計算するんだっけ？
    • 上式をそのままプログラムに書くとeが大きくなるとまずそう
  • 文字列から数値、数値から文字への変換ってどうするんだっけ？
    • 自分の使う言語（本記事ではPython）でどう実装するか
この辺り、従来ならアルゴリズムや言語仕様等を調べて実装する事になります。
上記についてChatGPTを用いて対話的に解決できないかを試みました。

分かる部分のコード作成

ひとまず分かる部分に関してコードを作成します。公開鍵生成までは特に問題なく作成できそうです。

import random
import math

def get_e(phi):
    while True:
        x = random.randint(2, phi/2)*2 - 1
        if math.gcd(x, phi) == 1:
            return x

if __name__ == "__main__":
    random.seed(1)
    p = 3
    q = 11
    n = p*q
    print("integer n: ", n)
    phi = (p-1)*(q-1)
    print("Phi function: ", phi)
    e = get_e(phi)
    print("RSA public key: ({}, {})".format(e, n))

とりあえず公開鍵の生成まで実装してみました。eはどう選んでも良いようですが、ここではランダムに条件に合ったものを選択する仕様にしています。（random.seed(1)は結果が再現するように入れています）
素数としては、p=3, q=11を用いています。

こちらを実行すると出力は下記の通り。

integer n:  33
Phi function:  20
RSA public key: (7, 33)

とりあえずは良さそうです。このコードをベースにしてコードを追加していきます。

 

ChatGPTに質問

ここからの実装方法でよく分からない部分が多かったので、ChatGPTさんに質問を投げてみました。

まずは全体的な所から聞いてみます。
RSA暗号鍵のアルゴリズムを実装したいと考えています。大学生に説明するつもりで、手順について解説をお願いします。
「大学生に説明するつもりで」は筆者の頭のレベルに合わせて記載しています。（どの程度効果があるのかは謎）
答えは下記のように出力されます。
RSA（Rivest-Shamir-Adleman）暗号は、公開鍵暗号方式の一種で、安全な通信を行うために広く使用されています。RSA暗号は、公開鍵と秘密鍵のペアを使用して暗号化および復号化を行うことができるため、セキュリティが高い方法として知られています。以下に、RSA暗号鍵のアルゴリズムを大学生向けに解説します。
1. 鍵の生成:
1.1 素数の選択: RSA暗号の基盤となるのは、2つの大きな素数（pとq）です。これらの素数はランダムに選ばれる必要があり、十分に大きいものを選びます。なぜなら、素数の積を素因数分解するのは困難であると考えられているからです。
1.2 nの計算: nはpとqの積です。すなわち、n = p * q です。これは公開鍵として使われます。
1.3 φ(n)の計算: φ(n)（ファイ関数またはオイラーのトーシェント関数）は、n未満でnと互いに素な数の個数です。φ(n) = (p – 1) * (q – 1) となります。
1.4 公開鍵指数の選択: 通常、公開鍵の指数（e）として、φ(n)と互いに素な値を選びます。一般的な選択肢は、小さな素数である17や65537です。eは暗号化に使用されます。
1.5 秘密鍵指数の計算: 秘密鍵指数（d）は、公開鍵指数（e）とφ(n)を用いて、以下のように計算されます: d ≡ e⁻¹ (mod φ(n))。つまり、d * e を φ(n) で割った余りが 1 となるような d を求めます。
2. 暗号化:
2.1 メッセージの数値化: 暗号化するメッセージを数値化します。これには通常、文字列をASCIIコードなどの数値に変換する方法が使われます。
2.2 暗号化の計算: メッセージを暗号化するために、公開鍵指数（e）とnを使用して、暗号文 C を以下のように計算します: C ≡ M^e (mod n)。ここで、Mは数値化されたメッセージです。
3. 復号化:
3.1 暗号文の復号化: 暗号文 C を受け取った場合、秘密鍵指数（d）とnを使用して、元のメッセージ M を以下のように計算します: M ≡ C^d (mod n)。
3.2 数値を文字列に変換: 復号化された数値 M を元の文字列に戻すために、適切な変換を行います。例えば、ASCIIコードを文字列に戻すなどです。
これらがRSA暗号の基本的な手順です。公開鍵と秘密鍵の組み合わせによって、安全な通信を実現することができます。ただし、実際の実装では、さらにセキュリティや効率性に関する考慮事項が多くありますので、実際の使用にあたっては注意が必要です。
凄い！大体いい感じに説明されています。
続いてはコーディングに関する部分について質問していきます。まずは秘密鍵指数について質問します。
秘密鍵指数の計算について説明をお願いします。公開鍵指数eとファイ関数phiが求まっているとした場合にdを求めるPythonコードはどのように実装すれば良いでしょうか？
これに対しての回答は下記の通りです。
秘密鍵指数（d）を計算する際には、公開鍵指数（e）とファイ関数（φ）が与えられています。d * e ≡ 1 (mod φ) という条件を満たす d を求める必要があります。これは、拡張ユークリッドの互除法を使用して解決できます。以下に、Pythonコードでその手順を示します。
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_gcd(b, a % b)
        return d, y, x - y * (a // b)

def calculate_private_key(e, phi):
    gcd, x, y = extended_gcd(e, phi)
    
    # Ensure that the private key exponent (d) is positive
    d = x if x > 0 else x + phi
    
    return d

# Given values
e = 65537  # Public key exponent
phi = 46656  # Phi value (replace with the actual value)

# Calculate private key exponent
d = calculate_private_key(e, phi)
print("Private key exponent (d):", d)

このコードでは、`extended_gcd`関数を用いて拡張ユークリッドの互除法を実装し、秘密鍵指数（d）を計算しています。計算されたdが負の場合は、正の値に変換しています。

ただし、実際のRSA暗号では、一般的に鍵長や素数の選択、セキュリティ対策などが必要です。セキュリティに関する知識やツールの使用を通じて、より堅牢な実装を行うことが重要です。
dを計算するには拡張ユークリッドの互除法と呼ばれる方法を用いるようです。
上記のextended_gcd, calculate_private_keyをコピペしてコードを追加します。
# get_e関数の下に下記コードをコピーします。
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = extended_gcd(b, a % b)
        return d, y, x - y * (a // b)

def calculate_private_key(e, phi):
    gcd, x, y = extended_gcd(e, phi)
    
    # Ensure that the private key exponent (d) is positive
    d = x if x > 0 else x + phi
    
    return d

if __name__ == "__main__":
# print("RSA public key: ({}, {})".format(e, n))の文の下に下記コードを記載します。
    d = calculate_private_key(e, phi)
    print("RSA private key: ({}, {})".format(d, n))
実行してみます。
integer n:  33
Phi function:  20
RSA public key: (7, 33)
RSA private key: (3, 33)
ひとまず良さそうですね。では引き続き文字列の暗号化について質問します。

dが求まりました。ありがとうございます。

続いて任意の文字列を暗号化したいと考えています。Pythonでどのようなコードを書けば良いでしょうか？
これについての回答は以下のようになります。

RSA暗号を使用して任意の文字列を暗号化するためには、以下の手順に従ってPythonコードを実装できます。ただし、実際のセキュリティ上の運用には注意が必要であり、安全なライブラリを使用することが推奨されます。

以下は、Pythonの標準ライブラリのみを使用して文字列を暗号化する例です。しかし、実際にはより専門的なライブラリ（例：`cryptography`など）を使用することをおすすめします。
import random

# Function to perform modular exponentiation using repeated squaring
def mod_exp(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

# Encrypt a message using RSA public key
def encrypt(message, e, n):
    encrypted_message = [mod_exp(ord(char), e, n) for char in message]
    return encrypted_message

# Given public key (e, n)
e = 65537  # Public key exponent
n = 253804874693508157406763741479569491150529996606586323685179825620725204914673368682099888715317990176729163149244500499537007981536284372551801845546765556092699858430888558266101262215101051191899284541104207883272383804769632939218585758596276905152320547981501014718156518709505177987306091

# Message to encrypt
message = "Hello, RSA encryption!"

# Encrypt the message
encrypted_message = encrypt(message, e, n)

print("Original message:", message)
print("Encrypted message:", encrypted_message)
このコードは、指定された公開鍵（e, n）を使用して文字列を暗号化します。`mod_exp`関数は、モジュラ指数法（repeated squaring）を用いて効率的な指数計算を行います。ただし、セキュリティを考慮して、実際の運用では安全なライブラリを使用することをお勧めします。
C = (M**e)%nの計算はrepeated squaringとよばれる方法で素早く実行可能との事です。
また、Pythonにおいて文字charから文字コードへの変換はord(char)で実行出来るようです。
mod_exp関数とencrypt関数をコピペし、符号化部分を作成します。
# calculate_private_key関数の下に下記コードをコピーします。
def mod_exp(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

def encrypt(message, e, n):
    encrypted_message = [mod_exp(ord(char), e, n) for char in message]
    return encrypted_message

if __name__ == "__main__":
# print("RSA private key: ({}, {})".format(d, n))文の下に下記コードを記載します。
    message = "QUANTUM"

    # Encrypt the message
    encrypted_message = encrypt(message, e, n)

    print("Original message:", message)
    print("Encrypted message:", encrypted_message)
ここでmessageを「QUANTUM」としているのはNielsen, Chuangの教科書[3]を見ながらコードを作っていたためです。ここは任意のASCII文字列で実行可能です。
上記を実行すると下記の出力が得られます。
integer n:  33
Phi function:  20
RSA public key: (7, 33)
RSA private key: (3, 33)
Original message: QUANTUM
Encrypted message: [27, 13, 32, 12, 6, 13, 11]
実はこの時点で問題が発生しているのですが、ひとまず最後まで実装してしまいます。
復号化について質問します。
こちらのコードで暗号化した文字列を復号化するにはどのようにすれば良いでしょうか？Pythonコードを示してください。
これについての回答は以下の通りです。
暗号化されたメッセージを復号化するためには、秘密鍵を使用して復号化を行います。以下に、前のコードで暗号化したメッセージを復号化するためのPythonコードを示します。
# Decrypt an encrypted message using RSA private key
def decrypt(encrypted_message, d, n):
    decrypted_message = [chr(mod_exp(char, d, n)) for char in encrypted_message]
    return ''.join(decrypted_message)

# Given private key (d, n)
d = 151866547746253051295635226035893938791751845078785447899828018057531388462871545464706015227124468726243791927808641775756943107579456973792199785031609201199365234049843808423748718063366605801057175300794984536997489780732045509488007491731768743622439067912511699164119920532946691573524809997799878261

# Decrypt the encrypted message
decrypted_message = decrypt(encrypted_message, d, n)

print("Decrypted message:", decrypted_message)
このコードは、与えられた秘密鍵（d, n）を使用して暗号化されたメッセージを復号化し、元のメッセージを取得します。ただし、実際の運用では安全なライブラリを使用して復号化を行うことが重要です。
Pythonにおいて文字コードordから文字への変換はchar(ord)で実行出来るようです。
これも大丈夫そうなので、decrypt関数をコピペして、復号化部分のコードを追加します。
# encrypt関数の下に下記コードをコピーします。
def decrypt(encrypted_message, d, n):
    decrypted_message = [chr(mod_exp(char, d, n)) for char in encrypted_message]
    return ''.join(decrypted_message)

if __name__ == "__main__":
# print("Encrypted message:", encrypted_message)文の下に下記コードを追加します。
    decrypted_message = decrypt(encrypted_message, d, n)

    print("Decrypted message:", decrypted_message)




しかしここで実行時に問題が発生しました。decryptが上手くいきません。正常な文字コードになっていないためか文字が出力されていません（本来は元の文字列QUANTUMが出力されて欲しい）。








integer n: 33
Phi function: 20
RSA public key: (7, 33)
RSA private key: (3, 33)
Original message: QUANTUM
Encrypted message: [27, 13, 32, 12, 6, 13, 11]
Decrypted message:











何が問題なのでしょうか？


ここで、数が小さすぎるのでは？との疑問が出てきました。そもそもn=33では上手く符号化、復号化できていないのでは…










実際、”QUANTUM”の中でQをencodeした値を確認すると81となっています。このようにencodeした値がn(=33)より大きいために符号化、復号化が失敗しているようです。


とりあえず素数の組を大きめにしてみます。p=11, q=23でどうでしょうか。（コード内のp=3, q=11の部分を修正）










integer n:  253
Phi function:  220
RSA public key: (37, 253)
RSA private key: (113, 253)
Original message: QUANTUM
Encrypted message: [82, 101, 43, 144, 182, 101, 209]
Decrypted message: QUANTUM












今度はうまく行きました。文字列が符号化され、復号化した時に元の文字列に戻っているのが確認できています。


これでRSA暗号の実装はひとまず完成したようです。






 


（余談）上で少し触れたNielsen, Chuangの本[3]ではp=3, q=11で”QUANTUM”を符号化、復号化する問題が掲載されています。これは、ここでのプログラムにあるような文字コードを用いた符号化ではなく、アルファベットの大文字のみを5bit表現（(00000)~(11111)つまり10進数での0〜31）で表現する事としています。これだとp=3, q=11でも問題なく符号化、復号化が可能です。


まとめ






ここまででPythonによるRSAのコード実装が完成しました。（実際にRSA暗号を運用する際には自分で実装するよりもライブラリを利用して下さい）ChatGPTを利用する事であまり詳しく分かってない分野のアルゴリズムでも容易に実装できる場合があります。本記事では、拡張ユークリッドの互除法、繰り返し二乗法、文字と文字コードの間の相互変換などを事前知識なしに実装する事が出来ました。ただ、そのまま実装するだけでは問題が発生する事もあるので、コードを実行しながら内容を精査する必要はあります。本記事の場合は筆者側の問題でエラーが生じていましたが、そもそもChatGPTの提案するコードそのものにエラーの原因がある場合もあります。


 


ChatGPTに代表される文章生成AIは、知識面や文章作成力で大抵の人を凌駕しているように見えます。しかし詳細を見ると色々とヘマをしている事も多いようです。（筆者の実家周辺の情報を聞くとメチャクチャな内容を返してきます。田舎なので仕方ないですが。。）現状人間側で質問の仕方を工夫したり、回答の内容を検討する必要はありますが、文章をまとめる、コード作成の支援をしてもらうなどの際には非常に役に立つツールです。本記事を読んでいる皆様もぜひ文章生成AIを活用して生産性を高めていってください。








 


参考文献


[1] R. Rivest, A. Shamir, and L. Adleman, Communications of the ACM. 21 (2) 120 (1978)


[2] P. W. Shor, SIAM J. Comput., 26 1484 (1997), arXiv:quant-ph/9508027


[3] M. Nielsen and I. Chuang, “Quantum Computation and Quantum Information”, Cambridge University Press (2000)　量子コンピュータ、量子情報の教科書です。RSA暗号についてはAppendixに記載があります。