RSAパスワード体制

公開鍵アルゴリズムの基本数論知識
公開鍵暗号学では大部分が数論の成果を引用しているので,RSA暗号体制を紹介する前に,使用するいくつかの数論の知識点を詳しく紹介する必要がある.
ユークリッドアルゴリズム
ユークリッドアルゴリズムは主に最大公約数問題を解決し、2つの正の整数r 0とr 1のgcd表現を記す.
gcd(r0,r1)
公開鍵システムでは、セキュリティが大きな整数に依存する因数分解は通常不可能である.従って、gcd、すなわちユークリッドアルゴリズムは、単純な観察に基づいて、より効率的なアルゴリズムを用いて計算されることが多い.
gcd(r0,r1)=gcd(r0−r1,r1)
ここで、仮定
r 0>r 1であり、両者とも正の整数であり、理解に難くない.
gcd(r0−r1,r1)=gcd(g⋅(x−y),g⋅y)=g
明らかに、満足さえすれば
(r 0−mr 1)>0であれば、以下を得ることができる.
gcd(r0,r1)=gcd(r0−r1,r1)=gcd(r0−2r1,r1)=⋯=gcd(r0−mr1,r1)
mが最大値を選択した場合、このアルゴリズムは次のように表すことができます.
gcd(r0,r1)=gcd(r0 mod r1,r1)
最終的なgcdは元の問題のgcdであることが証明されています.すなわち、
gcd(r0,r1)=⋯=gcd(ri,0)=ri
拡張ユークリッドアルゴリズム
拡張ユークリッドアルゴリズムは、モジュール逆要素を計算するために使用することができ、理解に難くないが、上述したユークリッドアルゴリズムは、反復相互減算をポーリングして最終的に結果を得ることであり、言い換えれば、このような反復相互減算を元の2つのパラメータのs倍とt倍の加算と見なすことができる.
gcd(r0,r1)=s⋅r0+t⋅r1
この式は通常、失番図方程式とも呼ばれる.
拡張ユークリッドアルゴリズム(EEA):
入力:正の整数r 0およびr 1、r 0>r 1出力:gcd(r 0,r 1)、およびgcd(r 0,r 1)=s

initialize:
    s[0] = 1
    t[0] = 0
    s[1] = 0
    t[1] = 1
    i = 1
algorithm:
    do
        i = i + 1
        r[i] = r[i - 2] mod r[i - 1]
        q[i - 1] = (r[i - 2] - r[i]) / r[i - 1]
        s[i] = s[i - 2] - q[i - 1] * s[i - 1]
        t[i] = t[i - 2] - q[i - 1] * t[i - 1]
    while r[i] != 0
    return:
        gcd(r[0], r[1] = r[i - 1]
        s = s[i - 1]
        t = t[i - 1]

オーラ関数
ループZm=0,1,⋯,m−1において,この集合において,mと相互素の数がどれだけあるかに興味のある問題がある.オラ関数を定義して計算することができます.
Zm内のmとの相互素の整数個数は、Φ(m)
数値が非常に大きい場合,集合内の要素を最初から最後まで一度処理し,各gcdの計算が非常に遅く,対応するEuler関数の解く価値も非常に困難であるが,mの因数分解が既知である場合,より簡単な計算方法が存在する.
mが式によって分解できる数の連乗を仮定する.
m=pe11⋅pe22⋅⋯⋅penn
ここで、
piは異なる素数を表し、
eiは正の整数を表す.
Φ(m)=∏i=1n(peii−pei−1i)
強調しなければならないのは、この方法でオーラ関数を迅速に計算するには、mの因数分解を知る必要があります.この特徴は、RSA公開鍵スキームの核心でもあります.
フェルマの小さい定理とオラの関数
フェルマの小さな定理は以下のように記述される:aが整数であり、pが素数であると仮定すると、
ap≡a (mod p)ap−1≡1 (mod p)
この定理は暗号学において非常に有用であり,その1つの応用は有限ドメイン内のある要素の逆要素を計算することである.なぜなら
a⋅ap−2≡1 (mod p) .ただし、pが素数の場合にのみ、この反転方法が成立することに注意してください.
フェルマの小さな定理のモジュール数を任意の整数モジュールに広げ、すなわち素数のモジュールとは限らず、オーラの定理を得ることができる.
aとmが整数であり、gcd(a,m)=1であるとすると、
aΦ(m)≡1 (mod m)
この定理はモードmに適用され,整数リングにも適用される.
Zm内のすべての整数.
RSA暗号体系
この暗号体系は現在最も広く使用されている非対称暗号方式であり、実際には*データの小さな断片の暗号化、特に鍵伝送*デジタル署名、例えばインターネット上のデジタル証明書によく用いられる.
ここで注意しなければならないのは、RSA暗号化は対称パスワードに取って代わるためではなく、非常に遅いためである.RSAを利用することは、通常、対称暗号システム内の鍵を安全に交換するために使用される.したがって、RSAは通常、対称パスワードとともに使用されます.
RSA暗号化と復号化
RSAの暗号化と復号化はいずれも整数リングZm内で行われ,モード計算が核心的役割を果たしている.公開鍵による暗号化および鍵による復号化の方法は、以下のように表すことができる.
暗号化
与えられた公開鍵(n,e)=kpubおよび明文xの場合、暗号化関数は以下のようになる.
y=ekpub(x)≡xe mod n
ここで、
x,y∈Zn
復号化
秘密鍵d=kprおよび秘密文yが与えられると、復号関数は以下のようになる.
x=dkpr(y)=yd mod n
ここで、
x,y∈Zn
RSAパスワード体制の要件

攻撃者は公開鍵を得ることができるので、与えられた公開鍵値eおよびnについて、秘密鍵dが計算上不可能である必要があると判断する.

xは、モードnのサイズに一意に依存するだけであるため、1回のRSA暗号化のビット数はlを超えてはならず、lはnのビット長を指す.

xe mod nとyd mod nの計算は比較的簡単であるべきである(長整数を迅速に計算する指数法)

所与のnは、多くの鍵/公開鍵ペアに対応すべきであり、そうでなければ、暴力攻撃

を防ぐことはできない.
RSAキー生成

大きな素数pとq

を2つ選択

n=p

計算Φ(n)=(p−1)(q−1)

次の条件を満たす公開指数を選択し、e∈{1,2,⋯,Φ(n)−1}
gcd(e,Φ(n))=1

は、以下の条件を満たす秘密鍵dを計算する
d⋅e≡1 mod Φ(n)