7. Public Key Cryptography - RSA
before get in...
🌻 Symmetric Cryptography <-> Asymmetric Cryptography
receiverとsenderは同じ鍵 を持っています.セキュリティチャネルを使用して公開鍵 を交換する.の不安全なチャネルでcipertext(C) を交換する.用語整理 C : ciphertext M : palintext K : key の欠点 
人が多ければ多いほど、1:1の公開鍵管理が困難になる
送信者は公開鍵を持ち,受信者は秘密鍵を持つ.
public key 暗号化または署名検証のための だれでも知っている
private key 復号化または署名(=create)のための 受信者のみが知っている の利点 
鍵管理が容易 デジタル署名は で使用可能である.
プロパティ アルゴリズムと暗号化鍵(公開鍵)しか知らないと、秘密鍵(=計算上不可能なto find) を見つけるのは難しい.とは逆に、両方のキーが知っていれば、en/復号 を容易に行うことができる.
利用 encrypt & decrypt digital signature 鍵交換(メッセージではなく鍵交換) 🌻 Security of Public key algorithm
特長 キースペースは十分に大きくなければなりません 512bits, 1024bits... 非常に大きな数値を計算する必要がある->対称鍵スキームと比較してslow 既知のhard問題に依存する
known hard problem : "trapdoor function" 中に入るときは好きなようにしますが、外に出るとき(ex)食虫植物ではありません) 
例 prime factorization に大きな数のp,qが2つある場合、pq=zは計算しやすいが、zからpとqを逆抽出するのは難しい、 . EX) RSA, Paillier, etc.. discrete logarithm problem に2つの整数gとxがある場合、a=GXmodPa=G^XmodPa=GXmodPは計算しやすいが、xが与えられたタイミングではgとaを逆方向に計算するのは難しい、 . Diffie-Hellman, Digital Signature, Elliptic Curve, ElGamal, etc.. Other Naccache-Stern(Knapsack), Algebraic Erase(Matrix Permutation), HFE (Multivariate Quadratic Equation), etc.. が広ければ広いほど安全になる 🌻 RSA
RSAの数学的背景
RSA cryptosystem
RSA digital signature
RSA cryptanalysis
Fermat's Theorem
ap−1=1(moda^{p-1}=1(modap−1=1(mod p)p)p)
where p is prime and gcd(a,p) = 1
also, ap=a(moda^p = a(modap=a(mod p)p)p) 素数テストに非常に有用である.
Euler's Theorem
aφ(n)=1(moda^{\varphi (n)}=1(modaφ(n)=1(mod n)n)n)
for any a, n where gcd(a,n)=1
φ(p)=p−1\varphi (p)=p-1φ(p)=p∮1(少数の場合)/pqpq(少数のp*q) example a = 3, n=10, φ(10)=4\varphi (10)=4φ(10)=4の場合、
34=813^4=8134=81=1 mod 10
RSAを含む多くのCyptographyアルゴリズムは、非常に大きな素数をランダムに選択することが多い.
"there are infinitely many primes"
n以下の素数はいくつありますか?
π(N)=npi(N)=nπ(N)=n素数numより小さい個数 π(N)∼NlnN\pi(N)\sim\frac{N}{lnN}π(N)∼lnNN π(N)∼∫2n1lntdt\pi(N)\sim\int^{n}_{2}{\frac{1}{ln t}dt}π(N)∼∫2nlnt1dt 2128^{128}2128以下の数字はいくつありますか?->2128∼3.4×10382^{128}\sim3.4\times 10^{38}2128∼3.4×1038 -> 3838 時間の複雑さ 無邪気にすべての場合に試行したときO(n) nにn/2より大きい素数が存在しないことが分かったとき,時間的複雑度はO(n)O(sqrt{n})O(n) であった.
与えられたpが素数であるか否かを判断する方法
ap∮1=1(moda^{p-1}=1(modap∮1=1(modp)p)が成り立つと、pは小数であり、成り立たないと小数ではなく
a pより小さいrandom numをたくさん選んで、テストしてみましょう. が正式に成立=確率素数 正式成立X=not prime
例)
n=221は少数ですか?
1a=38の場合、an–1=38220=1(mod 221)a^{n-1}=38^{220}=1(mod 221)an–1=38220=1(mod 221)
221は最初のnumかもしれません
a=26の場合、an
221は黄金期ではありません
Miller-Rabin algorithm
奇整数n>2の場合、
n−1は、n−1=2 kqn−1=2^{k}qn−1=2 kqと表すことができる.
しかし、k>0、qは奇数である.
prime numと式を加算する場合prime num test
nがprime numであるかどうかを確認するには、2つの確認が必要です. 条件1)aq=a^q=aq=1 mod n 条件2)a 2 k-1 qa^{2^{k-1}q}a 2 k-1 q=-1 mod n=n-1 mod n
(ただしqは奇数であり、k>0である.) 条件1 OOR条件2 O=可能prime 条件1 X OR条件2 X=非a prime
エクスポートプロセス
an−1=1a^{n-1}=1an−1=1 mod n
-> an−1−1=0a^{n-1}-1= 0an−1−1=0 mod n
-> a2kq−1a^{2^kq}-1a2kq−1 = 0 mod n
miller labinアルゴリズムを用いた小数チェックコード
例
input and output input : N Nは奇数複合整数、 である. Nはpqと同様に少なくとも2つの異なる主因子から構成される. output primes p and q large N is difficult! p,qが与えられると、n=pqの計算が容易になる. Nを与え、p、qを算出する N時間が簡単、 Nが大きいときは難しい
😊 generating RSA keys
public key : (n, e)
private key : (n, d) p and q are large primes! n = pq φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)φ(n)=(p−1)(q−1) 💬 1 < e < φ(n)\varphi(n)φ(n),
gcd(e,φ(n)\varphi(n)φ(n)=1の整数eは
公開鍵に使用! 💬 1 < d < φ(n)\varphi(n)φ(n),
ed=1(mod φ(n)\varphi(n)φ(n)の整数dは
秘密鍵に使用! dはmoduloφ(n)\varphi(n)φ(n)からeへの逆. 拡張Euclideanアルゴリズム、 計算可能
Encryption : c=mec=m^ec=me mod nnn
Decryption : m=cdm = c^dm=cd mod nnn
(m = plaintext, c = ciphertext)
example 
currently..
主に 1204ビット-RSA(309ビット)に使用されます. |p-q|できるだけ大きくします. n=pqは繰り返しできません. コモンモード攻撃
φ(n)\varphi(n)φ(n)とnが分かれば、攻撃者はunwon pを解読することができる. 
🌻 Implemented RSA
with a hash padding,
the receiver can detect wether the message has been modified during transmission
上の図に示すように、m(メッセージ)はnより小さいm 1、m 2、・・・、mim_1, m_2, ......, m_im1,m2,......,miに分割すると、効率の問題が発生します.
たいしょうひかく
|encryption algorithm|speed|shared secret key|
|---|---|---|
|symmetric ex)AES|FAST|YES (need sharing a secret key in advance)|
|RSA|SLOW(主にショートメッセージ暗号化に使用される速度が100～1000倍遅い)|NO(only needreceiver’s公開鍵)|
長さとAESに合わせて使いましょう!
Message senderはmessage(m)とともに署名する(σ\sigmaσ)見送れ!
receiverはこれを検証できます!の利点 reduce size:long message mの場合、hash(m)=h(m)の長さは よりずっと短い.セキュリティの向上:攻撃者の中間操作を阻止する
(m 3 m 3 m 3は偽造情報です.)
効果 privacy (confidentiality) data authentication (data intergrity) non-repudiation user authentication
🌻 Symmetric Cryptography <-> Asymmetric Cryptography
✉️ Symmetric Cryptography
✉️ Asymmetric Cryptography
送信者は公開鍵を持ち,受信者は秘密鍵を持つ.
public key
private key
利用
🌻 Security of Public key algorithm
特長
known hard problem : "trapdoor function"
🌻 RSA
INTRO
RSAの数学的背景
RSA cryptosystem
RSA digital signature
RSA cryptanalysis
🦋 RSAの数学的背景
Fermat's Theorem
ap−1=1(moda^{p-1}=1(modap−1=1(mod p)p)p)
where p is prime and gcd(a,p) = 1
also, ap=a(moda^p = a(modap=a(mod p)p)p)
Euler's Theorem
aφ(n)=1(moda^{\varphi (n)}=1(modaφ(n)=1(mod n)n)n)
for any a, n where gcd(a,n)=1
φ(p)=p−1\varphi (p)=p-1φ(p)=p∮1(少数の場合)/pqpq(少数のp*q)
34=813^4=8134=81=1 mod 10
🦋 testing for primality
RSAを含む多くのCyptographyアルゴリズムは、非常に大きな素数をランダムに選択することが多い.
"there are infinitely many primes"
n以下の素数はいくつありますか?
π(N)=npi(N)=nπ(N)=n素数numより小さい個数
与えられたpが素数であるか否かを判断する方法
ap∮1=1(moda^{p-1}=1(modap∮1=1(modp)p)が成り立つと、pは小数であり、成り立たないと小数ではなく
a pより小さいrandom numをたくさん選んで、テストしてみましょう.
例)
n=221は少数ですか?
1
221は最初のnumかもしれません
a=26の場合、an
221は黄金期ではありません
Miller-Rabin algorithm
奇整数n>2の場合、
n−1は、n−1=2 kqn−1=2^{k}qn−1=2 kqと表すことができる.
しかし、k>0、qは奇数である.
prime numと式を加算する場合prime num test
nがprime numであるかどうかを確認するには、2つの確認が必要です.
(ただしqは奇数であり、k>0である.)
エクスポートプロセス
an−1=1a^{n-1}=1an−1=1 mod n
-> an−1−1=0a^{n-1}-1= 0an−1−1=0 mod n
-> a2kq−1a^{2^kq}-1a2kq−1 = 0 mod n
miller labinアルゴリズムを用いた小数チェックコード
# repeat for primality testing!
MILLER-RABIN(n):
1. Find integers k>0, q odd, so that n-1 = (2^k)q
2. Select a random integer a, 1 < a < n-1
3. if a^q mod n = 1, then return 'probably prime'
4. for j = 0 to k-1 do
if a^{{2^j}q}mod n = n-1, then return 'probabily prime
5. return 'composite' // not prime例
Integer Fctorization Problem
🦋 RSA操作手順
😊 generating RSA keys
public key : (n, e)
private key : (n, d)
gcd(e,φ(n)\varphi(n)φ(n)=1の整数eは
公開鍵に使用!
ed=1(mod φ(n)\varphi(n)φ(n)の整数dは
秘密鍵に使用!
Encryption : c=mec=m^ec=me mod nnn
Decryption : m=cdm = c^dm=cd mod nnn
(m = plaintext, c = ciphertext)
example
🦋 RSA注意事項
主に
🌻 Implemented RSA
✉️ hasing is required in RSA!
the receiver can detect wether the message has been modified during transmission
✉️ How to encrypt a long message! -> AESと混ぜて使いましょう!
上の図に示すように、m(メッセージ)はnより小さいm 1、m 2、・・・、mim_1, m_2, ......, m_im1,m2,......,miに分割すると、効率の問題が発生します.
たいしょうひかく
|encryption algorithm|speed|shared secret key|
|---|---|---|
|symmetric ex)AES|FAST|YES (need sharing a secret key in advance)|
|RSA|SLOW(主にショートメッセージ暗号化に使用される速度が100～1000倍遅い)|NO(only needreceiver’s公開鍵)|
長さとAESに合わせて使いましょう!
🦋 digital signature
Message senderはmessage(m)とともに署名する(σ\sigmaσ)見送れ!
receiverはこれを検証できます!
(m 3 m 3 m 3は偽造情報です.)
安全な+長いメッセージを送信
Reference
この問題について(7. Public Key Cryptography - RSA), 我々は、より多くの情報をここで見つけました https://velog.io/@yesterdaykite/7.-Public-Key-Cryptography-RSA-1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol