Introduction to Information and Communication Technology

Introduction to Information
and Communication
Technology (a)
11th week: 2.6 Security technology
Kazumasa Yamamoto
Dept. Computer Science & Engineering
Introduction to ICT(a) 11th week
1
Notice
 This lecture is one of the experimental “bilingual”
lectures on the “Super Global University” program.
 This lecture is given in JAPANESE using English slides.
Introduction to ICT(a) 11th week
2
Main points of this week
• Security
• Cipher algorithm
• encryption
• decryption (deciphering)
• key
• Common key (Secret key) cryptosystem
• Public key cryptosystem
• Caesar cipher
• RSA cipher
Introduction to ICT(a) 11th week
3
今回のポイント
 セキュリティ
 暗号化アルゴリズム
 暗号化
 復号（復号化）
鍵
 共通鍵（秘密鍵）暗号
 公開鍵暗号
 シーザー暗号
 RSA暗号
Introduction to ICT(a) 11th week
4
Caesar cipher
 One of common key cryptosystems
 One of “substitution ciphers”
 http://www.xarg.org/tools/caesar-cipher/
 When encrypting, each letter in the plaintext is
replaced by a letter some fixed number of positions
down the alphabet.
 “some fixed number” = key
 Deciphering is done in reverse.
Introduction to ICT(a) 11th week
5
シーザー暗号
 共通鍵暗号のひとつ
 「換字式暗号」のひとつ
 http://www.xarg.org/tools/caesar-cipher/
 平文の各文字が、ある固定された数だけずらした
アルファベットで置き換えられる。
 「ある固定された数」＝鍵
 ずらした分だけ戻せば復号できる。
Introduction to ICT(a) 11th week
6
Substitution cipher
 A method of encoding by which units of plaintext are replaced with
ciphertext, according to a fixed system; the "units" may be single
letters (the most common), pairs of letters, triplets of letters,
mixtures of the above, and so forth.
 The receiver deciphers the text by performing the inverse
substitution.
From “The Adventure of the Dancing Men”,
one of the Sherlock Holmes short stories
written by Sir Arthur Conan Doyle.
Introduction to ICT(a) 11th week
7
換字式暗号
 平文の文字を何らかの方式に従って「単位」に置き
換えることで暗号化する方式。「単位」は文字であ
る必要はない。
 復号化時は、逆の手順を行う。
コナン・ドイル「シャーロック・ホームズの
冒険」の『踊る人形』に出てくる暗号。
Introduction to ICT(a) 11th week
8
Cracking “The Dancing Men”
 How did Sherlock crack the code?
 He used “letter frequency”
to estimate the letters.
Sorting
Introduction to ICT(a) 11th week
9
「踊る人形」の暗号を破る
 シャーロックはどうやって
暗号を破ったのか？
 文字の出現頻度を使って推測した。
ソート
Introduction to ICT(a) 11th week
10
Off the subject
 Hangman (Game)
 A game of guessing a word or phrase one letter at a time
 You maybe should start with “e” because of the letter frequency.
 http://www.playhangman.com/
 Enigma
 Cipher machine used by Nazi Germany
before and during World War II
(polyalphabetic substitution cipher).
 Alan Turing was the central force in
continuing to break the Enigma in the
United Kingdom during World War II.
 “The Imitation Game” (movie)
Introduction to ICT(a) 11th week
11
余談
 Hangman（ゲーム）
 1文字ずつ答えて単語やフレーズを当てるゲーム
 文字の出現頻度から考えて、最初は “e” から始めるのが無難。
 http://www.playhangman.com/
 エニグマ（Enigma）
 第二次世界大戦頃にナチスドイツが使
用した暗号機（順変多表換字式）。
 第二次大戦中、アラン・チューリングが
エニグマの暗号を破る仕事に従事して
いる。
 “The Imitation Game” (映画)
Introduction to ICT(a) 11th week
12
RSA cipher
 Public key cryptosystem
 The key for encryption differs from the key for
deciphering.
 The key for encryption cannot be used for deciphering.
E
 Encryption： ciphertext = plaintext mod N
D
 Decryption： plaintext = ciphertext mod N
 Public key： the pair of (E, N )
 Secret key： the pair of (D, N )
Introduction to ICT(a) 11th week
13
RSA暗号
 公開鍵暗号
 暗号化の鍵と復号化の鍵が異なる
 暗号化の鍵では復号できない
E
 暗号化：暗号文＝平文 mod N
D
 復号：
平文＝暗号文 mod N
 公開鍵： (E, N ) の対
 秘密鍵： (D, N ) の対
