  |
はてなキーワード: 準同型写像とは
RSA暗号は、代数的構造、特に合同算術および整数環における準同型写像を用いた公開鍵暗号である。
RSAの安全性は、環の自己同型写像の一方向性と、有限生成群の元の分解が困難であることに基づいている。
この暗号方式は整数環 Z/NZ（N = p・q）上の準同型写像の一方向性を活用する。
まず、RSAにおける鍵生成は、代数的に以下のように構築される：
互いに素な大きな素数 p および q を選び、合成数 N = p・q を作成する。
これにより、商環 Z/NZ が定義される。ここで、N はRSAにおける「モジュラス」として機能する。
この商環は、全体として単位的な環であり、RSA暗号の計算基盤となる。
オイラーのトーシェント関数 φ(N) を次のように計算する：
φ(N) = (p - 1)(q - 1)
これは環 Z/NZ の単数群 (Z/NZ)* の位数を表し、RSAの準同型構造における指数の計算に用いられる。
単数群 (Z/NZ)* は、φ(N) を位数とする巡回群であり、一般に生成元 g ∈ (Z/NZ)* を持つ。
RSAでは、この群の生成元から得られる公開指数 e は、φ(N) と互いに素な整数として選ばれる。公開指数 e はRSAの「公開鍵指数」となる。
e・d ≡ 1 (mod φ(N))
これは、e に対する逆元 d の存在を保証し、秘密指数として機能する。ここで d はユークリッド互除法により効率的に求められる。
以上により、公開鍵 (N, e) と秘密鍵 (N, d) が生成される。これらの鍵は、合同算術と商環上の準同型写像によって定義される。
RSA暗号は、モジュラー演算によるべき乗写像を使用した暗号化および復号過程である。この操作は、(Z/NZ)* 上の自己同型写像に基づいている。
任意のメッセージ M ∈ Z/NZ に対し、公開鍵 (N, e) を用いて次の準同型写像を作用させる：
C = σ(M) = M^e (mod N)
ここで σ: M → M^e は (Z/NZ)* の自己同型写像として作用し、得られた C は暗号文となる。
この写像はモジュラ指数写像として同型写像であるが、一方向的であるため暗号化に適している。
暗号文 C を受け取った受信者は、秘密指数 d を用いて復号を行う。具体的には次のように計算する：
M = C^d (mod N) = (M^e)^d (mod N) = M^(e・d) (mod N)
ここで e・d ≡ 1 (mod φ(N)) であるため、e・d = kφ(N) + 1（整数 k）と表すことができ、したがって
M^(e・d) = M^(kφ(N) + 1) = (M^(φ(N)))^k・M ≡ 1^k・M ≡ M (mod N)
により、元のメッセージ M を復元することができる。ここでオイラーの定理に基づき、(M^(φ(N))) ≡ 1 (mod N) が成り立つため、この復号化が成立する。
RSA暗号は、Z/NZ の構成において N = p・q の因数分解が困難であることを仮定する。
合成数 N の素因数分解問題は、現在の計算アルゴリズムにおいて指数時間に近い計算量が必要であり、代数的には解読が非常に難しい問題であるとされる。
RSA暗号における暗号化は群の自己同型写像によって構成されるが、逆写像を求めることは一般に困難である。
これはRSAの一方向性を保証し、現実的に解読不可能な構造を形成している。
RSA暗号の解読は逆写像としてのべき乗の逆操作を計算することに相当し、これを効率的に解決する手段が存在しないことが安全性の根拠となる。
RSA暗号の構造は合同算術に基づく準同型性を有し、M → M^e (mod N) というモジュラ指数写像によりメッセージ空間上の一対一対応を実現する。
この準同型性により計算効率が保証されつつも一方向性を持ち、安全な暗号化が可能である。
以上より、RSA暗号は合同算術、準同型写像、群の生成元と逆元の難解さに基づく暗号であり計算量理論と抽象代数からその安全性が保証されている。
RSA暗号の解読可能性は準同型写像の逆像を効率的に求める方法が存在しないことに基づいており数学的にはこの逆像問題の困難性がRSA安全性を支えているといえる。
