Microsoft Word - エクセルによる解読の演習.doc

Size: px

Start display at page:

Download "Microsoft Word - エクセルによる解読の演習.doc"

さみおまた
5 years ago
Views:

1 エクセルによるによる暗号解読暗号解読の演習問題 1 次のシーザーシーザー暗号暗号を解読解読せよせよ DOHA H ILHBAPMBS MSVDLY PA PZ! ( 解答 ) d f g h i m n o p q r s w x 問題 2 次のシーザーシーザー暗号暗号を解読解読せよせよ ZNK KTKSE CGY YAVKXOUX OT TASHKX ( 解答 ) d f g h i m n o p q r s w x 1

2 演習 1 次の単アルファベットアルファベット式暗号文式暗号文を解け LBO ZOKL QXU LC ROXJP SXLBOSXLYAK YK LC VC SXLBOSXLYAK UCM SMKL XAHMYJO LBO BXZYL CI JOXVYPD QYLB FXFOJ XPV FOPAYR YP BXPV この暗号文の頻度分析は次のようになるこれをヒントに解読してください標準頻度分布 o i n s h r d mw f g p x q 演習 1 の頻度分析 x o p s f m q r d h i g n w 2

3 演習 2 次のシーザーシーザー暗号暗号を解読解読せよせよ L Z W J W S J W K W N W J S D L Q H W K G X H W G H D W O Z G V G F L W S L E W S LK G E W U G F K A V W J L Z W S E G M F L G X H JG L W A F L Z W QL S C W K G E W U GF K A V W J L Z W T S D S F U W S U A V S F V S D C S D A A F X G G V K G E W K A E H D Q V G F L D A C W L S K L W G X E W S L S F V G L Z W J K L Z A F C C A D D AF Y S F A E S D K X G J X G G V A K U J M W D まず暗号文の頻度分析を行うと次のようになる演習 2 の頻度分布 d f g h i m n o p q r s w x 暗号文と同じ字数 (189 字 ) の標準頻度分布を調べると次のようになる 3 2 標準頻度分布 2 d f g h i m n o p q r s w x d f g h i m n o p q r s w x 3

4 ヴィジュネル方陣平文 d f g h i m n o p q r s w x w 1 B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 2 C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 3 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 4 E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 6 G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 7 H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 8 I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 9 J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 11 L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 12 M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 13 N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 14 O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 16 Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 17 R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 18 S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 19 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 2 U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 21 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 22 W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 23 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 24 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 2 Z A B C D E F G H I J K L M N O P Q R S T U V W X Y 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 4

5 演習 3 次のヴィジュネルヴィジュネル暗号暗号を解読解読せよせよ A L N K Y M X R I L V S A J S L G N D C A S W F F U W L J Z L H J Y C Y I F Y C D E F B L P X G Z L N E O C S L A B F J L R F N C H X R I Q O I C L R V R R R P T E E F S U H U V P Z S S K J F E A U Q H M Q Z T L W B D C A M A X R V X R C J F S H A M O R F P Q H H G F Q H C Z I Z L L E D Y U H V V B V J C E C B Q B B E G H M A K F L L B J N P X N C F L J R C J P P Y F L S C G N M K E L J Y N S J Y C U W B D C V R R W M B R Q Y G T M A Y G Z V B F K V R G Y C T S E E G U K B W R O I S Z P Z X Q R W O I J R Q H P E V Y K C U V J W P R J Q D M G Y N H M A Y Y G Z W U F C Z E A U A S S G Y C Z A R I C X Y V K C D I G R L K E F T M S H N J G J I N C J A L R G C V T Y V R O E G X Y A L R I C K X U V P L A B E B L V R U U O I E V F L L N U Z L I A F L A L N K U P P Q E G N L G K F L R G Y C F J B L L K W B D C A L V E E Z P L Z L N M A K F L V B F K A L R C Y U X R I L D L V T F O I U R B A E X V L V Y G J G K I J R Q Z X V C J S M T Y R L H G Y C Y I J R Q H P F F Y S E Q U C Y L R Y Y K H E R E N I Q W P V Q G Y C I E E E Y U H G Y C A L V E E Z J B I N H M A K G U K J V P L S A K F L J Y F M Y R R R P O M F S C K P B F I V S G F D A L R N G U H B N Y A X U V H E G Z T F P R R D V R G Y C D E Y C B P M A K W V Y J F L K I E N F F M G E C C Z E D M C I Q K L Y S H X F A L R Y G N K J Z L K A N J Z S S J Z L N E U U Y Y V V E E P X F D P I I U I K H R F D Y Z W R I N P I P V F L T N Z L A I Q Z R A L R I C C V R G Y C J S Y U L P K U K U O I A K F L P N J R S I N W D L P Y 問 1 キーワードが何文字から出来ているかを検索したい暗号文において同じ文字列文字列が周期的に出現していないかを調べてキーワードが何文字かを答えよ ( ヒント CALVEEZ VRGYC ALRIC) 問 2 番号の文字列を文字列 1

