Pythonを使って、RSA暗号を調べてみました

こんにちは。エンジニアの内藤です。

開発やサーバー業務をしていると、秘密鍵を扱うことは多いと思いますが、今回はその中でも非常によく利用されるRSA暗号について、その仕組みをPythonで調べてみました。

RSA鍵の作成

まず、普通に ssh-keygen コマンドを使って RSA鍵を作成してみましょう。

% ssh-keygen -t rsa -f ./id_sample_rsa

すると、つぎのようなメッセージが表示されて、

The key fingerprint is:
SHA256:IAE30v3trC/sF0rLvI/6q0ISHgDHeVS6jPBE3b86xR8 knaito@knaitonoMacBook-Air.local

The key's randomart image is:
+---[RSA 3072]----+
|o.=*=+.          |
|.ooo++o          |
|....o .o .       |
| +oo o .o .      |
| .ooo  .S+       |
|  o .   = E      |
|   o   B = o     |
|    . o O.o      |
|     .o**Bo      |
+----[SHA256]-----+

秘密鍵ファイル id_sample_rsaと公開鍵 id_sample_rsa.pubが作成されます。メッセージに記載されているRSA 3072というのは、これが3072ビットの暗号鍵であることを示しています。

今回は、これらのファイルを調べてみます。これらはテキストファイルなのですが、秘密鍵の方は

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAABlwAAAAdzc2gtcn
NhAAAAAwEAAQAAAYEAsqF/TKyA9Xc60rYLLRzHVFO1/YvF6L3yMgCDH373TbW1e8xHWST3
...
oO8Zd0rHyQUV0AAAAga25haXRvQGtuYWl0b25vTWFjQm9vay1BaXIubG9jYWwBAgM=
-----END OPENSSH PRIVATE KEY-----

といった形していて、一方、公開鍵の方は

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQCyoX9MrID1dzrStgstHMdUU7X9i8XovfIyAIMffvdNtbV7zEdZJPcxtW78Mb+Z6HQgBNWQMvK24gYBo8SrlRzNKe6WcOldirTadi1/Jc9WuI9tSd5LaeQDzhMaIxYrc55oLOdOoT8xRDWbFJ8PtEvx1jaG3VQpnUHZ4l8OfViKlWdubR7LHXNOn72Ovz3cgqaaFvcQ6vKzAmkehTk3DhRo7T75XBXM0F4ZumDansIdyW0w3JsUaVi2GtZ7J0hSd+TXYFyO+O6gH8FT3K+8+lhKEbOrTSbLfiEigpobPGYWNSEPuKyfJh981V5FQ23YelluU7c5HsdFWZKEriFe1J4bekVWxrOv8KHEf5sKkvRKmN786qHo6onSiktUa2LjI3ou/JJlOAsJ+WeEzfqBaDaD6H0J5gjcr8zDOLe5LBXpLGWtiEstSvcMIT8ieIrJDOHd2RBxwsP48t9yK2vlMq4ZY79/llvWar4cz/G0YD7DDLtGLGMQgqo+v2vlsY7OQD0= knaito@knaitonoMacBook-Air.local

のような形をしています。エンジニアやサーバー管理者であれば、よく見慣れたファイルだと思います。

しかし、これを見ただけでは、何を意味しているのかがよく分かりません。実は、秘密鍵の方は次の5つの自然数から成り立っています。

公開モジュラス: n
素因数p: p
素因数q: q
公開指数: e
秘密指数: d

なお、このうち、秘密鍵の機能として必要なのは公開モジュラス nと秘密指数 dのみです。

一方、公開鍵の方は、次の2つの自然数から成り立っています。

公開モジュラス: n
公開指数: e

この記事では、これらの数値をPythonを使って読み取ってみる方法について紹介します。

RSA鍵の復習

まず、これらの関係を簡単に復習しておきましょう。最近ではNHKの笑わない数学でも扱っていたようですが、残念なことに私は見逃してしまいました。再放送に期待しています。

さて、先に述べたRSA鍵の5つの要素

公開モジュラス: n
素因数p: p
素因数q: q
公開指数: e
秘密指数: d

のうち、p, qは素数で

n = p × q
e × d = 1 mod (p-1)(q-1)

という関係があります。( (p-1)(q-1)は、オイラーのトーシェント関数 \phi(n)とも言います）
そして、ある自然数xを公開鍵eで暗号化するとは

c = x^e mod n

によって、暗号化されたcを得ることです。
逆にcを秘密鍵dで複合するとは

x = c^d mod n

でxを復元するということになります。

試しに、簡単な場合について試してみましょう。例えば、n=33, p=11, q=3, e=3, d=7という組み合わせを使ってみます。このとき、

n = 33 = 11 × 3 = p × q
e × d = 3 × 7 = 21 = 1 mod 20 = 1 mod (11-1)×(3-1)

なので、条件を満たしています。

いま、x=13とすると、これを暗号化すると、次のpythonコードで

n=33
p=11
q=3
e=3
d=7

x=13

c = x ** e % n
print("x = {} を暗号化するとc = {} になります".format(x, c))

となり、これを実行すると

x = 13を暗号化するとc = 19になります

という結果になります。つまり、13を暗号化して19になったということですね。

次に、cからxを複合化してみましょう。先のコードに次の2行を付け足して実行します。

y = c ** d % n
print("c = {} を複合化するとy = {} になります".format(c, y))

実行結果は

x = 13 を暗号化するとc = 19 になります
c = 19 を複合化するとy = 13 になります

となり、無事に元の数 y=13 を復元できました。
（注意：一度に暗号化・複合化出来るのは、n より小さい数のみになります。それより大きな数を扱い場合は、n より小さい数に分割して、それぞれ暗号化・複合化します）

RSA鍵の読み取り

それでは、最初に作成した秘密鍵、公開鍵をpythonで読み取ってみましょう。

そのために、まず paramikoとcryptographyというライブラリが必要になります。pipコマンドで次のようにインストールできます。

pip install paramiko cryptography

なお、私の環境は

python: 3.8.12
paramiko: 3.5.0
cryptography: 43.0.1

です。

まず公開鍵の読み取りですが、これは次のようなコードで読み込むことが出来ます。（読み込む公開鍵のファイル名は、id_sample_rsa.pubとしていますが、適時修正して下さい）

import base64
import struct

def get_rsa_parameters_from_ssh_key(ssh_key):
    # 公開鍵のプレフィックスを削除して、Base64エンコードされた部分を抽出
    key_body = ssh_key.strip().split()[1]
    key_data = base64.b64decode(key_body)

    # バイナリデータの解析
    def read_int(data):
        length = struct.unpack('>I', data[:4])[0]
        integer = int.from_bytes(data[4:4+length], byteorder='big')
        return integer, data[4+length:]

    # ssh-rsa ヘッダーをスキップ
    key_data = key_data[11:]

    # e を抽出
    e, key_data = read_int(key_data)

    # n を抽出
    n, key_data = read_int(key_data)

    return e, n

# 公開鍵文字列

public_key_path = "id_sample_rsa.pub"
with open(public_key_path, "rb") as key_file:
    # e と n を取得
    e, n = get_rsa_parameters_from_ssh_key(key_file.read())
    print(f"n: {n}")
    print(f"e: {e}")

これを実行すると、次のような結果になります。

n: 4053808005805138744143524914178891976137358379780846884293760626635987451601969822003722231067381605450758783282561745014078171157120939620466066170862722550381676261111946671083038727610265770487220625116168950486190651328821888348785271419477402895762371737974121077340403020088239140705142853333802628825022425824513373218115536138352239257799428059469510124817133097980723114306327652059965921387717657969517414772865191711946131786615768460952859635884888837150098856736336670029308174160316030704962311513542614244321548727097330825374973077124452646980361107087539819488867797531609682509294916343178041539935250552452814352825475264855026770846480350458308685060002595514799142972660924974821500913291916864313580939234473290192170747510480995648057647428143204153568980306205633402120862765346812929761660666067512453418299515657726062561967354253649275815193867839741150712520136250929179627948824165334407722188861
e: 65537

nは非常に大きな数になりますが、pythonはメモリの許す限り大きな整数を扱えるので大丈夫です。これがpythonの魅力の一つですね。

次に、秘密鍵を読み取ってみましょう。これは paramiko を使って、次のコードで読み取ることが出来ます。（読み込む秘密鍵のファイル名は、id_sample_rsaとしていますが、適時修正して下さい）

import paramiko

# 秘密鍵ファイルのパスを指定
private_key_path = "id_sample_rsa"

# 秘密鍵を読み込む
private_key = paramiko.RSAKey.from_private_key_file(private_key_path)

# RSA秘密鍵の内部オブジェクトを取得
rsa_private_key = private_key.key  # このオブジェクトはcryptographyライブラリのRSA秘密鍵オブジェクトです

# 秘密鍵の数値パラメータを取得
private_numbers = rsa_private_key.private_numbers()

# RSAパラメータの取得
n = private_numbers.public_numbers.n  # モジュラス
e = private_numbers.public_numbers.e  # 公開指数
d = private_numbers.d                 # 秘密指数
p = private_numbers.p                 # 素因数p
q = private_numbers.q                 # 素因数q

# 結果を表示
print(f"n (モジュラス): {n}")
print(f"e (公開指数): {e}")
print(f"d (秘密指数): {d}")
print(f"p (素因数p): {p}")
print(f"q (素因数q): {q}")

これの実行結果は次のようになります。

n: 4053808005805138744143524914178891976137358379780846884293760626635987451601969822003722231067381605450758783282561745014078171157120939620466066170862722550381676261111946671083038727610265770487220625116168950486190651328821888348785271419477402895762371737974121077340403020088239140705142853333802628825022425824513373218115536138352239257799428059469510124817133097980723114306327652059965921387717657969517414772865191711946131786615768460952859635884888837150098856736336670029308174160316030704962311513542614244321548727097330825374973077124452646980361107087539819488867797531609682509294916343178041539935250552452814352825475264855026770846480350458308685060002595514799142972660924974821500913291916864313580939234473290192170747510480995648057647428143204153568980306205633402120862765346812929761660666067512453418299515657726062561967354253649275815193867839741150712520136250929179627948824165334407722188861
e: 65537
knaito@knaitonoMacBook-Air secret_key2 % python read_private_key.py 
n (モジュラス): 4053808005805138744143524914178891976137358379780846884293760626635987451601969822003722231067381605450758783282561745014078171157120939620466066170862722550381676261111946671083038727610265770487220625116168950486190651328821888348785271419477402895762371737974121077340403020088239140705142853333802628825022425824513373218115536138352239257799428059469510124817133097980723114306327652059965921387717657969517414772865191711946131786615768460952859635884888837150098856736336670029308174160316030704962311513542614244321548727097330825374973077124452646980361107087539819488867797531609682509294916343178041539935250552452814352825475264855026770846480350458308685060002595514799142972660924974821500913291916864313580939234473290192170747510480995648057647428143204153568980306205633402120862765346812929761660666067512453418299515657726062561967354253649275815193867839741150712520136250929179627948824165334407722188861
e (公開指数): 65537
d (秘密指数): 1034343614646284237599646361824609482047834152107898158279449245443138718062897895288863438178567148425280198575628995836327802280992055668300861475337083578550778803398293669741528809727312269620020801885844289333202314288425768908683450702297955829881416302278152076770163713656644871002203317110149191437081724897958597844779712151998506871979523566999544506266568498167960875801919694184151702663311025475170822738786513508509135537723558908769911940297345180087441288431096763060063839491651794586752234639583339513465223421550442326798358690273317043477097014030724153824763147753385435135986366247542353431541670719046193275226271355340383967935324284548493113665982989425952507995656056633593043336504985082479035349146367751319083636991965421682742756350481520402851985745351580158205279004899441213854135292106406974619006315374801770920546932579686882926698880908067451283981779716141801464381304194416337317424385
p (素因数p): 2124374344742583384102849289186677156419529691466485731645388249020229497512127025039858192812237515063965697237470938901617438715431798627672494191757139381376979970040634263309024855074265522547676351413134529270456244783819810386343716108044021114187609705892256596514230887626549706729322645289624965432630947771735137009229178631845967199109474726805703824498306889710963128467470877162132251776349241339344475266237102836707291735625056297287451331147750497
q (素因数q): 1908236190028151769321542974869322185980685508363384276350041399971300835419970586867284058000132242825293139743289696482667333192737875520534983382324181679849188286922016343769312844576225895750607899552135524325058037105444483657660181622916841236395730992635962118893040652555385936457401724280842197780932876525531174681532809509346356370258969001517415619907293815205321413546483275079068237635432519652160376723202943080116727669898649162867031294564389213

これまた大きな数がいろいろ出てきましたが、このようにして、pythonで公開鍵と秘密鍵の中身を読み取る事ができました。

RSA暗号鍵のセキュリティ

公開鍵はnとeの情報しか持っていません。

しかし、nは自然数ですから、原理的には素因数分解することが出来ます。しかも後に書くように、nを素因数分解して素因数pと素因数qが求められてしまえば、暗号指数dも求める事が出来るので、そこから暗号鍵を復元することが可能です。

もちろんnが小さいと、すぐに素因数分解出来てしまいますから、公開鍵から簡単に秘密鍵を再現されてしまいます。そこで、非常に大きなnを使う事が必要になり、これがRSA暗号のセキュリティを担保している、ということですね。今回は3072ビットで作成しましたが、最近では4096ビットくらいがよく使われているようです。

また、素因数p,qと公開鍵の公開指数eの情報を使うと、秘密指数pを取得出来てしまいます。pythonでは、モジュロ逆元（nを法とした逆元)を簡単に計算出来る pow関数があるため、次のような関数で求められます。

