![[PukiWiki]](new.png "[PukiWiki]")
#author("2021-11-02T13:24:31+00:00","","") *[[Problem 182:http://projecteuler.net/problem=182]] 「RSA暗号」 [#f0e8588d] RSA暗号は以下のアルゴリズムに基づいている: RSA 暗号は以下のアルゴリズムに基づいている: -鍵生成 ++二つの異なる素数pとqを生成する. ++n=pqとし, φ=(p-1)(q-1) (=φ(n))とする. ++1<e<φの範囲でgcd(e,φ)=1となる整数eを決定する. ++二つの異なる素数 &tex{p}; と &tex{q}; を生成する. ++&tex{n=pq}; とし, φ=&tex{(p-1)(q-1)}; (=φ(&tex{n};))とする. ++1<&tex{e};<φ の範囲で gcd(&tex{e};,φ)=1 となる整数 &tex{e}; を決定する. -暗号化 ++平文を[0,n-1]中の整数mとする. 平文は以下の方法で[0,n-1]中の整数に暗号化される. ++c=m&sup{e}; mod nとし, cを暗号文とする. ++平文を [0,&tex{n};-1] 中の整数 &tex{m}; とする. 平文は以下の方法で [0,&tex{n};-1] 中の整数に暗号化される. ++&tex{c=m^{e}}; mod &tex{n}; とし, &tex{c}; を暗号文とする. -復号 ++暗号文をcとし以下の操作を行う. ++ed=1 mod φとなるdを計算する. m=c&sup{d}; mod nが元の平文となる. ++暗号文を &tex{c}; とし以下の操作を行う. ++&tex{ed};=1 mod φとなる &tex{d}; を計算する. &tex{m=c^{d}}; mod &tex{n}; が元の平文となる. さてあるeとmについてm&sup{e}; mod n=mとなることがある. 以下, m&sup{e}; mod n=mとなるmを''公然の平文''と呼ぶことにする. さてある &tex{e}; と &tex{m}; について &tex{m^{e}}; mod &tex{n}; = &tex{m}; となることがある. 以下,&tex{ m^{e}}; mod &tex{n=m}; となる &tex{m}; を''公然の平文''と呼ぶことにする. 公開鍵の一部 e を選ぶときには, 公然の平文が多くならないという点が重要である. 例えば, p = 19, q = 37 とする. このとき, n = 19 * 37 = 703でありφ = 18 * 36 = 648 である. もし e = 181 とすると, gcd(181, 648) = 1 であるが, 全ての平文m (0≤m≤n-1)が公然の平文となってしまう. eについてどのような選び方をしても, 必ずいくつかは公然の平文が存在する. 従って, 公然の平文の数を最小化するようにeを選ぶのは重要である. 公開鍵の一部 &tex{e}; を選ぶときには, 公然の平文が多くならないという点が重要である. 例えば, &tex{p}; = 19, &tex{q}; = 37 とする. このとき, &tex{n}; = 19 * 37 = 703 でありφ = 18 * 36 = 648 である. もし &tex{e}; = 181 とすると, gcd(181, 648) = 1 であるが, 全ての平文 &tex{m}; (0≤&tex{m};≤&tex{n};-1) が公然の平文となってしまう. &tex{e}; についてどのような選び方をしても, 必ずいくつかは公然の平文が存在する. 従って, 公然の平文の数を最小化するように &tex{e}; を選ぶのは重要である. さて, p = 1009, q = 3643とする. このとき, 公然の平文の個数が最小となる全てのeの総和を求めよ (ただし1<e<φ(1009,3643)かつgcd(e,φ)=1). さて, &tex{p}; = 1009, &tex{q}; = 3643 とする. このとき, 公然の平文の個数が最小となる全ての &tex{e}; の総和を求めよ (ただし 1<&tex{e};<φ(1009,3643) かつ gcd(&tex{e};,φ)=1). IP:219.106.167.72 TIME:"2021-11-02 (火) 22:24:31" REFERER:"http://odz.sakura.ne.jp/projecteuler/index.php" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:93.0) Gecko/20100101 Firefox/93.0"