6 番号の文字列を文字列 2 番号の文字列を文字列 3 番号の文字列を文字列 4 番号 2 の文字列を文字列として各文字列に頻度分析をかけたところ次のようになった < 標準頻度分布 > 2 標準頻度分布 d f g h i m n o p q r s w x を利用してキーワードを答えよ文字列 1 の頻度分布文字列 2 の頻度分布 2 2 d f g h i m n o p q r s w x d f g h i m p q n o r s x w 文字列 3 の頻度分布文字列 4 の頻度分布 2 2 g f h d i r n q m o p s w x 2 f d i g h r n m o p q s w x 文字列の頻度分布 d f g h i p q m r n s o w x 6

7 演習 4 ヘルマンの鍵配送鍵配送をしをしようよう二人がペアになってまず一方向関数 Y^x (mod p) を取り決める次に各自が個人鍵を選びそれを秘密にして一方向関数にいれて結果を伝え各自が個人鍵を用いてメッセージを計算する最後に同じ鍵が得られたかを互いに確認する RSA 暗号の作成手順作成手順を説明説明しようしよう作成手順 1 大きな素数 p q ( 桁程度 ) を選び n=pq とする 2 (p-1)(q-1) と互いに素な数 r を選ぶ 3. この n と r を公開鍵として公表する 4. 平文 X に対して X^r Y (mod n) で決まる値を暗号文暗号文とする復号化ボブの個人鍵を s をとするときボブは次のように復号するここに s は rs 1(mod (p-1)(q-1)) を満たす整数 s である Y^s(mod n) を計算すると Y^s X となって平文 X が得られるイヴは個人鍵 s を知るために rs 1(mod (p-1)(q-1)) を解かねばならないがそのためには n の素因数分解 n=pq を求めねばならないしかし p q が大きいときそれはとても莫大な時間を要するので不可能である 7

8 マーティンガードナーガードナーの問題 n= r=97 この n を p と q の積に素因数分解しメッセージを解読せよというのである賞金は百ドルこの問題が解読されたのはそれから十七年後の 1994 年 4 月であった p= q= 世界各地のスーパーコンピュータのネットワークが結ばれて解読されたわけであるがそれにしても短期間で解読されたことに驚きを覚えるかもしれないしかし選ばれた $n$ はわずかに 129 桁の数にしか過ぎなかったのである演習 RSA 暗号を作ってってそれをそれを解読解読しようしようボブがアリスにウラン (U という文字 ) を送りたいとする ASCII では U は 1 で表されこれは十進法では 8 に等しい公開鍵 n=899 r=13 としてこの平文の暗号文を作りまたそれを復号せよ以上で演習を終える以下のページでは解答例を記す 8

9 エクセルによるによる暗号解読暗号解読の演習演習の解答例問題 1 Wh if fowr i is 問題 2 Th nm ws sprior in nmr 演習 1 単アルファベットアルファベット式暗号文式暗号文の攻略法再掲 1 頻度分析からまずを推測するこのとき母音のはほとんどすべての文字の前後に現れるが子音のはそうでないことに留意する 2 という組み合わせはよりずっと出現頻度が高い 3 一文字単語は二つしかないそれはと I である 4 が分かった段階で h も分かる h はの前にしばしば現れるがの後にはめったに来ない ( h h hn など ) よく現れる二文字単語は of o in i is s so w h or on do if m m p n go no s m である 6 よく現れる三文字単語に h nd がある 7 どの単語も母音を含むことから残りの母音 o の見当をつける 8 2つ続けて同じ文字が現れる場合 ss ff mm oo のうちのどれかを表すと考えてよい 9 出現頻度が1% 以下になる文字がつほどあるそれは q x を表す熟達によって単語あわよくばまるまる 1 つのフレーズを突き止める問題の暗号文暗号文の解読例エクセルのワークシートなどを使って暗号文の頻度分析をすると次のようになる標準頻度分布演習 1 の頻度分析 x o o 8 i n s h r d mw f g p x q p s f m q r dh i gn w 9