def calculate_private_key_d(p, q, e):
    # オイラーのトーシェント関数 phi(n) を計算
    phi_n = (p - 1) * (q - 1)

    # 秘密指数 d を計算
    # d = e^(-1) mod phi(n) (modular multiplicative inverse)
    d = pow(e, -1, phi_n)

    return d

例えば、今回の場合であれば、

# 素因数 p（整数）
p = 2124374344742583384102849289186677156419529691466485731645388249020229497512127025039858192812237515063965697237470938901617438715431798627672494191757139381376979970040634263309024855074265522547676351413134529270456244783819810386343716108044021114187609705892256596514230887626549706729322645289624965432630947771735137009229178631845967199109474726805703824498306889710963128467470877162132251776349241339344475266237102836707291735625056297287451331147750497

# 素因数 q（整数）
q = 1908236190028151769321542974869322185980685508363384276350041399971300835419970586867284058000132242825293139743289696482667333192737875520534983382324181679849188286922016343769312844576225895750607899552135524325058037105444483657660181622916841236395730992635962118893040652555385936457401724280842197780932876525531174681532809509346356370258969001517415619907293815205321413546483275079068237635432519652160376723202943080116727669898649162867031294564389213

# 公開指数（整数）
e = 65537

# 秘密指数 d を計算
d = calculate_private_key_d(p, q, e)
print(f"秘密指数 d: {d}")

