将来の暗号技術に関する安全性要件調査報告書

Size: px

Start display at page:

Download "将来の暗号技術に関する安全性要件調査報告書"

みひなののした
5 years ago
Views:

1 i

2 DES... 4 DES Cracker (1998 ) Lenstra & Verheul Silverman GDP GDP ii

3 DES MPU URL A A A A A B B B C iii

4 1015 CRYPTREC Cryptography Research & Evaluation Committees 2000 (IPA) (TAO)

5 2

6 DNA [1] GDP 3

7 DES DES DES Challenge[2]RSA Security DES DES [3] CBC DES [11] P112, [4] DES 1 DES DES DES Cracker (1998 ) DES Cracker DES Electronic Frontier Foundation (EFF) DES [6] Cryptography Research Advanced Wireless Technologies [7] 4

8 DES Cracker DES DES Cracker DES 56 4 DES [5] DES Cracker DES Cracker DES CMOS 0.8m 40 MHz 24 ECB CBC [6][8] DES 16 40M/162.5 M / 60M / VME DES Cracker 2 DES Cracker = M 12 2 = / DES Cracker K / DES Cracker MHz, 210nm M / M 4M/24166K 5

9 Lenstra & Verheul1999 A. K. Lenstra E. R. Verheul [9] 1. Life span 2. Security margin 3. Computing environment 4. Cryptanalysis (a) Life span x x (b) Security margin DES y DES y y 1982 y = DES FIPS DES 5 6

10 (c) Computing environment Moore IC (d) Cryptanalysis DES x y DES - z = x y x y 12 z 2 z = z 2 DES 2 1 z+ z = 2 23 z 23 z DES z DES

11 Lenstra & Verheul Symmetric Classical Subgroup Elliptic Curve Infeasible Lower bound Corresponding Key Size Asymmetric Discrete Key Size number of for Hardware number of Key Size (and Logarithm progress Mips Years cost in US $ for years on SDL Field Key Size no yes a 1 day attack 450MHz Year Size) (cf. (4.5)) PentiumII PC * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

12 Symmetric Classical Subgroup Elliptic Curve Infeasible Lower bound Corresponding Key Size Asymmetric Discrete Key Size number of for Hardware number of Key Size (and Logarithm progress Mips Years cost in US $ for years on SDL Field Key Size no yes a 1 day attack 450MHz Year Size) (cf. (4.5)) PentiumII PC * * * * * * * * * * * * * * * * * * * * * * * * * * Arjen K. Lenstra, Eric R. Verheul, "Selecting Cryptographic Key Sizes", Lenstra-Verheul DES DES Lenstra-Verheul 450MHz Pentium IIPC DES 1200 Pentium II ,000,000 DES 1MMYMillion MIPS Year Lenstra-Verheul 9

13 Lenstra Verheul Lenstra-Verheul NESSIE 1 [10] RSA R.D.Silverman [12] ECOM WG 2 [11] 5 - DES DES Moore 10

14 Moore

15 Silverman2000 R.D.Silverman RSA Lenstra-Verheul [12] Lenstra-Verheul RSA 20 RSA Silverman RSA Silverman [13] embarassingly parallel DES PC DES Cracker DES DES Lenstra-Verheul Lenstra-Verheul 12

16 (1) (2) 13

17 ASCII DES Cracker DES Cracker 8 [6] 69 69/2561/4 8 1/65536(l/4 8 ) 8 14

18 embarassingly parallel embarassingly parallel N N N 15