10 L X O は何かな? h ZK QU C RJP ShSYAK ShSYAK UCM SMK AHMYJ JVYPD QYh FFJ PV FPAYR YP h YK C hpv hzy VC CI 二文字単語 C YK VC CI YP は何かな? 三文字単語 QU UCM PV は何かな? h Zs QU o RJn UoM SMs AHMiJ nd FnAiR in hnd ShSiAs is o do ShSiAs h hzi of JdinD Qih FFJ ここまで来れば ShSiAs = は思いつきたい h Zs wu o RJn mhmis is o do mhmis UoM mms HMiJ h hzi of JdinD wih FFJ nd FniR in hnd UoM は何かな? 出現頻度が高いはずのと r がまだ決まっていないそれは何かな? h Zs w o rn mhmis is o do mhmis o ms Hir h hzi of rding wih FFr nd Fni in hnd よって暗号は次のように解読される h s w o rn mhmis is o do mhmis o ms qir h hi of rding wih ppr nd pni in hnd

11 演習 2の解答例まず暗号文の頻度分析を行うと次のようになる演習 2 の頻度分布 d f g h i m n o p q r s w x 暗号文と同じ字数 (189 字 ) の標準頻度分布を調べると次のようになる 3 2 標準頻度分布 2 d f g h i m n o p q r s w x 上の2 表を見比べよう上の表は標準分布をシフトしたものであるはずである上の表の m n o p q の落ち込み部分は標準分布の w x の落ち込みにあたり上の表の s w の山谷山の部分は標準分布の d の部分にあたるであろうそこで s から始まるカエサルシフト 18 と推察して演習 2の分布を18 文字シフトさせてその分布を並べ直すと次のようになる演習 2 のカエサルシフト 18 の頻度分析 s w x d f g h i m n o p q r このグラフグラフの山と谷はほとんどほとんど標準分布標準分布のそれとのそれと一致一致している! ゆえに与えられた暗号文はカエサルシフト 18 の暗号文であるよって次の暗号アルファベットと平文アルファベットの対応表により暗号が解読される 11

12 暗号文 d f g h i 平文 i m n o p q r s m n o p q r s w x w x d f g h 与えられた暗号文は次のように解読される Thr r sr ps of pop who don m Som onsidr h mon of proin h som onsidr h n id nd i in food som simp don i s of m nd ohrs hin iing nims for food is r 演習 3の解答例キーワードは HENRY キーワードが分かったので暗号文を平文に書き直すと次のようになるこれはオーヘンリーの短編最後の一葉の一節であった Th frnoon S m o Johns s s d whr sh ws niing woon swr. Sh p on rm rond hr sof nd sid, I somhing o o, Johns. Sd o s, Mr.Bhrmn did of pnmoni in h hospi. H f i on o wo ds go. Whn somon fond him in his room on h morning of h firs d, h ws rd hpss wih pin. His shos nd ohs wr qi w nd s od s i. A h pop h ghrd hr wondrd whr h hd n on h wid nigh h. Thn h fond som hings ing in h room.th nrn whih h hd n osid ws si ighd. Thr ws so ddr h hd drggd from h rn. And h hings for pining wr on h foor nr his d. Loo o of h window h s i f on h w. Didn o wondr wh i nr mod hrogh h high wind ws owing? Ah, dring, i s Mr.Bhrmn Bhrmn s msrpi h pind i hr on h od nigh whn h s f f. 12

13 演習 4 の解答例 < 第一段階 > 一方向関数を 8^x (mod 49) とし, あきら君の個人鍵は, 6 かおるさんの個人鍵は, であるとする. < 第二段階 > あきら君の計算 8^6 (mod 49)=43 かおるさんの計算 8^{}(mod 49)=22 そして, 鍵の交換をする. < 第三段階 > あきら君の計算 22^6 (mod 49)=29 かおるさんの計算 43^{} (mod 49)=29 かくして, 二人は同じ数 29 を得る. 演習の解答例この暗号化を Y とすると, 8^{13} mod(899) と計算されるので Y= よって, 暗号文はである.\\ これの復号は次のようになる. n の素因数分解 n=29 31 を見出し, 個人鍵を割り出す. 13s 1 (mod 28 3 なる s を見つけると, 答えは,s=17 となる. すなわち, 個人鍵は,s=17 したがって, あとは, 13

14 ^{17} (mod 899) を計算するだけである. 実際, ^{17} 8 (mod 899) となり,X=8 を得る. 以上で, 演習を終る. 14

チェビシェフ多項式の2変数への拡張と公開鍵暗号（ElGamal暗号）への応用

チェビシェフ多項式の2変数への拡張と公開鍵暗号（ElGamal暗号）への応用チェビシェフ多項式の変数への拡張と公開鍵暗号 Ell 暗号への応用 Ⅰ. チェビシェフ Chbhv Chbhv の多項式よりであるからよってここでとおくと coθ iθ coθ iθ iθ coθcoθ 4 4 iθ iθ iθ iθ iθ i θ i θ i θ i θ co θ co θ} co θ coθcoθ co θ coθ coθ したがってが成り立つこの漸化式とであることより