を実行すると

秘密指数 d: 1034343614646284237599646361824609482047834152107898158279449245443138718062897895288863438178567148425280198575628995836327802280992055668300861475337083578550778803398293669741528809727312269620020801885844289333202314288425768908683450702297955829881416302278152076770163713656644871002203317110149191437081724897958597844779712151998506871979523566999544506266568498167960875801919694184151702663311025475170822738786513508509135537723558908769911940297345180087441288431096763060063839491651794586752234639583339513465223421550442326798358690273317043477097014030724153824763147753385435135986366247542353431541670719046193275226271355340383967935324284548493113665982989425952507995656056633593043336504985082479035349146367751319083636991965421682742756350481520402851985745351580158205279004899441213854135292106406974619006315374801770920546932579686882926698880908067451283981779716141801464381304194416337317424385

となります。

では、最後に、これらn, p, q, e, dを使って、暗号鍵ファイルを作成してみましょう。それはcryptographyとparamikoというライブラリを使って、次のようなコードになります。作成された暗号鍵ファイルのファイル名は my_openssh_private_keyとしています。

import paramiko
from cryptography.hazmat.primitives.asymmetric import rsa

# 与えられたRSAパラメータを整数で指定

# モジュラス（整数）
n = 4053808005805138744143524914178891976137358379780846884293760626635987451601969822003722231067381605450758783282561745014078171157120939620466066170862722550381676261111946671083038727610265770487220625116168950486190651328821888348785271419477402895762371737974121077340403020088239140705142853333802628825022425824513373218115536138352239257799428059469510124817133097980723114306327652059965921387717657969517414772865191711946131786615768460952859635884888837150098856736336670029308174160316030704962311513542614244321548727097330825374973077124452646980361107087539819488867797531609682509294916343178041539935250552452814352825475264855026770846480350458308685060002595514799142972660924974821500913291916864313580939234473290192170747510480995648057647428143204153568980306205633402120862765346812929761660666067512453418299515657726062561967354253649275815193867839741150712520136250929179627948824165334407722188861

