暗号の理論

(1)

暗号の理論

教科領域教育専攻自然系コース(数学) 近回大輔

1 はじめに

暗号には、様々な方式が存在し、今現在も多くの通信システムなどに利用されている。そして、暗号システムには、様々な数学的要素が利用されている。本論文では、その中でも公開鍵暗号系の方式である RSA暗号と楕円曲線暗号につして取り上げ、数勃句要素キ暗号システムの中身を紹介する。

2 研究の目的

まず、RSA暗号キ楕円曲線暗号における数学的な要素を研究することで、これらの暗号系に必要な数学的な要素を理解する。次に、本鱒句な部分を研究することで、これらの暗号系に対する理解を深める。

3 研究の内容 (1) 数論

1.楕円曲線 (楕円曲線)

Kを標数*2，3の体として、x3+ax+b

丸

b EK)を蚤援を持たない 3次の多項式とする。

ここでK上の楕円曲線とは、鮮民童点と呼ばれるOと書かれる1つの要素を含む方程式

予弓 3

均 x+bを満たすx，yEKである点，(x，y) の集合を表す二

(楕円曲線

t

での性質)

楕円曲線をEとし、P，

Q

をE上の点とする。

① Pが無関室点Oであるとすると、一手=0 とし子時国Qと定義する。つまり、 Oがここで考えている点の群における加法の単

4 4

﹁DQU

指導教員平野康之

位元であるゼ、口元に相当すると考える。

② E令 1，x2}とすると、

‑p

咲‑Xl，x2}となり E上の点となる。

③ 直線PQとEのP，

Q

以外の交点をR'とする。 R'とx軸について対称な点をRとすると、

P

刊さ

= R

④手喝のとき、すなわち直線PQがEの接線となるとき、

P

^刊^さ

= P +

^手当P=

R

⑤Q= ‑P

のとき、

P

刊さ

= p + (

ー防=0

⑥ P刊住Q+P

⑦ E上の3点P，Q，Rにおいて、

( p + Q ) + R = P + (

Q+R)

。これらの性質から、単位元・逆元が存在し、

交換瀕

u

、結合槻リのそれぞれが成り立つことがわかる。この条件から、楕円曲線上の点集合はア~ノL併をなす。

(2) 暗号理論

1.公開鍵暗号系

送信者から受信者に対してメッセージ(平刃を送る際、第三者に知られることなくメ

ッセージを送る必要があるo そこで、用いられる方法として、送信者はメッセージを変換して送り、受信者がそれを逆変換して元のメッセージに戻す方法である。送信者の変換を暗号化といい、受信者の逆変換を復号化という。この暗号化・復号化を行う際には、鍵という一種のパスワードのようなものを用いて、

暗号化・復号化のパターンを広げている。昔から使われているシステムは同じ鍵て暗号

(2)

化・復号イじする方法で、この暗号系を対税鍵暗号(または秘密場暫時)という。最近の暗号システムには異なる鍵を用いる方法が多用

され、この暗号系を手除問暗号系という。

非対税者音号系の例として、受信者は2つの異なる鍵を用意する。そのうちの1つを公開し、他方を秘密にしておく。送信者は公開された方の鍵

0

音別協l)を用いて、メッセージを暗号イじする。受信者は暗号化されたメッセージを、秘密にしておいた方の鍵復号化鍵)を用いて、復号化して元のメッセージiこ戻す。このシステムを公開鱒暗号系という。

この方式の特徴は、公開鍵から復号化鍵を知ることが困難となっている。

2. RSA暗号

RSA暗号とは、世界初の公開鍵暗号系で、

大きい数の素因数分解の困難さを手法とする。

( R S A

^{暗号での鍵生成)}

自然数n，e，dを以下の条件を満たすようにとる。

(1)素数 p，q(p=T

ψ

^により ⁿ^二pqとなるn (2) (φ(n)，θ=1となるe，φ(n)=(P‑I)(q‑1) (3) ed三1(mod φ(n))となるd

D，eを公開鍵とし、 dを秘密鍵とする。

(郎A暗号での暗号化・復号イり平文xに対して、暗号化とは、

y

三 x . e

(modn)，(0壬yくがなるyを求める。

暗号文yに対して、復号化とは、

Z三yd(modn)，(O<zくがなるzを求める。

そして、X=Zとなる。

侭

SA

暗号の理論)

RSA暗号では、 n弓>qにおいて2つの素因数p，qからnを得るのは簡単であるが、 nからp，qを得るのカ》宇常に困難であるという一方向

f

生がポイントとなっている。

3.楕円曲線婿号

楕円曲締音号とは、公開鍵暗号系の方式で、

楕円曲線上の離散対数問題を利用している。

ここで、は、ElGamal暗号の類似の方法を紹介する。

(楕円曲線音号での鍵生劇

(1)有限体F_q上の楕円曲線EとE上のαを選ぶ。

(2) 乱数aを発生させ、 s=aαを計算する。

Fq，E，a，

s

を公開鍵とし、aを秘密鍵とする。

(楕円曲線暗号での暗号化・復号イり (1) 平文mをE上の点xに対応させる。

(2)乱数kを発生させる。

( 3 ) Y l = k a

，戸=x

+ks

を計算する。

(心{yl，y~ を暗号文として受信者に送る。

(5) {yl，y~を用いて、 Dk^l

∞守

^{:2-aYl を計算}

する。

(6) xをmに対応させる。

(楕円曲線暗号の理論)

楕円曲線暗号では、 s=aαにおいて、 aと αから

H

を求めるのは簡単だが、 αと

8

から aを求めるのが困難であるというところがポイントである。

楕円曲線暗号は、速度が遅かった公開鑓培号の暗号化守護号化の計算を高速化できるのではないかと期待されている。

4 おわりに

暗号システムは、現在もより厳重に、より効率的に、より速く、より簡単になるようますます発展してきている。それらのシステムの根底にあるものが数学的な要素であり、数学の発展も大きな役割を担っていると思えつれる。本研究だけに終わることなく、暗号理論における数学の理論や暗号のシステムについて、これからも研究していこうと思う。

FO

Fh υ

円δ

暗 号 の 理 論