Introduction to ICT(a) 11th week
14
Modulo operation
 Finding the remainder after division
 27 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
 For addition
 (7+6) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 13 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 1
 For multiplication
 (15×3) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 45 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 9
 (15×3) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = ((15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(3 𝑚𝑚𝑜𝑜𝑑𝑑 12)) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 9
 For exponential
3
 15 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3375 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
3
 15 𝑚𝑚𝑜𝑜𝑑𝑑 12
= ((15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(15 𝑚𝑚𝑜𝑜𝑑𝑑 12)) 𝑚𝑚𝑜𝑜𝑑𝑑 12
= 27 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
Introduction to ICT(a) 11th week
15
モジュロ演算
 余りを取る演算
 27 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
 加算
 (7+6) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 13 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 1
 乗算
 (15×3) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 45 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 9
 (15×3) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = ((15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(3 𝑚𝑚𝑜𝑜𝑑𝑑 12)) 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 9
 累乗
3
 15 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3375 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
3
 15 𝑚𝑚𝑜𝑜𝑑𝑑 12
= ((15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(15 𝑚𝑚𝑜𝑜𝑑𝑑 12)×(15 𝑚𝑚𝑜𝑜𝑑𝑑 12)) 𝑚𝑚𝑜𝑜𝑑𝑑 12
= 27 𝑚𝑚𝑜𝑜𝑑𝑑 12 = 3
Introduction to ICT(a) 11th week
16
The point of RSA cipher (1)
 P, Q： Very big prime numbers
 N = P× Q
 Decide E, D so that it fulfills E× D = m× (P-1)× (Q1) + 1 （m is an arbitrary natural number）
 Actually, “LCM(P-1, Q-1)+1”
E D
 (X ) = X (mod N)
 Is the secret key able to be calculated from the
public key （E, N） which is already known?
Introduction to ICT(a) 11th week
17
RSA暗号のポイント（１）
 P, Q：すごく大きな素数
 N = P× Q
 E× D = m× (P-1)× (Q-1) + 1 を満たすように E, D
を決める（mは任意の自然数）
 実際は“((P-1)と(Q-1)の最少公倍数)+1”
X
ED
= X (mod N)
 公開鍵（E, N）は既知だが、これらから秘密鍵を求
めることはできるか？
Introduction to ICT(a) 11th week
18
The point of RSA cipher (2)
 Is the secret key able to be calculated from the public key （E, N）
which is already known?
 Answer: YES! ...but, it takes UNFEASIBLE time if P, Q are very big
prime numbers.
 Because there are no fast algorithms to solve factorization in big prime
numbers.
 Example（RSA-129）
 N=11438162575788886766923577997614661201021829672124236256
2561842935706935245733897830597123563958705058989075147599
290026879543541（129 digits）
 P=34905295108476509491478496199038981334177646384933878439
90820577（64 digits）
 Q=32769132993266709549961988190834461413177642967992942539
798288533（65 digits）
 A number over 600 digits is used currently. （RSA-2048）
Introduction to ICT(a) 11th week
19
RSA暗号のポイント（２）
 公開鍵（E, N）は既知だが、これらから秘密鍵を求めること
はできるか？
 答：できる、が、P, Qが大きい数だとめちゃくちゃ（現実的で
はない）時間が掛かる
 素因数分解を速く行うアルゴリズムがないため
 例（RSA-129）
 N=114381625757888867669235779976146612010218296721242
36256256184293570693524573389783059712356395870505898
9075147599290026879543541（129桁）
 P=349052951084765094914784961990389813341776463849338
7843990820577（64桁）
 Q=32769132993266709549961988190834461413177642967992
942539798288533（65桁）
 現在は600桁以上使う（RSA-2048）
Introduction to ICT(a) 11th week
20
Mini report of this week
 Caesar cipher (ROT13)
 Encrypt “toyohashi” by ROT13
 Decipher “tvxnqnv” by ROT13
 RSA cipher
 Encrypt “toyohashi” character by character by using the
table of Excel （P = 3, Q = 11） and E = 3
 Decipher “aik2m2i” encrypted by E = 7 character by
character （D according to E = 7 is 3）
 Today’s impression
Introduction to ICT(a) 11th week
21
今週のミニレポート
 シーザー暗号（ROT13）
 ROT13で「toyohashi」を暗号化せよ
 ROT13で「tvxnqnv」を復号せよ
 RSA暗号
 Excelの表（P = 3, Q = 11）を使って、E = 3 で「toyohashi」を
１文字ずつ暗号化せよ
 同じく E = 7 で暗号化された「aik2m2i」を１文字ずつ復号
せよ（E = 7に対応する D は 3 である）
 本日の感想
Introduction to ICT(a) 11th week
22

Download Report