# 公開指数（整数）
e = 65537

# 秘密指数（整数）
d = 1034343614646284237599646361824609482047834152107898158279449245443138718062897895288863438178567148425280198575628995836327802280992055668300861475337083578550778803398293669741528809727312269620020801885844289333202314288425768908683450702297955829881416302278152076770163713656644871002203317110149191437081724897958597844779712151998506871979523566999544506266568498167960875801919694184151702663311025475170822738786513508509135537723558908769911940297345180087441288431096763060063839491651794586752234639583339513465223421550442326798358690273317043477097014030724153824763147753385435135986366247542353431541670719046193275226271355340383967935324284548493113665982989425952507995656056633593043336504985082479035349146367751319083636991965421682742756350481520402851985745351580158205279004899441213854135292106406974619006315374801770920546932579686882926698880908067451283981779716141801464381304194416337317424385

# 素因数 p（整数）
p = 2124374344742583384102849289186677156419529691466485731645388249020229497512127025039858192812237515063965697237470938901617438715431798627672494191757139381376979970040634263309024855074265522547676351413134529270456244783819810386343716108044021114187609705892256596514230887626549706729322645289624965432630947771735137009229178631845967199109474726805703824498306889710963128467470877162132251776349241339344475266237102836707291735625056297287451331147750497

# 素因数 q（整数）
q = 1908236190028151769321542974869322185980685508363384276350041399971300835419970586867284058000132242825293139743289696482667333192737875520534983382324181679849188286922016343769312844576225895750607899552135524325058037105444483657660181622916841236395730992635962118893040652555385936457401724280842197780932876525531174681532809509346356370258969001517415619907293815205321413546483275079068237635432519652160376723202943080116727669898649162867031294564389213

# CRTパラメータの計算
dmp1 = d % (p - 1)
dmq1 = d % (q - 1)
iqmp = pow(q, -1, p)

# RSA秘密鍵オブジェクトの作成（cryptographyを使用）
from cryptography.hazmat.primitives.asymmetric import rsa

private_numbers = rsa.RSAPrivateNumbers(
    p=p,
    q=q,
    d=d,
    dmp1=dmp1,
    dmq1=dmq1,
    iqmp=iqmp,
    public_numbers=rsa.RSAPublicNumbers(
        e=e,
        n=n
    )
)

private_key = private_numbers.private_key()

# ParamikoのRSAKeyオブジェクトを作成
paramiko_private_key = paramiko.RSAKey(key=private_key)

# 秘密鍵をOpenSSH形式で保存
paramiko_private_key.write_private_key_file("my_openssh_private_key", password=None)

print("OpenSSH形式の秘密鍵ファイル 'my_openssh_private_key' が作成されました。")

こうして作成された 秘密鍵ファイルmy_openssh_private_keyは、ファイルの中身としては元の秘密鍵ファイル id_public_rsaと完全に同じではないのですが、同じように秘密鍵として利用することが出来ます。もちろん、id_sample_rsa.pubで公開鍵認証されたサーバーにSSHログインすることも可能です。

最後に

今回の記事では、RSA暗号について、Pythonでその中身を調べてみました。Pythonは大きな数を扱うのが簡単であり、また、ライブラリも充実しているので、今回の調査で非常に助かりました。

RSA暗号は素数の性質を利用した暗号ですが、セキュリティを担保するためにはそのビット数を大きくしていかなくてはなりません。暗号化である以上、ビット数を上げる必要があるのは避けては通れないのですが、近年では、より効率的な暗号を行う方式として、楕円関数を利用したECC暗号も用いられるようになっています。機会があれば、このECC暗号についても調べてみたいと思います。