19 N N N DES DES Cracker 1020 ( 20 16

20 N N GDP 4% 17

21 CPU CPU 50 5,000.comhttp:// CPU CPU [14]

22 I S P u c I / S ) P = I ( P / S ) ( c u u c u u P / u S u I c Camellia [15] [16] u 19

23 DES K, Camellia 128 6,367 4,979 11, , Camellia 128 Feistel SPN R 1 1 R 1 R R 20

24 16 DESCASTCamellia AESRijndael f R f / R I / S ( I / S) f / R C P / C = ( I / S)( f / R) / C AES 21

25 5-5 I f S 50K R C CPU Lenstra-Verheul

26 GDP 4% 4 GDP GDP 23

27 GDP GDP 10,416,818 US [19] GDP GDP 2002 GDP [17] GDP 32,252,480 US GDP 24

28 5-9 Lenstra-Verheul

30 = 2 ) / ( log 2 ) / ( log 2 = 27

31 Lenstra-Verheul

32 7 29

33 MPU Unix /etc/passwd [20] [21] 2 [21] b 2 b N 2 = N 30

34 N 2 n = 2N 1 64 n = G 64 48GB 128 n E 350 EB AESCamellia N n = 2N 1 n N = 2 1 n 1 b n = 2N b b / 2 31

35 DES DES 7-1 Lenstra-Verheul 2003 DES Cracker 32

36 DES Cracker MPU MPU PC DES MMYLenstra-Verheul [9] MMY Million MIPS Year1MIPS MMY / 2 56 = Pentium 500 / 438 / MPU FLOPS MIPS 33

37 MPU FLOPS MIPS FLOPS 7-2 CPU MPU - CPU 3000 MPU 1 ~ CPU

38 / 10 / - 2 MPU - 5 PC - MPU 10 1U MPU MPU MPU - /MPU 10 MPU MPU 2005 BlueGene/L 1 BlueGene/L 35

39 PC PC 10 PC PC PC 10W 1kWh 9 B2 kwh 1 36

40 ( [22] W 200 kw 1 [1] [27] [23][24][25] Shor [26] 37

41 Shor RSA 1 1 Moore 38

42 URL [1], [2] "Cryptographic Challenges", RSA Security, [3] DATA ENCRYPTION STANDARD (DES), FIPS PUB 46-3, [4] Project DES, distributed.net, [5] "RSA's DES Challenge III is solved in record time", RSA Security, [6] EFF (Electronic Frontier Foundation), "Cracking DES" (Jan 1999), DES, [7] Record-Breaking DES Key Search Completed, [8] John R T Brazier, Possible NSA Decryption Capabilities, [9] Arjen K. Lenstra, Eric R. Verheul, "Selecting Cryptographic Key Sizes", Journal of Cryptology (1999, 2001), [10] B. Preneel, et al., "Security Evaluation of NESSIE First Phase" (September 2001), [11] ECOM WG [12] R.D.Silverman (RSA), "A Cost Based Security Analysis of Symmetric and Asymmetric Key Lengths" (Apr 2000), [13] A.Shamir, E.Tromer, "Factoring Large Numbers with the TWIRL Device (preliminary draft)" (Jan 2003). [14] Semiconductor Industry Association (SIA), eds., "International Technology Roadmap for Semiconductors (ITRS) 2002 Update", [15] Camellia, [16], Camellia 128, [17] World Bank, "Total GDP 2002", [18] US Department of Defense, "National Defense Budget Estimates for FY2004", 39

43 [19] [20], [21],, Triple DES, IMES Discussion Paper Series 99-J-6, (1999), [22] (, [23], (2000), puters/. [24] (2003), [25] Centre for Quantum Computation, [26] P. W. Shor, Algorithms for quantum computation: discrete log and factoring, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, S. Goldwasser (editor), IEEE Computer Society Press, Los Alamitos, 1994, pp [27], [28] The International Technology Roadmap for Semiconductors web site, [29] Intel, ZDNet 2003/12/3, [30] David Klepacki (IBM T. J. Watson Research Center), "Blue Gene Towards Petascale Computing" (April 2003), p9, [31], p 13, [32] Slides concerning TOP500 06/2002, [33] The Advanced Simulation and Computing Program (ASCI), [34] Networking and Information Technology Research and Development Supplement to the President s Budget FY2003 (Bluebook 2003),

44 A A.1 40 minimum feature 18 International Technology Roadmap for Semiconductors, ITRS[28] 15 A.2 Semiconductor Industry Association, SIA 1992 National Technology Roadmap for Semiconductors, NTRS ITRS

45 A MPU 1/2 A-1 A GHz GHz Moore A.4 Intel [29] LSI3 CMOS 42

47 B B.1 B-1 B-2 44

48 B GFLOPS TFLOPS TOP LINPACK TPP GFLOPSCM-5 36TFLOPS

49 CPU 1990 Intel Touchstone DeltaCPU 512 CM-5CPU 1024 NWT CPU 140 CPU ASCI Red CPU MPU CPU 1 10MFLOPS 100MFLOPS CPU ,000 B CPU ASCI [33] Bluebook

50 1 ([34] p17) 4 1. ASCI 2. PC 3. BlueGene/LIBM DNA (1)(3) (4)

51 C s s 10 Lenstra-Verheul C-1 48

52 Lenstra-Verheul p 0 t 0 p(t) p( t) = p0e at t x(t) 0 x( t) p( t) x( t ) t 1 c t1 t = 0 t x( t) dt = c t 1 1 t = 0 u= t x( t) p( t) dudt 1 x(t) : t u = t f ( t) = 1 p( t) du t p( t) = p0e at 49

53 f t) = p ( t t) e f ( 0 1 at at at { a( t t) e e } = p ( at at 1) e 0 at ( t) = p = t = ( at 1) 1 / a t Lenstra-Verheul log2 2t /3 2log 2 = ( e ) a = = at t /1.5 e 2 = 10 t = 10 1 t t = ( at1 1) / a = ( ) / = f ( t) = p p at 0 ( t1 t) e = t y (t) g (t) y( t) / g( t) c t p ( t) y( t) = p( t) g( t) x( t) 50

54 t1 t = t t = 0 u= t y( t) / g( t) dt = c t y( t) p( t) dudt X ( t) = y( t) / g( t), P( t) = g( t) p( t) t1 t = X ( t) dt = c t t t = 0 u= t X ( t) P( t) dudt Lenstra-Verheul 10 2 at t /1.5 t /10 e = 2 2 = log 2 ( e ) 23t / 30 23log 2 a = 30 = t t = ( at1 1) / a = ( ) / = f ( t) = p ( ) p at 0 t1 t e = Lenstra-Verheul

楕円曲線暗号と RSA 暗号の安全性比較

楕円曲線暗号と RSA 暗号の安全性比較 RSA, RSA RSA 7 NIST SP-7 Neal Koblitz Victor Miller ECDLP (Elliptic Curve Discrete Logarithm Problem) RSA Blu-ray AACS (Advanced Access Control System) DTCP (Digital Transmission Content Protection) RSA