[Blockchain and Cryptocurrency] 03. Blockchain's Theoretical Foundation, Cryptography
0 likes12,227 views
'Blockchain and Cryptocurrency' Subject @ Korea University, 2021 01. Syllabus 02. Blockchain Overview and Introduction - Technical Concepts of Blockchain Systems - 03. Blockchain's Theoretical Foundation, Cryptography 04. Bitcoin and Nakamoto Blockchain 05. Ethereum and Smart Contract 06. NFT and Metaverse 07. Cardano(ADA) and Other Altcoins 08. Dark Coins 09. Blockchain Usage Beyond Currency - Way to Design Good Blockchain Business Models -
![????????????
??? ?? ??? ??
(¡Ì: zk-STARKs)
[1] Bitcoin Beginner, ¡°Privacy Coin Comparison¡±, December 30, 2017
[2] Felix K¨¹ster, "Privacy Coins Guide: Comparison of Anonymous Cryptocurrencies", Aug 23, 2017
Dark Coin, ¡®???(Monero)¡¯
6](https://image.slidesharecdn.com/gsis03-211212061359/85/Blockchain-and-Cryptocurrency-03-Blockchain-s-Theoretical-Foundation-Cryptography-6-320.jpg)
![????????????
??? ?? ??? ??
(¡Ì: zk-STARKs)
[1] Bitcoin Beginner, ¡°Privacy Coin Comparison¡±, December 30, 2017
[2] Felix K¨¹ster, "Privacy Coins Guide: Comparison of Anonymous Cryptocurrencies", Aug 23, 2017
Dark Coin, Zcash (2016)
8](https://image.slidesharecdn.com/gsis03-211212061359/85/Blockchain-and-Cryptocurrency-03-Blockchain-s-Theoretical-Foundation-Cryptography-8-320.jpg)
![????????????
??? ?? ??? ??
[Note] Telegram
27](https://image.slidesharecdn.com/gsis03-211212061359/85/Blockchain-and-Cryptocurrency-03-Blockchain-s-Theoretical-Foundation-Cryptography-27-320.jpg)
![????????????
??? ?? ??? ??
Bob¡¯s Public Key
Asymmetric
Cipher
(RSA)
Secret Key
Symmetric
Cipher
(AES)
Plaintext
Encrypted Key
hdr45bceuh73
6&%ewv3445
Ciphertext
50$4gbsghh73
6&355hk3445
Asymmetric
Cipher
(RSA)
Symmetric
Cipher
(AES)
Ciphertext
50$4gbsghh73
6&355hk3445
Encrypted Key
hdr45bceuh73
6&%ewv3445
Bob¡¯s Private Key
Plaintext
Secret Key
[Alice] [Bob]
Hybrid Encryption (Digital Envelope)
100](https://image.slidesharecdn.com/gsis03-211212061359/85/Blockchain-and-Cryptocurrency-03-Blockchain-s-Theoretical-Foundation-Cryptography-100-320.jpg)
![????????????
??? ?? ??? ??
SPA on PIN
for i = 0 to 2
if (INPUT[i] ¡Ù PWD[i])
return(¡°REJECT¡±)
return(¡°ACCEPT¡±)
212](https://image.slidesharecdn.com/gsis03-211212061359/85/Blockchain-and-Cryptocurrency-03-Blockchain-s-Theoretical-Foundation-Cryptography-212-320.jpg)
[Blockchain and Cryptocurrency] 03. Blockchain's Theoretical Foundation, Cryptography
- 1. ???????????? ??? ?? ??? ?? 1 ????? ??? ??, ???
- 2. ??????? ??? ?? (skim71@korea.ac.kr) ??????? 610? ? ? Security Assessment aNd Engineering Lab www.KimLab.net / www.HackProof.systems ?? ?? : 1990.3~1999.2) ?????? ?? ??¡¤??¡¤?? 1998.12~2004.2) KISA ?????? ? CC??1?? 2004.3~2011.2) ?????? ??????? ??? 2011.3~??) ????? ??????????????? ??? (?)HARU & SECUINSIDE ??? ? ?? 2017.4~??) ??RMF????(AR2C) ??? 2018.5~??) ?????????????(CHAOS) ??? Ç°) ?????? ???? Ç°) ??????????? ?? Ç°) ????? 4???????? ?? ¬F) ?????? ?????? ¬F) ??? CIO ???? ¬F) Black Hat Asia Review Board - SCI(E) ??: 76?, ????: 4800+ (?? ??) - '07, '18: ?????? ? ????? ?? ?? - '12, '16: ????? ????? (?? 5%) - '19: ?????????? ????? ????? ?? (?? 0.3% = 3?/800??) - ACSAC (1?), AsiaCrypt (1?), BlackHat (6?), CT-RSA (3?), DEFCON (4?), ICCC (8?), Virus Bulletin (2?) - KBS '????', '????', '?? ??', EBS '???? ???', JTBC '???? ???' ? tvN '????' ? ?? ?? ?? R&D ?? 2 Google? DRM ?? ?? (2020?)
- 3. ???????????? ??? ?? ??? ?? ??????? ???? ??? 3
- 4. ???????????? ??? ?? ??? ?? Bitcoin (2008) (In October 2008, posted to the Cypherpunks mailing list) 4
- 5. ???????????? ??? ?? ??? ?? ????? ??? ?????? 5 Smart Contract PoW
- 6. ???????????? ??? ?? ??? ?? (¡Ì: zk-STARKs) [1] Bitcoin Beginner, ¡°Privacy Coin Comparison¡±, December 30, 2017 [2] Felix K¨¹ster, "Privacy Coins Guide: Comparison of Anonymous Cryptocurrencies", Aug 23, 2017 Dark Coin, ¡®???(Monero)¡¯ 6
- 7. ???????????? ??? ?? ??? ?? 7
- 8. ???????????? ??? ?? ??? ?? (¡Ì: zk-STARKs) [1] Bitcoin Beginner, ¡°Privacy Coin Comparison¡±, December 30, 2017 [2] Felix K¨¹ster, "Privacy Coins Guide: Comparison of Anonymous Cryptocurrencies", Aug 23, 2017 Dark Coin, Zcash (2016) 8
- 9. ???????????? ??? ?? ??? ?? Zcash? ??? ?? 9
- 10. ???????????? ??? ?? ??? ?? 10
- 11. ???????????? ??? ?? ??? ?? ??? ???? ??? 11
- 12. ???????????? ??? ?? ??? ?? 12
- 13. ???????????? ??? ?? ??? ?? 13
- 14. ???????????? ??? ?? ??? ?? 14
- 15. ???????????? ??? ?? ??? ?? 15
- 16. ???????????? ??? ?? ??? ?? 16
- 17. ???????????? ??? ?? ??? ?? 17
- 18. ???????????? ??? ?? ??? ?? 18
- 19. ???????????? ??? ?? ??? ?? (Source: ???, 2013.12.) (¡°Upstream¡± Data) 19
- 20. ???????????? ??? ?? ??? ?? 20
- 21. ???????????? ??? ?? ??? ?? ??? ????? 21
- 22. ???????????? ??? ?? ??? ?? ??? ????? 22
- 23. ???????????? ??? ?? ??? ?? (Source: ???, 2015.11.) ??? ????? 23
- 24. ???????????? ??? ?? ??? ?? 24
- 25. ???????????? ??? ?? ??? ?? End-to-End Encryption (??? ???) 25
- 26. ???????????? ??? ?? ??? ?? a.k.a. Warrant-Proof Encryption 26
- 27. ???????????? ??? ?? ??? ?? [Note] Telegram 27
- 28. ???????????? ??? ?? ??? ?? ??? Secure Messenger? 28
- 29. ???????????? ??? ?? ??? ?? 29
- 30. ???????????? ??? ?? ??? ?? 30
- 31. ???????????? ??? ?? ??? ?? 31 The Rise of Side Effects
- 32. ???????????? ??? ?? ??? ?? Privacy vs. Lawful Access 32
- 33. ???????????? ??? ?? ??? ?? Privacy vs. Lawful Access 33
- 34. ???????????? ??? ?? ??? ?? Privacy vs. Lawful Access 34
- 35. ???????????? ??? ?? ??? ?? Privacy vs. Lawful Access 35
- 36. ???????????? ??? ?? ??? ?? Privacy vs. Lawful Access 36
- 37. ???????????? ??? ?? ??? ?? 37 Privacy vs. Lawful Access in Korea
- 38. ???????????? ??? ?? ??? ?? (?? : Natureresearch Journal, doi: 10.1038/d41586-020-00740-y) 38
- 39. ???????????? ??? ?? ??? ?? ???? ??? ????? ???? ??? ???. ???? ??? ????? ???? ??? ???. ???? ??? ? ???, ?? ??? ??? ???? ?? ??? ?? ? ? ??? ??? ??. 39 Privacy vs. Lawful Access in Korea
- 40. ???????????? ??? ?? ??? ?? ??? ??? 40
- 41. ???????????? ??? ?? ??? ?? ??? ??? 41
- 42. ???????????? ??? ?? ??? ?? ?? ?? 42
- 43. ???????????? ??? ?? ??? ?? What is Crypto? Cryptology : science of secret communication Cryptography : design secret systems Cryptanalysis : break secret systems 43
- 44. ???????????? ??? ?? ??? ?? What is Crypto¡¯s Goal? Symmetric-key ciphers: ?Block ciphers ?Stream ciphers Public-key ciphers Cryptographic goals Confidentiality Data integrity Authentication Non-repudiation Message authentication Entity authentication Arbitrary length hash functions Message Authentication codes (MACs) Digital signatures Authentication primitives Digital signatures MACs Digital signatures (a.k.a. Data origin authentication) 44
- 45. ???????????? ??? ?? ??? ?? ? Plaintext : the original message ? Ciphertext : the coded message ? Cipher : algorithm for transforming plaintext to ciphertext ? Key : information used in cipher known only to sender/receiver ? Encipher (Encrypt) : converting plaintext to ciphertext ? Decipher (Decrypt) : recovering plaintext from ciphertext ? Cryptanalysis : analyzing of encrypted without legitimate access to the keys. ? Brute Force Search : simply try every possible key Terminology 45
- 46. ???????????? ??? ?? ??? ?? ? Classic (~ 1976/77) ? BC 487 : Transposition Cipher, ¡°Scytale¡± ? BC 300 : Steganography ? BC 100 ~ BC 44 : Substitution Cipher, ¡°Caesar Cipher¡± ? 1883 : Kerckhoffs' Assumption ? WW II : ? ¡°Enigma¡± and ¡°Turing Machine¡± for Cryptanalysis ? 1949 : Perfect Secrecy (C.E.Shannon) ? ¡°Confusion¡± and ¡°Diffusion¡± Brief History 46
- 47. ???????????? ??? ?? ??? ?? ? Modern (1976/77 ~ Today) ? 1976 : Public-Key Cryptography (Diffie, Hellman) ? 1977 : Data Encryption Standard, DES (NIST) ? 1978 : RSA (Rivest, Shamir, Adleman) ? 1982/85 : Goldwasser presented 2 paradigms for firm foundations of cryptography. ? ¡°Indistinguishability¡± and ¡°Simulatability¡± ? 1999 : SEED (KISA) Brief History 47
- 48. ???????????? ??? ?? ??? ?? ? BC 2000 : Pictographs (????) The Origin of Crypto 48
- 49. ???????????? ??? ?? ??? ?? ? BC 487 : ?? ??? ??? ? ?? ?? ?????? ????? ¡°Scytale¡± ?? ? ??? ??? ?? The Origin of Crypto Key (the circumference of the scytale) 49
- 50. ???????????? ??? ?? ??? ?? ? ??(ÞDÖÃ) ?? ? Permutation/Transposition ?? ? ?? ?? ?? ??? ??? ?? ?? ????? ?? Transposition Cipher 50
- 51. ???????????? ??? ?? ??? ?? ? ?? ?? ? ?1? ???? ?? ???? ?? ? ?? (Grille) : Transposition Cipher ¨C (e.g.) ?? ?? 51
- 52. ???????????? ??? ?? ??? ?? ? ¡°We need more machine gun ammunition fast xx¡±?? ??? ???? ? ?? Transposition Cipher ¨C (e.g.) ?? ?? 52
- 53. ???????????? ??? ?? ??? ?? ? Cipher vs. Steganography Steganography ??? 1KG? XX? ?? ? ? ? ? ? 53
- 54. ???????????? ??? ?? ??? ?? ? ???????(steganography)? ???? ? ¡®??? ?(covered writing)¡¯??? ? ? 2,300?? ???? ??? ???? (Miletus)?? ???? ?? ?????? (Histiaeus)? ????? ???? ? ?? ??? ???? ?? ??? ?? ?? ? ?? ????? ????, ??, ?? ?? ????? ??? ?? ?? ?? ? ???? ?? ??? ?? ??? ??? ? ?? ?? Steganography 54
- 55. ???????????? ??? ?? ??? ?? Steganography Apparently neutral's protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext for embargo on by-products, ejecting suets and vegetable oils. WWII?? ??? ??????? ??? (¡°Pershing sails from NY June 1.¡±) 55
- 56. ???????????? ??? ?? ??? ?? Steganography ¡°I AM TRAPPED¡±?? ??? ?? ?? 56
- 57. ???????????? ??? ?? ??? ?? Steganography ??? 1KG? XX? ?? ? ? ? ?? ????? 57
- 58. ???????????? ??? ?? ??? ?? ? ??? ??? ?? ??, ?? ?? ?? ? ???? ???? ? Plaintext) Come here at once ? Ciphertext) Substitution Cipher (“Q×Ö ??) 58
- 59. ???????????? ??? ?? ??? ?? ? Security) ?? ?? ??? ??? ??? ? ??? ??? ?? Substitution Cipher (“Q×Ö ??) 0.127 0.091 0.082 0.075 0.070 0.067 0.063 0.061 0.060 0.043 0.040 0.028 0.028 0.024 0.023 0.022 0.020 0.020 0.019 0.015 0.010 0.008 0.002 0.001 0.001 0.001 0.000 0.020 0.040 0.060 0.080 0.100 0.120 0.140 E T A O I N S H RD L C UMWF G Y P B V K J Q X Z 59
- 60. ???????????? ??? ?? ??? ?? Geoffrey Chaucer, Treatise on the Astrolabe, 1391 60
- 61. ???????????? ??? ?? ??? ?? Substitution Cipher ¨C (e.g.) ??? ?? 61
- 62. ???????????? ??? ?? ??? ?? ? ?? ?? ? ???? ??? ?? ???(Philip Johnston)??, ?2? ???? ?? ?? ? ???. ? ????? ????? ??? ? ?? 211?? ??? ???? ???. ? ?? ? ??, ????(iron fish) ? ???, ???? ? ???, ??? ? ?? Substitution Cipher ¨C (e.g.) ??? ?? 62
- 63. ???????????? ??? ?? ??? ?? ? 2? ?? ?? ? ??? ??? ?? ? ? ???? 28?? ?????, ??? ???? ???? ? ?? ???? ?. ? 1968? ???? 1? ????? ??? ??? ??. ? 2001?? ??? ??? ?? 29?? ? ?? ?? ??? ????? ????? ?? ??????? ?? ????? ? ??. Substitution Cipher ¨C (e.g.) ??? ?? 63
- 64. ???????????? ??? ?? ??? ?? ? ???? ?? ?? ?? ??? ?? ? ? ??? ?? ??? ???? ???? ?? ? ??. ? ??? ¡°??? ??? ?? ???? ? ?¡±????, ? ??? ???? ??? ? ???? ? ??. ? 1945?? C.E.Shannon? ?? ?????? ? ???. Product Cipher 64
- 65. ???????????? ??? ?? ??? ?? Enigma & Alan Turing 65
- 66. ???????????? ??? ?? ??? ?? Enigma & Alan Turing 66
- 67. ???????????? ??? ?? ??? ?? ? The Father of Information Theory ? Information Theory ? Worked at MIT / Bell Labs ? ¡°The Math. Theory of Communication¡± (1948) ? Def. of the ¡°binary digit¡±(bit) as a unit of info. ? Def. of ¡°entropy¡± as a measure of info. ? Cryptography ? Model of a secrecy system ? ¡°Communication Theory of Secrecy Systems¡± (1945, Bell Labs memo, classified). ? Def. of ¡°perfect secrecy¡± ? Formulate the principles of ¡°confusion¡± (standing for substitution) and ¡°diffusion¡± (standing for transposition) Claude E. Shannon (1916~2001) 67
- 68. ???????????? ??? ?? ??? ?? Claude E. Shannon (1916~2001) 68
- 69. ???????????? ??? ?? ??? ?? ?? ?? 69
- 70. ???????????? ??? ?? ??? ?? ? Key : 5e d9 20 4f ec e0 b9 67 ? Plaintext : ¡°The unknown message is: The DES-test contest's plaintext¡± ? Ciphertext : 3e a7 86 f9 1d 76 bb d3 66 c6 3f 54 eb 3f e3 3f 39 88 81 4c 8b a1 97 f7 be 1b dd 7e fb 39 96 31 3c 3d 3b 65 c8 b8 3e 31 89 f9 04 14 fb cd c3 70 c1 11 a5 2f 3a ef 80 f4 cf f5 43 a4 b1 65 5b ae Modern Ciphers (e.g., DES) 70
- 71. ???????????? ??? ?? ??? ?? Modern Ciphers ¨C Stream Cipher ¨C Pseudo-Random Sequence Generator Plaintext Bitstream Ciphertext Bitstream Key 1 1 1 1 1 1 1 1 0 0 0 0 0 0 ¡ 1 0 0 1 1 0 1 0 1 1 0 1 0 0 ¡ 0 1 1 0 0 1 0 1 1 1 0 1 0 0 ¡ Plaintext Stream Pseudo-Random Stream Ciphertext Stream 71
- 72. ???????????? ??? ?? ??? ?? Modern Ciphers ¨C Block Cipher ¨C ciphertext blocks n bits n bits plaintext blocks n bits n bits Common Block Sizes: n = 64, 128, 256 bits Common Key Sizes: k = 40, 56, 64, 80, 128, 168, 192, 256 bits k bits Key Block Cipher n bits 72
- 73. ???????????? ??? ?? ??? ?? Block Length Algorithm Key Length DES (Data Encryption Standard, IBM) 64 56 3DES (Triple DES) 64 168 IDEA (Lai / Massey, ETH Z¨¹rich) 64 128 RC2 (Ron Rivest, RSA) 64 40 ... 1024 CAST (Canada) 64 128 RC5 (Ron Rivest, RSA) 64 ... 256 64 ... 256 AES (Advanced Encryption Standard) 128 128 ... 256 SEED (KISA, Korea) 128 128 Modern Ciphers ¨C Block Cipher ¨C 73
- 74. ???????????? ??? ?? ??? ?? ? 1973? ?? NIST? ?? ??? ??? ??? ??? ?? RFP? ???. ? ?? ????? IBM? ??? LUCIFER ? ?(??? : Horst Feistel et al.)? ???? ???? ??? (??, DES). ???(???)?? DES? ?? 74
- 75. ???????????? ??? ?? ??? ?? ? 1975? 3?, DES? FIPS(Federal Information Processing Standard) Draft ???? ?? ??? ???. ?? DES? ?? ?????? ???? ?? ??? ?. ? ?? DES? ???? 1983?, 1988?, 1993? NBS? ?? ???????, 1998 ? 12?? ????? ? ??? ??? ?. ? 1997? NIST? AES ????? ???. ???(???)?? DES? ?? 75
- 76. ???????????? ??? ?? ??? ?? ? ?? ??? ? ???? ?? ? ???? ??? ?? ? ??? ?? ? ??? ? ??? ?? ?? ? ???? ?? ? ???? ???? ??? ?? ?? ? ?? ?? DES? ?? ?? 76
- 77. ???????????? ??? ?? ??? ?? ? Data Encryption Standard ? DES? ???? ?? ? ???? ?? : 64??(?? 8?? ?? ?? 4? ? ??) ??? ???? ??? ????? ? ? ?? (????) : 64?? ??? ?? ?? ? 64?? ? 8??? ??? ??(parity bit)???, ?? ?? ?? ??? ?? 56??? ? ???(round) ? : 16???? ?? ???? ? ? ???? 16? ???? ?? ? confusion and diffusion DES in a Nutshell (1977) 77
- 78. ???????????? ??? ?? ??? ?? Initial Permutation F + F + F + F + ¡ Initial Permutation-1 (64) (64) (32) (32) (48) (48) (48) (48) Key Scheduler (56) K K1 K2 K16 K3 X Y ? F need not be invertible! ? Have ¡°unstructured¡± behavior. ? Decryption is the same as encryption with reversed key schedule (hardware implementation!). DES in a Nutshell (1977) 78
- 79. ???????????? ??? ?? ??? ?? DES in a Nutshell (1977) ¨C 1 Round ¨C Expansion Permutation 48 P-Box Permutation S-Box Substitution 32 Shift Shift 48 Compression Permutation Feistel Network 56 32 32 Keyi-1 Ri-1 Li-1 Keyi Ri Li 32 32 56 79
- 80. ???????????? ??? ?? ??? ?? DES in a Nutshell (1977) ¨C 1 Round ¨C 80
- 81. ???????????? ??? ?? ??? ?? DES in a Nutshell (1977) ¨C 1 Round ¨C 81
- 82. ???????????? ??? ?? ??? ?? ?????? ???? ??? ?? (¡®76) 82
- 83. ???????????? ??? ?? ??? ?? ? ???? ??? ????? ?? ??? ?? ?? ????? ?????? ?? ???? ??? ?????? ?? ?? ? ??? ?????? ???? ? ?? ??? ????? ??. ? ??? ??? DES ?? ?? ?? ¡®?? ? ?? ??(Œ¦·Q? °µÌ– ·½Ê½, symmetric key cryptosystem)¡¯??? ????? ? ?? ?? ??? ??? ?? ??? ? ?? ???? ?? ?? ??? ?? ? ?? ??. ?????? ???? ??? ?? (¡®76) 83
- 84. ???????????? ??? ?? ??? ?? ? Symmetric Cipher (Secret Key Encryption) : Encryption Key = Decryption Key ? Asymmetric Cipher (Public Key Encryption) : Encryption Key ¡Ù Decryption Key ?????? ???? ??? ?? (¡®76) 84
- 85. ???????????? ??? ?? ??? ?? Public Key Private Key Encryption Key Decryption Key PKC in a Nutshell (1976) 85
- 86. ???????????? ??? ?? ??? ?? Alice Bob Directory Alice + + Bob + Encryption Decryption PKC in a Nutshell (1976) 86
- 87. ???????????? ??? ?? ??? ?? PKC in Formal (1976) 87
- 88. ???????????? ??? ?? ??? ?? ?????? ???? ??? ?? (¡®78) 88
- 89. ???????????? ??? ?? ??? ?? ?????? ???? ??? ?? (¡®78) 89
- 90. ???????????? ??? ?? ??? ?? ?????? ???? ??? ?? (¡®78) 90
- 91. ???????????? ??? ?? ??? ?? RSA in a Nutshell (1978) Alice + + Bob + Alice Bob Directory 31 13 ¡±A¡± 13 6513 369,720,589,101, 871,337,890,625 1/13 (6513)1/13 = 65 = ¡°A¡± Encryption Decryption 91
- 92. ???????????? ??? ?? ??? ?? Hard (NP) 317 = 129,140,163 129,140,163 ¡õ = 3 ¡ú ¡õ = 1/17 317 mod 2773 = 1553 1553 ¡õ mod 2773 = 3 ¡ú ¡õ = 157 Easy (P) RSA in a Nutshell (1978) 92
- 93. ???????????? ??? ?? ??? ?? RSA in a Nutshell (1978) Alice + + Bob + Directory ¡±!¡± (7, 55) 23 Encryption Decryption Bob 7, 55(= 5¡Á11) 337 mod 55 = 22 22 2223 mod 55 = 33 = ¡°!¡± 93 ¢Ù Select two random primes : 5, 11 ¢Ú Select random number : 7 ¢Û Compute EUCLID(7,5,11)=23 ¢Ü Compute 5¡Á11=55 ¢Ý Publish (7,55) as Public Key ¢Þ Keep 23 as Private Key
- 94. ???????????? ??? ?? ??? ?? ? M = 10101111010011111¡¡(2) = a¡Á55n-1 + b¡Á55n-2 + ¡. c¡Á550 (where, 0 ¡Ü a, b, ¡, c ¡Ü 54) ? C = M7 mod 55 = (a7 mod 55, b7 mod 55, ¡, c7 mod 55) RSA in a Nutshell (1978) 94
- 95. ???????????? ??? ?? ??? ?? m 00¡0 r G(r) m1 * H(m1 *) m2 * G H ( ) : ? f one-way permutation C = f(OAEP(m,r)) = (m1 *||m2 *)e mod N RSA-OAEP (1994) 95
- 96. ???????????? ??? ?? ??? ?? ? Martin Gardner column and RSA-129 challenge ? Described public-key and RSA cryptosystem in his Scientific American column, Mathematical Games (1977) ? Ron Rivest offered copy of RSA technical memo. ? Ron Rivest offered $100 to first person to break challenge ciphertext based on 129-digit product of primes. ? Ron¡¯s estimated time to solution: 40 quadrillion years RSA? ??????? 96
- 97. ???????????? ??? ?? ??? ?? ? Question (1977) : ? N=114,381,625,757,888,867,669,235,779,976,146 ,612,010,218,296,721,242,362,562,561,842,935,70 6,935,245,733,897,830,597,123,563,958,705,058,9 89,075,147,599,290,026,879,543,541 ? Answer (1994, 8 months work by about 600 volunteers from more than 20 countries; 5000 MIPS-years.) : ? p=32,769,132,993,266,709,549,961,988,190,834,4 61,413,177,642,967,992,942,539,798,288,533 ? q=3,490,529,510,847,650,949,147,849,619,903,89 8,133,417,764,638,493,387,843,990,820,577 RSA? ??????? 97
- 98. ???????????? ??? ?? ??? ?? RSA? ??????? 98
- 99. ???????????? ??? ?? ??? ?? ??? ?? vs. ???? ?? ?? ??? ?? ?? ???? ?? ?? ?? BC 487? ? 1976? ? ???(???) ????(???, ???) ?? ?? ?? ??? ? = ??? ? ??? ? ¡Ù ??? ? ??? ?/??? ? ??/?? ??/?? ?? ???? ?? ?? ?? ?? n*(n-1)/2 2*n ?? ???? ?? ??? ? ?? ?? ??? ?? ??? ??? ?? ?? ?? ?? ?? ? ?? ? ??? ??? ???? ?? ???? ?? ???? ? DES, AES, IDEA, SEED, ARIA DH, RSA, ECC 99
- 100. ???????????? ??? ?? ??? ?? Bob¡¯s Public Key Asymmetric Cipher (RSA) Secret Key Symmetric Cipher (AES) Plaintext Encrypted Key hdr45bceuh73 6&%ewv3445 Ciphertext 50$4gbsghh73 6&355hk3445 Asymmetric Cipher (RSA) Symmetric Cipher (AES) Ciphertext 50$4gbsghh73 6&355hk3445 Encrypted Key hdr45bceuh73 6&%ewv3445 Bob¡¯s Private Key Plaintext Secret Key [Alice] [Bob] Hybrid Encryption (Digital Envelope) 100
- 101. ???????????? ??? ?? ??? ?? Diffie-Hellman Key Agreement Alice Bob 35 = 243 37 = 2187 K = 21875 = (37)5 = 335 = 50,031,545,098,999,707 ??? ???? 3 K = 2437 = (35)7 = 335 = 50,031,545,098,999,707 101
- 102. ???????????? ??? ?? ??? ?? Diffie-Hellman Key Agreement Alice Bob 35 mod 127 = 116 37 mod 127 = 28 K = 285 = (37)5 = 335 = 90 (mod 127) ??? ???? 3, 127 K = 1167 = (35)7 = 335 = 90 (mod 127) 102
- 103. ???????????? ??? ?? ??? ?? Hard (NP) g¡õ = Y 10 ¡õ = 10,000,000,000 ¡ú ¡õ = 10 g¡õ mod p = Y 10 ¡õ mod 19 = 9 ¡ú ¡õ = 10 Easy (P) ???? ?? 103
- 104. ???????????? ??? ?? ??? ?? ???? ?? Z Z23 (mod 23) 51 5 5 52 25 2 53 125 10 54 625 4 55 3125 20 56 15625 8 ¡ ¡ ¡ 104
- 105. ???????????? ??? ?? ??? ?? ???? ?? (Elliptic Curve Crypto) 105
- 106. ???????????? ??? ?? ??? ?? ? ????? "????"? ???? ??? ???? ??? ??. ? ????? ??? ?? ??? ????? ??? ?? ???. y2 = x3 + ax + b mod n (?, 0 ¡Ü x,y < n) ????(Elliptic Curve)??? 106
- 107. ???????????? ??? ?? ??? ?? ? Diffie-Hellman ? Keys generated by exponentiation over the group. ? Exponentiation defined by repeated multiplication ? Elliptic Curve Diffie-Hellman ? ECC was introduced by Victor Miller and Neal Koblitz in 1985. ? Keys generated by multiplication over elliptic curves. ? Multiplication through repeated addition ? Cryptanalysis involves determining k given a and (k x G) ???? Diffie-Hellman 107
- 108. ???????????? ??? ?? ??? ?? ???? Diffie-Hellman 108
- 109. ???????????? ??? ?? ??? ?? 109
- 110. ???????????? ??? ?? ??? ?? ????, ???? ??? ????? 110
- 111. ???????????? ??? ?? ??? ?? ????(Digital Signature)? ?? Data integrity + Message authentication + Non-repudiation 111
- 112. ???????????? ??? ?? ??? ?? ????(Digital Signature)? ???? Public Key Private Key Encryption = Verification Decryption = Signing 112
- 113. ???????????? ??? ?? ??? ?? message Signing algorithm message signature Signer¡¯s private key Unsecured channel Signer Signature verification algorithm Signer¡¯s public key Verifier Ok / not Ok ????(Digital Signature)? ???? 113
- 114. ???????????? ??? ?? ??? ?? RSA Digital Signature ? ? ? ? ? ? ???? ???? ??? ??? ??? ??? ??? ??? 31 13 + 31 651/31 = 0.032258 0.03225831 = (651/31)31 = 65 =? ¡°A¡± + ¡°A¡± 1/31 ¡°A¡± 0.032258 0.032258 114
- 115. ???????????? ??? ?? ??? ?? RSA Digital Signature & Hash Function 115
- 116. ???????????? ??? ?? ??? ?? ? Public Key = (17, 2773), Private Key (157) ? M = ¡°EBS Korea Educational Broadcasting System¡± : ? H(¡°EBS Korea Educational Broadcasting System¡±) = 3 ? 3157 mod 2773 = 441 RSA Digital Signature & Hash Function 116
- 117. ???????????? ??? ?? ??? ?? Hash Function (?? ??) Message M (arbitrary length) Hash Value h (fixed length) H 117
- 118. ???????????? ??? ?? ??? ?? Hash Function (?? ??) 118
- 119. ???????????? ??? ?? ??? ?? Cryptographic Hash Function SHA256 SHA256 SHA256 X ? ? Different ? Hello! ? 334d016f755cd6do58c53a86e1 a3b8ef80c14f52fb05145b87ce3 a5edd42c87b? 334d016f755cd6do58c53a86e1 a3b8ef80c14f52fb05145b87ce3 a5edd42c87b? Collision resistance Preimage resistance 2nd-preimage resistance 119
- 120. ???????????? ??? ?? ??? ?? Cryptographic Hash Function 120
- 121. ???????????? ??? ?? ??? ?? Cryptographic Hash Function 121
- 122. ???????????? ??? ?? ??? ?? ? 1990?) Ron Rivest? MD4(Message Digest Algorithm 4)?? ?? ??? ??. ? 1992?) Ron Rivest? MD4? ??? MD5? ? 128?? ?? ??? ??. ? ?? MD5? ?? ????? ???(?? ¡°collisions for random IV¡±)? ???? ??? ? ??? ????? ???? ? ?? ???? ? ?? ?? ??. ? 1993?) ÃÀ NSA? MD5? ?? ??? SHA(Secure Hash Algorithm)??? ??? ?? ??? ???. Cryptographic Hash Function? ?? 122
- 123. ???????????? ??? ?? ??? ?? ? 1995?) 1995?? SHA? ??? ???? ???? NSA? SHA? ??? SHA-1? ? ? ? 1998?) ??? KISA? KIISC? MD5? SHA-1? ??? ??? ?????? HAS- 160(160-bit Hash Algorithm Standard)? ? ? ? 2005?) 2005? ?? ????? Wang Xiaoyun ???? 160?? ??? SHA-1? ?? ?? ?? ?? ??? ??. ?? 280? ?? ?? ???? ??? ??? SHA-1? ?? ???? 269?? ??. Cryptographic Hash Function? ?? 123
- 124. ???????????? ??? ?? ??? ?? Digital Signature in E-Certificates 124
- 125. ???????????? ??? ?? ??? ?? ? Loren Kohnfelder ¨C Invention of Digital Certificates ? Loren Kohnfelder¡¯s B.S. thesis (MIT 1978, supervised by Len Adleman), proposed notion of digital certificate ¡ª a digitally signed message attesting to another party¡¯s public key. ??? ??? ?? (1978) 125
- 126. ???????????? ??? ?? ??? ?? Alice Bob Directory Alice + + Eve + Encryption Decryption Bob ??? ??? ?? (1978) 126
- 127. ???????????? ??? ?? ??? ?? ??? ??? ?? (1978) 127
- 128. ???????????? ??? ?? ??? ?? ?????? ??? ??? 128
- 129. ???????????? ??? ?? ??? ?? ? 1999? 7? ?????? ??. ?? ? 9? ??? ?? ?? ??? ?? ¡®SEED¡¯ ??. ? ¡®??????? ??? ???? ??? ??? ?¡¯? ?? ??? ?? ?? ?? ????? ? ?? ??? ??? ???, ?? ??????? ??? ???????? ??? ?. ? 2002? 4?? ? ??. ? ??????? ??? ??? ¡ú ????? ? ??????? ??? ???? ??? ??? ? ¡ú ?????? ??????? 129
- 130. ???????????? ??? ?? ??? ?? ??????? 130
- 131. ???????????? ??? ?? ??? ?? ????????? ¨C NPKI vs. GPKI ??? ???? ?? NPKI GPKI ???? 131
- 132. ???????????? ??? ?? ??? ?? ????? 1??? ?? ?? 132
- 133. ???????????? ??? ?? ??? ?? ????? ?? ??? (2006) 133
- 134. ???????????? ??? ?? ??? ?? ??? ?? ?? (2014) 134
- 135. ???????????? ??? ?? ??? ?? ??? ?? ??? ?? (2014) 135
- 136. ???????????? ??? ?? ??? ?? ??? ?? ??? ?? (2014) 136
- 137. ???????????? ??? ?? ??? ?? ??? ?? ??? ?? (2015) 137
- 138. ???????????? ??? ?? ??? ?? ????? ???? ?? (2015) 138
- 139. ???????????? ??? ?? ??? ?? ?????? ?? (2020) 139
- 140. ???????????? ??? ?? ??? ?? ? ?????? ¡®??¡¯??? ??? ??? ?????, ??? ??? ???? ?? ?? ??? ???? ???? ?. ? ??????? ¡®?????¡¯ ? ¡®????? ? ??? ??????¡¯ ??? ?? ? ?? ?? ??? ?? ??? ?? ? ? ??? ?? ? ??? ???. ?????? ?? (2020) 140
- 141. ???????????? ??? ?? ??? ?? ? ?? ?? ???? ????? ???? ? ??? ? ???? ???? ?? ? ???? ??? ?? ? ??? ??? ?? ??? ?? ???? ?? ???? ??? ???? ?? ?? ??? ???? ?. ?????? ?? (2020) 141
- 142. ???????????? ??? ?? ??? ?? ? ?????? ?? ?? ?? ?? ??? ?? ?? ?? ????? ??? ??? ? ??. ? ????? ?????? ?? ?? ??? ??? ? ?? ??? ?? ?? ? ???, ? ?????? ?? ?? ?, ??? ???? ? ????? ?? ?? ????? ??? ? ??? ???? ?? ??. ?????? ????? ¨C ?? 142
- 143. ???????????? ??? ?? ??? ?? ?????? ????? ¨C ?? ?? ?? ?? (Easy) ??? ???? ? ????? ?? ?? 143
- 144. ???????????? ??? ?? ??? ?? 144
- 145. ???????????? ??? ?? ??? ?? DID? ??? ?? ?? ??? ?? ??? ?? ? ???? ?? ???? (?? ¡®Provable¡¯ ??). ???? ????? ?? ??? ?? ??? ?? ??? ? ??? DID? ?? ???? ?? ?? ??? ?? ???? ??? ??. 145
- 146. ???????????? ??? ?? ??? ?? ? ?? ??? ¡®?? ??¡¯? ???? ???. ? ???? ???? ???? ???? ?? ?? ? ?? ????? ?? ???? ?? ??? ?? ? ????? ?. ? ??? ???? ?? ?? ????? ?? ?? ??? ?? ?? ????? ??? ? ? ?? ?? ??? ??? ??? ??. ? ???? ?? ???? ? ??? ?? ??? ???? ??? ?? ??? ???? ?? ?? ???. ?????? ????? ¨C ??? 146
- 147. ???????????? ??? ?? ??? ?? 147
- 148. ???????????? ??? ?? ??? ?? 148
- 149. ???????????? ??? ?? ??? ?? ??? ????? 149
- 150. ???????????? ??? ?? ??? ?? ? ?? ???? ??? ? ?????? ???? ??????? 90% ??? ???? ?? 1?? 4??? ??? ?? ???. ? ??? ??? ?? ???? ???? ?? ? ?? ? ??? ?? ??? ??? ?? ???? ? ??. ? ??? ?? ??? ???? ?? ??? ??? ? ??? ?? ?? ??? ??? ? ?? ?? ? ?? ? ??? ???? ??? ??? ?? ?? ??? ??? ???? ?? ??? ??. ?????? ????? ¨C ?? ? ?? 150
- 151. ???????????? ??? ?? ??? ?? ?????? ????? ¨C ?? ? ?? 151
- 152. ???????????? ??? ?? ??? ?? ??? ?? 152
- 153. ???????????? ??? ?? ??? ?? Dawn of Provable Security (1982) 153
- 154. ???????????? ??? ?? ??? ?? ? ¡°Probabilistic Encryption¡±, Shafi Goldwasser, Silvio Micali (1982) (Encryption should be randomized!) ? ¡°A Digital Signature Scheme Secure Against Adaptive Chosen Message Attacks¡±, Goldwasser, Micali, Rivest (1988) (Uses well- defined game to define security objective.) Dawn of Provable Security (1982) 154
- 155. ???????????? ??? ?? ??? ?? Dawn of Provable Security (1982) 155
- 156. ???????????? ??? ?? ??? ?? It's not at all clear how to formalize the notion that "nothing is learned". 156
- 157. ???????????? ??? ?? ??? ?? What Is ¡°Nothing Is Learned¡°? Plaintext is ¡°I found a solution to the calendar sync problem¡±. 157
- 158. ???????????? ??? ?? ??? ?? What Is ¡°Nothing Is Learned¡°? Plaintext is english! Plaintext is ¡°I found a solution to the calendar sync problem¡±. Plaintext is ¡°¡. solution ¡. calendar sync ¡.¡±. 158
- 159. ???????????? ??? ?? ??? ?? Semantic Security 159
- 160. ???????????? ??? ?? ??? ?? ? Perfect secrecy : if a passive adversary, even with infinite computational resources, can learn nothing about the plaintext from the ciphertext, except possibly its length. ? Semantic security : a passive adversary with polynomially bounded computational resources can learn nothing about the plaintext from the ciphertext. Semantic Security 160
- 161. ???????????? ??? ?? ??? ?? Semantic Security in Formal 161
- 162. ???????????? ??? ?? ??? ?? Zero-Knowledge Interactive Proofs 162
- 163. ???????????? ??? ?? ??? ?? Zero-Knowledge Interactive Proofs 163
- 164. ???????????? ??? ?? ??? ?? (CRYPTO¡¯89) ZKIP for Kids 164
- 165. ???????????? ??? ?? ??? ?? 1. V stands at A. 2. P walks to C or D. 3. V walks to B. 4. V asks P to come L or R. 5. P follows the request. 6. Repeat 1 ~ 5, n times. ZKIP for Kids A B D C 165
- 166. ???????????? ??? ?? ??? ?? Applications of ZKIP (CRYPTO¡¯86) 166
- 167. ???????????? ??? ?? ??? ?? Applications of ZKIP 167
- 168. ???????????? ??? ?? ??? ?? Secure Computation 168
- 169. ???????????? ??? ?? ??? ?? Secure Multi-Party Computation (MPC) 169
- 170. ???????????? ??? ?? ??? ?? ? Cryptographic protocol for emulating a trusted party (already started in the late 1970s) ? MPC enables decentralization and privacy! Secure Multi-Party Computation (MPC) Goal : - Correctness : Everyone computes y=f(x,y) - Security : Nothing but the output is revealed 170
- 171. ???????????? ??? ?? ??? ?? ??? ?? ?? 171
- 172. ???????????? ??? ?? ??? ?? Ring Signature 172
- 173. ???????????? ??? ?? ??? ?? Dark Web 173
- 174. ???????????? ??? ?? ??? ?? Tor 174
- 175. ???????????? ??? ?? ??? ?? ? ??? ???? '??'? ???? ??? ? ????, ????? ???? ??? ?? David Chaum ??? 1981?? ?? ??? ???? ?????? ?? ??? ? ?? ?? ?? ? ?? 'Onion Routing', '??(TOR: The Onion Routing)', 'I2P(Invisible Internet Project)' ? ? ??? ????? ??? ?. 175 Mix Networks
- 176. ???????????? ??? ?? ??? ?? Mix Networks 176
- 177. ???????????? ??? ?? ??? ?? ?? ???? ?? ??? ??? 177
- 178. ???????????? ??? ?? ??? ?? ? Order-Preserving Encryption (OPE) ? Format-Preserving Encryption (FPE) ? Fully Homomorphic Encryption ? Searchable Encryption (for Cloud) Database Encryption 178
- 179. ???????????? ??? ?? ??? ?? Order-Preserving Encryption (OPE) ? OPE? ?? ? R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu, ¡°Order-preserving encryption for numeric data¡±, SIGMOD 2004, pp. 563~574 eA eD eC eB OPE key Plain data (A > B > C >D) cipher data (eA > eB > eC >eD) eA eB eC eD A B C D A D C B 179
- 180. ???????????? ??? ?? ??? ?? Order-Preserving Encryption (OPE) ? OPE? ??? ? A. Boldyreva, N. Chenette, Y. Lee, A. O'Neill, ¡°Order-Preserving Symmetric Encryption¡±, EUROCRYPT 2009, pp. 224~241 ? IND-CPA? ??? ? ??? ???? ????? CPA ??? ?? ????? ??? ? ??? ?? 180
- 181. ???????????? ??? ?? ??? ?? Format-Preserving Encryption (FPE) 181
- 182. ???????????? ??? ?? ??? ?? Format-Preserving Encryption (FPE) 182
- 183. ???????????? ??? ?? ??? ?? Format-Preserving Encryption (FPE) 183
- 184. ???????????? ??? ?? ??? ?? Format-Preserving Encryption (FPE) 184
- 185. ???????????? ??? ?? ??? ?? Whose Privacy? Data subject whose personal data is in DB Questioner Searchable Encryption (for Cloud) 185
- 186. ???????????? ??? ?? ??? ?? Searchable Encryption (for Cloud) 186
- 187. ???????????? ??? ?? ??? ?? Fully Homomorphic Encryption 187
- 188. ???????????? ??? ?? ??? ?? ? In 1978, Rivest, Adleman, and Dertouzos asked, ¡°Can one compute on encrypted data, while keeping it encrypted?¡± ? In 2009, Craig Gentry (Stanford, IBM) gave solution based on use of lattices. If efficiency can be greatly improved, could be huge implications (e.g. for cloud computing). Fully Homomorphic Encryption 188
- 189. ???????????? ??? ?? ??? ?? Fully Homomorphic Encryption ? C. Gentry, ¡°Fully homomorphic encryption using ideal lattices¡±, STOC 2009 ? ?? ??? ???? ???? ?? 189
- 190. ???????????? ??? ?? ??? ?? Fully Homomorphic Encryption 190
- 191. ???????????? ??? ?? ??? ?? 191
- 192. ???????????? ??? ?? ??? ?? Currently there is no ¡°silver bullet¡± solution, said Lynne Parker, White House deputy chief technology officer. She pointed to several reasons: ¡øData de-identification can be accidentally undone when the scrubbed data is combined with other sources of information. ¡øData aggregation limits analytics. ¡øSimulating data raises concerns about accuracy and reverse engineering, while homomorphic encryption ¡ª which allows data to be mined without sacrificing privacy ¡ª hurts performance and speed. Other techniques and technologies also have their weaknesses, she said. ¡øDifferential privacy, or systems that publicly share information on group patterns while withholding information on individuals in a dataset, water down insights. 192
- 193. ???????????? ??? ?? ??? ?? ?????? ??! Define & Design!! Identify privacy breach Design a new algorithm to fix the privacy breach Breach and Patch Approach Formally specify the privacy model Define and Design Approach Design an algorithm that satisfies the privacy conditions Derive conditions for privacy 193
- 194. ???????????? ??? ?? ??? ?? 194
- 195. ???????????? ??? ?? ??? ?? 195
- 196. ???????????? ??? ?? ??? ?? ¡°To help more researchers with their work, IBM released the open-source Differential Privacy Library.¡± 196
- 197. ???????????? ??? ?? ??? ?? 197
- 198. ???????????? ??? ?? ??? ?? ???? ??? ??? : ??? ?? 198
- 199. ???????????? ??? ?? ??? ?? Magnetic Card vs. Smart Card 199
- 200. ???????????? ??? ?? ??? ?? Smart Card 200
- 201. ???????????? ??? ?? ??? ?? ? ROM : Holds the Operating System ? EEPROM : Holds the application programs and their data ? PROM : Holds the card number ? RAM : Used as temporary storage space for variables ? Processor : 8 bit processor based on CISC architecture. Moving towards 32 bit due to JavaCards ? I/O Interface for data transfer to and from the card. Smart Card 201
- 202. ???????????? ??? ?? ??? ?? Smart Card Vcc (=5V) RST CLK RFU (??) Vpp (EEPROM ???? ??. ??? IC???? ??????, ???? ?? ? ?.) I/O GND RFU (??) 202
- 203. ???????????? ??? ?? ??? ?? Smart Card 203
- 204. ???????????? ??? ?? ??? ?? ? ??? K? ??? ??? ??? ??! ? Smart Card? ????? private key K CPU challenge c response fK(c) 204
- 205. ???????????? ??? ?? ??? ?? Smart Card Security 205
- 206. ???????????? ??? ?? ??? ?? Smart Card Security 206
- 207. ???????????? ??? ?? ??? ?? Smart Card Security Invasive Analysis Non-invasive Analysis Side Channel Attacks Probing Fault-based Analysis Timing Analysis Power Analysis A technique to probe signal after exposing surface of chips and removing protective coating A technique to derive internal confidential information using the difference between normal output and faulty output caused artificially A technique to estimate confidential information by analyzing processing time A technique to estimate confidential information by observing power consumption 207
- 208. ???????????? ??? ?? ??? ?? ? Paul Kocher et al. introduced ? Timing attacks (CRYPTO ¡¯96) ? Differential Power analysis (CRYPTO ¡¯99) ? Differential fault analysis (Eurocrypt ¡¯97) ? induce a fault and ¡°see what happens¡± ? a.k.a. micro-wave attack ? Sound of computer while computing RSA ? Van Eck phreaking : ? eavesdropping on screen output displayed on a CRT or LCD monitor by measuring electromagnetic emissions ? emissions from keyboard Brief History of Side Channel Attacks 208
- 209. ???????????? ??? ?? ??? ?? Power Attack Data input Data output Terminal IC chip Power supply 0111011011111 0111011101110 1111000001 Measure power consumption Guess secret information stored on IC chip memory 209
- 210. ???????????? ??? ?? ??? ?? Power Attack Can sample voltage differences at around 1GHz with less than 1% error. It also transfers Data to a PC. Cost around $400. Courtesy: Side-Channel Analysis Lab, 210
- 211. ???????????? ??? ?? ??? ?? ? Simple Power Attack (SPA) ? Makes use of characteristics that are directly visible in a single measurement trace ? Differential Power Attack (DPA) ? Looks for side channel differences that are NOT directly visible in one measurement trace ? Statistical methods have to be applied ? Divide-and-conquer tactics: finding small pieces of the key at a time ? Harder to prevent ? DPA = SPA + Statistical Analysis SPA vs. DPA 211
- 212. ???????????? ??? ?? ??? ?? SPA on PIN for i = 0 to 2 if (INPUT[i] ¡Ù PWD[i]) return(¡°REJECT¡±) return(¡°ACCEPT¡±) 212
- 213. ???????????? ??? ?? ??? ?? SPA on PIN 3 1 2 PWD 3 1 0 INPUT 3 1 1 INPUT 3 1 2 INPUT 1 0 0 INPUT 2 0 0 INPUT 3 0 0 INPUT 0 0 0 INPUT 3 1 0 INPUT 3 0 0 INPUT 213
- 214. ???????????? ??? ?? ??? ?? SPA on RSA z = 1 for i = k-1 downto 0 { z = z2 mod n if ei = 1 then z = z ¡Á m mod n } return (z) me = m(e3 e2 e1 e0) mod n 214
- 215. ???????????? ??? ?? ??? ?? SPA on RSA 310 = 3(1 0 1 0) mod 15 3 1 12¡Á3 mod 15 = 3 2 0 32 mod 15 = 9 1 1 92¡Á3 mod 15 = 3 0 0 32 mod 15 = 9 i ei z 215
- 216. ???????????? ??? ?? ??? ?? SPA on RSA Test key value : 0F 00 F0 00 FF 00 216
- 217. ???????????? ??? ?? ??? ?? Hack 4096-bit RSA Keys via CPU Sound 217
- 218. ???????????? ??? ?? ??? ?? Hack 4096-bit RSA Keys via CPU Sound 218
- 219. ???????????? ??? ?? ??? ?? ?? ?? (Quantum-Safe Security) 219
- 220. ???????????? ??? ?? ??? ?? ? 1982? ??? ?????? ??? ?? ?? ?? ?? ?? ? 1985? ?? ???????? ???? ???? ?? ? ??? ??? ??? ? 1994? ????? ?? ??(Peter Shor) ? ??? ??? ??????(??? ? ? ????? ????)? ??? ? 1997? IBM? ??? ??? 2?? ?? ???? ?? ?? ?? ??? (Quantum Computer) 220
- 221. ???????????? ??? ?? ??? ?? ? ?? ??? ?? ??? ??? ?? ??? ?? ??? ????, ??? ???? ?? ?? ???? ?? ??. ? ???? ??? ?? ???? ?? ??? ??? ?? ??? ???? ??, ???? ? ??? ?? ???. ?????? ??? ?? ¡°????¡±? ¡°????¡±? ??? ?? ?. ? ???? (superposition) : ??? ??? ?? ?? ??? ?? ? ? ???? (entanglement) : ? ??? ??? ? ??? ???? ??? ??? ??? ???? 221 ?? ??? (Quantum Computer)
- 222. ???????????? ??? ?? ??? ?? ? ????? ?? ??? ???(qubit) ? ? ????? ????? ???? ?? ? 0? 1, 2?? ??? ??? ?? ? ? ?. ?? ???? ??? 2?? ???? 4?? ?? 00, 01, 10, 11? ??? ?? ? ? ??. ? ?, n?? ???? 2n??? ??? ???? ???, ?? ???? ?? ??? ?? ?? ??? ??? ??? ???? ??? ? ? ? ?? ???. 222 ?? ??? (Quantum Computer)
- 223. ???????????? ??? ?? ??? ?? ? ?????? ??? ?????? ? 1994? ?? ??(Peter Shor)? (???) ? ??????? ???? ??(polynomial time) ????? ????? ???. ? 2001? IBM? ????? ? ????? (? ?) ?????? ???? 15 = 3 * 5? ?? ??? ??? ???. RSA? ????? ? 223
- 224. ???????????? ??? ?? ??? ?? ? ??? ??? ??? ?? ?? 400 ?? ?? ?? ?? ??? ???? ???? ? ?????, ??? ?? ?????? ? 1?? ???? ??? ??. ? ??? N? ?? ??? ??? ? O((log N)3) ? ??? O(log N)? ????? ???. 224 RSA? ?????
- 225. ???????????? ??? ?? ??? ?? RSA? ????? 225
- 226. ???????????? ??? ?? ??? ?? ? ?? ???(quantum computer)? ?? ? ???? ?? ? ?? ?? ??? ?? ?? ????? 226
- 227. ???????????? ??? ?? ??? ?? ? ???? ??? ?? ?? ??, QKD(Quantum Key Distribution, ????? ??) ? SKT, KT ? ? ????? ??? PQC(Post-Quantum Cryptography, ??????) ? LGU+ ? ?? ?? ??? ?? 227
- 228. ???????????? ??? ?? ??? ?? ?? ?? ??? ?? 228
- 229. ???????????? ??? ?? ??? ?? 229
- 230. ???????????? ??? ?? ??? ?? (Source: https://amhoin.blog.me/222076260058) 230
- 231. ???????????? ??? ?? ??? ?? ? In 1967 David Kahn published The Codebreakers ¡ª The Story of Secret Writing. ? A monumental history of cryptography. ? NSA attempted to suppress its publication. To Learn More 231
- 232. ???????????? ??? ?? ??? ?? ? Established 1982 by David Chaum, Ron Rivest, and others, to promote academic research in cryptology. ? Sponsors three major conferences/year (Crypto, Eurocrypt, Asiacrypt) and four workshops; about 200 papers/year, plus another 600/year posted on web. ? Publishes J. Cryptography ? Around 1600 members, (25% students), from 74 countries, 27 Fellows. To Learn More 232
- 233. ???????????? ??? ?? ??? ?? ? ?2021 by Seungjoo Gabriel Kim. Permission to make digital or hard copies of part or all of this material is currently granted without fee provided that copies are made only for personal or classroom use, are not distributed for profit or commercial advantage, and that new copies bear this notice and the full citation. 233
- 234. ???????????? ??? ?? ??? ?? 234 ????? ??? ??, ???