Luận án Nghiên cứu một số giải pháp nâng cao hiệu năng của thuật toán mã hóa

Nội dung text: Luận án Nghiên cứu một số giải pháp nâng cao hiệu năng của thuật toán mã hóa

1. 99 [44] Junod P. and Vaudenay S., Perfect diffusion primitives for block cipher - Building efficient MDS matrices in Selected Areas in Cryptology (SAC 2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004. [45] J.Daemen, V.Rijmen, “AES Proposal: Rijndael”, in Proceedings of the First Advanced Encryption Standard Candidate Conference, NIST, 1998. [46] Kishan Chand Gupta and Indranil Ghosh Ray, On Constructions of MDS Matrices From Circulant-Like Matrices For Lightweight Cryptography, Technical Report No. ASU/2014/1, Dated : 14th February, 2014. [47] K. Lauter,D. Charles, “Computing modular polynomials”, Journal of Computational Mathematics, pp. 195-204, 2005. [48] Koblitz (1987) N., “Elliptic curve cryptosystem”, Math.Comp, 48 (16), pp. 203- 209. [49] Kutyłowski M, Strothmann WB, Lý thuyết mật mã và thực hành đảm bảo an toàn các hệ thống máy tính, Nhà xuất bản Read Me, Warsawa 1998. [50] Lawrence C. Washington (2008), “Elliptic Curves-Number theory and Cryptography”, CRC Press. [51] Lorenzo Grassi, “MixColumns Properties and Attacks on (round-reduced) AES with a Single Secret S-Box”, 2017. [52] L.Brown, M Kwan, J Pieprzyk, J Seberry, " Improving Resistance to Differential Cryptanalysis and the Redesign of LOKI", Advances in Cryptology - Asiacrypt'91, Lecture Notes in Computer Science, vol 739, Springer-Verlag, 1993 [53] L.Saadi, “Stealth Ciphers”, Trafford Pub, 2004. [54] M. Kutyłowski, WB. Strothmann, Lý thuyết mật mã và thực hành đảm bảo an toàn các hệ thống máy tính, Nhà xuất bản Read Me, Warsawa 1998. [55] Maurer U. M., Wolf S., “Diffie-Hellman Oracles”, Lecture Notes in Computer Science, CRYPTO ’96, vol.1109, str.268-282, Springer- Verlag, 1996.
2. 101 [68] Muhammad Reza Z’aba. “Analysis of linear relationships in block ciphers”. PhD thesis, Queensland University of Technology. 2010.256p. [69] Muzereau A., Smart N. P., Vrecauteren F., “The equivalence between the DHP and DLP for elliptic curves used in practical applications”, LMS J. Comput. Math., vol. 7(2004), str. 50-72, 2004. [70] Mustafa Khairallah, Anupam Chattopadhyay, and Thomas Peyrin, “Looting the LUTs : FPGA Optimization of AES and AES-like Ciphers for Authenticated Encryption”, 2017. [71] Pollard J., “Monte Carlo methods for index computation mod p”, Mathematics of Computation, pp.918-924, 1978. [72] P.Barrett, “Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor”, in Proceedings of Advanced in Cryptography-CRYPTO’86, Springer- Verlag, 1987. [73] P.Junod and S. Vaudenay, “Perfect diffusion primitives for block cipher - Building efficient MDS matrices in Selected Areas in Cryptology” (SAC 2004), LNCS 3357, pp. 84-99, Springer-Verlag, 2004. [74] P.Campbell, B.Calvert, S.Boswell, “Security+ In Depth”, Course Technology PTR, 2003 [75] P. Montgomery, “Modular Multiplication Without Trial Division”, Mathematics of Computation, vol. 44, str. 519-521,1985. [76] Riddhi Ghosal, “Analysing Relations involving small number of Monomials in AES S- Box”, 2017. [77] R. Rivest, A. Shamir, L. Adleman,. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, Vol. 21 (2), 1978.
3. 103 [89] Smart N., “The discrete logarithm problem on elliptic curves of trace one”, J. Crypto., vol. 12, str. 193-196, 1999. [90] Swankoski E., Brooks R., Vijaykrishnan N., Kandemir M., Irwin M. J., “A Parallel Architecture for Secure FPGA Symmetric Encryption”, in Proceedings of the 11th Reconfigurable Architectures Workshop(RAW'04). [91] Takahashi D., Kanada Y., “High-performance radix-2, 3 and 5 parallel 1- D complex FFT algorithms for distributed-memory parallel computers”, Journal of Supercomputing, vol. 15, str. 207-228, 2000. [92] Xiongwei Fei, Kenli Li, Wangdong Yang, Keqin Li, “Practical parallel AES algorithms on cloud for massive users and their performance evaluation",.2012 [93] Van der Hoeven J., “The truncated Fourier transform and applications”, in: ISSAC 2004, ACM, str. 290-296, 2004. [94] Van der Hoeven J., “Notes on the truncated Fourier transform”, unpublished, retrieved from ˜vdhoeven/, 2005. [95] W.Diffie and MEHellman, “New directions in cryptography”, IEEE Transactions on Information Theory, IT-22, 6, 1976. [96] W. O. Chan, Cryptanalysis of SIGABA, Master’s Thesis, Department of Computer Science, San Jose State University, May 2007. [97] Wu, Shengbao, Mingsheng Wang, and Wenling Wu. “Recursive diffusion layers for (lightweight) block ciphers and hash functions”. Selected Areas in Cryptography p.355-371.Springer Berlin Heidelberg, (2013). [98] Zhou Lijing, Licheng Wang, Yiru Sun (2018) "On Efficient Constructions of Lightweight MDS Matrices". IACR Transactions on Symmetric Cryptology, 2018 (1), 180-200.
4. P2 Phụ lục 1. THƯ VIỆN MODULE NHÂN NHANH ĐA THỨC Biên dịch thư viện Phụ lục 2 chứa mã nguồn của thư viện để nhân nhanh đa thức với hệ số là các số nguyên không âm. Triển khai này được chuẩn bị dựa trên chuẩn ngôn ngữ ANSI C và phần mở rộng OpenMP Mã thư viện gồm các tệp có chứa các bản khai cần thiết và thực hiện thuật toán nhân. - uintpoly.h: tệp tiêu đề chính có chứa giao diện bậc cao đến các hàm hoạt động trên đa thức. - uintpoly.c: tệp chứa việc thực hiện các hàm cơ bản hoạt động trên các đa thức (chiếm và giải phóng bộ nhớ, so sánh, hiển thị và nhân theo phương pháp phổ thông). - arth.c: tệp chứa việc thực hiện các phép tính số học (cộng, nhân, rút gọn module) và các hàm khởi tạo cố định cho thuật toán Garner (CRT). - dft fp32.c: tệp chứa việc thực hiện hàm tạo ra dữ liệu cần thiết để thực hiện biến đổi Fourier (DFT). - dft fp32 crt.c: tệp chứa việc thực hiện thuật toán nhân nhanh, song song các đa thức. Chuẩn bị thực hiện sử dụng các Directive OpenMP và thực hiện tính toán trên bộ vi xử lý đa nhân. Sử dụng thư viện Đoạn mã sau cho thấy cách sử dụng các hàm của thư viện. Bậc tối đa được chấp nhận bởi phiên bản của thư viện này là 222- 1. #include "uintpoly.h" main(int argc, char *argv[]) { clock_t start1, end1, start2, end2; double cpu_time_used1, cpu_time_used2;
5. P4 */ start1 = clock(); UINT_Poly_mul(&c, &a, &b); end1 = clock(); cpu_time_used1 = ((double)(end1 - start1)/CLOCKS_PER_SEC ); /* * Thực hiện phép nhân bằng phương pháp FFT + CRT ghi tích của chúng là * đa thức d. */ start2 = clock(); UINT_Poly_dft_crt_mul(&d, &a, &b); end2 = clock(); cpu_time_used2 = ((double)(end2 - start2) / CLOCKS_PER_SEC); /* * In các thừa số và thương số tính được dựa vào hai thuật toán * (Các đa thức c i d đồng nhất với độ chính xác * đến các số 0 trong hệ số. */ printf("a = \n"); UINT_Poly_print(&a); printf("b = \n"); UINT_Poly_print(&b); printf("c = \n"); UINT_Poly_print(&c); printf("d = \n"); UINT_Poly_print(&d); printf("conventional method took %f seconds to execute \n", cpu_time_used1); printf("conventional method start at %u clk \n", start1);
6. P6 Phụ lục 2. MÃ NGUỒN CỦA THƯ VIỆN NHÂN NHANH ĐA THỨC file uintpoly.c: Những phép tính cơ bản trên đa thức IntUINT_Poly_init(UINT_Poly * a) { memset(a, 0, sizeof(UINT_Poly)); a->deg = -1; return 0;} IntUINT_Poly_init_mem(UINT_Poly * a, int digits, int deg) { int i; a->digits = digits; a->deg = deg; if ((a->v = calloc(a->deg + 1, sizeof(uint32_t *))) == 0) { return -1; } memset(a->v, 0, (a->deg + 1) * sizeof(uint32_t)); for (i = 0; i v[i] = calloc(a->digits, sizeof(uint32_t))) == 0) { UINT_Poly_clear(a); return -1; } memset(a->v[i], 0, a->digits * sizeof(uint32_t)); } return 0;} IntUINT_Poly_init_coef(UINT_Poly * a, const uint32_t * coef, int digits, int deg) { if (a->deg digits v[deg], 0, a->digits * sizeof(uint32_t)); memcpy(a->v[deg], coef, digits * sizeof(uint32_t)); return 0;} IntUINT_Poly_clear(UINT_Poly * a) { int i;
7. P8 if (ARTH_cmp_digit(a->v[i], 0, a->digits) != 0) { return 0;}}} return 1;} intUINT_Poly_mul(UINT_Poly * c, const UINT_Poly * a, const UINT_Poly * b) { UINT_Poly t; uint32_t *d; int i, j; /* Phân bổ bộ nhớ cho kết quả. */ UINT_Poly_init_mem(&t, a->digits + b->digits + 1, a->deg + b->deg); d = calloc(t.digits - 1, sizeof(uint32_t)); /* Phép nhân. */ for (i = 0; i deg; i++) { for (j = 0; j deg; j++) { ARTH_mul(d, a->v[i], a->digits, b->v[j], b->digits); t.v[i + j][t.digits - 1] += ARTH_add(t.v[i + j], d, t.digits - 1);}} /* Ghi kết quả. */ UINT_Poly_clear(c); c->v = t.v; c->digits = t.digits; c->deg = t.deg; free(d); return 0;} intUINT_Poly_print(const UINT_Poly * a) { int i, j; for (i = 0; i deg; i++) { printf("[%d] ", i); for (j = a->digits - 1; j > -1; j ) { printf(":%08x", a->v[i][j]);}
8. P10 if (i & prec) { di |= rprec;} rprec n = 1; while (1) { /* Quá ít nghiệm. */ if (((dft->n & (p - 1)) == 1) && (dft->n n) { break;} dft->n roots = dft->n / 2; /* Tính hệ số q để nhân theo phương pháp Montgomery. */ q = 1; while (p * q != 1) { q = q * (2 - p * q);} q = -q; /* t1 = t2 = 2^32 % p. */ t1 = (uint32_t)(0x0100000000ULL % p); t2 = t1; /* s = 2^64 % p. */
9. P12 free(dft->ir);} return 0;} file dft fp32 crt.c: thuật toán nhân nhanh /* 32-Số nguyên tố 32bit dạng b*2^22 + 1. */ static const uint32_t p32[56] = { 513 * 0x400000U + 1, 517 * 0x400000U + 1, 544 * 0x400000U + 1, 553 * 0x400000U + 1, 559 * 0x400000U + 1, 565 * 0x400000U + 1, 573 * 0x400000U + 1, 589 * 0x400000U + 1, 592 * 0x400000U + 1, 604 * 0x400000U + 1, 610 * 0x400000U + 1, 627 * 0x400000U + 1, 628 * 0x400000U + 1, 637 * 0x400000U + 1, 639 * 0x400000U + 1, 645 * 0x400000U + 1, 648 * 0x400000U + 1, 649 * 0x400000U + 1, 655 * 0x400000U + 1, 663 * 0x400000U + 1, 669 * 0x400000U + 1, 670 * 0x400000U + 1, 684 * 0x400000U + 1, 688 * 0x400000U + 1, 694 * 0x400000U + 1, 714 * 0x400000U + 1, 715 * 0x400000U + 1, 733 * 0x400000U + 1, 742 * 0x400000U + 1, 757 * 0x400000U + 1, 765 * 0x400000U + 1, 768 * 0x400000U + 1, 772 * 0x400000U + 1, 790 * 0x400000U + 1, 814 * 0x400000U + 1, 819 * 0x400000U + 1, 823 * 0x400000U + 1, 832 * 0x400000U + 1, 837 * 0x400000U + 1, 847 * 0x400000U + 1, 853 * 0x400000U + 1, 859 * 0x400000U + 1, 862 * 0x400000U + 1, 865 * 0x400000U + 1, 874 * 0x400000U + 1, 879 * 0x400000U + 1, 894 * 0x400000U + 1, 915 * 0x400000U + 1, 928 * 0x400000U + 1, 939 * 0x400000U + 1, 940 * 0x400000U + 1, 957 * 0x400000U + 1, 972 * 0x400000U + 1, 979 * 0x400000U + 1, 1000 * 0x400000U + 1, 1014 * 0x400000U + 1 }; /* Nghiệm nguyên thủy giành cho số nguyên tố theo bảng p32. */ static const uint32_t p32_r[56] = { 7, 6, 3, 3, 3, 3, 5, 3, 3, 3, 3, 13, 3, 3, 7, 11, 5, 3, 6, 10, 15, 11, 35, 3, 3, 10, 3, 3, 3, 3, 13, 5, 3, 6, 3, 10, 3, 3, 41, 3, 3, 3, 3, 3, 3, 5, 5, 31, 3, 10, 3, 19, 7, 3, 3, 5};
10. P14 t3 = (t1 >> 32) + (t2 >> 32); if ((uint32_t)t1 != 0) { t3 += 1; } if ((uint64_t)p <= t3) { t3 -= (uint64_t)p;} return (uint32_t)t3;} static intdft_size_for_poly(int deg) { int size = 2; while (size < deg + 1) { size *= 2;} return size;} intUINT_Poly_dft_crt_init(int deg_max) { int i, j; dft_size = dft_size_for_poly(deg_max + 1); if (ARTH_Fp32_crt_init(&crt, p32, 56) < 0) { return -1; } for (i = 0; i < 56; i++) { if (ARTH_Fp32_dft_init(dft + i, dft_size, p32[i], p32_r[i]) < 0) { for (j = 0; j < i; j++) { ARTH_Fp32_dft_free(dft + j); } ARTH_Fp32_crt_free(&crt); return -1;}} return 0;} intUINT_Poly_dft_crt_finish() { int i; dft_size = 0; for (i = 0; i < 56; i++) { ARTH_Fp32_dft_free(dft + i); }
11. P16 private(pa, pb, ha, la, hb, lb, p, q, r, ir, s, t, i2e, m, bs, i, j, k) for (i = 0; i deg; j++) { pa[j] = mont_mul(ARTH_mod_digit(a->v[j], a->digits, p), s, p, q);} for (j = 0; j deg; j++) { pb[j] = mont_mul(ARTH_mod_digit(b->v[j], b->digits, p), s, p, q);} /* (2) FFT. */ m = n; while (m != 1) { bs = n / m; m /= 2; for (j = 0; j < bs; j++) { r = dft[i].r[j]; la = pa + 2 * j * m; ha = la + m; lb = pb + 2 * j * m; hb = lb + m; for (k = 0; k < m; k++, la++, ha++, lb++, hb++) { t = mont_mul(*ha, r, p, q); *ha = mont_sub(*la, t, p); *la = mont_add(*la, t, p);
12. P18 #pragma omp parallel for default(none) shared(dft, crt, a, b, c, dft_a, dft_b, deg_c, primes, n) \ private(pa, pb, ha, la, hb, lb, p, q, r, ir, s, t, i2e, m, bs, i, j, k) for (i = 0; i digits = 1; for (i = 0; i digits digits = j + 1;}}} /* Copy kết quả. */ c->deg = deg_c; c->v = calloc(c->deg + 1, sizeof(uint32_t *)); for (i = 0; i v[i] = calloc(c->digits, sizeof(uint32_t)); pb = dft_b + i * primes;
13. P20 if (op1[i] op2[i]) { return -1;}} if (len1 0; i ) { if (op1[i] != 0) { return -1;}} if (op1[0] op2) { return -1;} return 0;} intARTH_add(uint32_t * dst, const uint32_t * src, int len) { uint32_t c = 0; int i; for (i = 0; i < len; i++) { ARTH_ADC(dst[i], dst[i], src[i], c);} return (int)c;} intARTH_add_digit(uint32_t * dst, uint32_t src, int len) { uint32_t c = 0;
14. P22 for (i = 0; i n = n; /* Alokacja pamięci. */ if ((crt->p = calloc(crt->n, sizeof(uint32_t))) == 0) { return -1;} if ((crt->c = calloc(crt->n, sizeof(uint32_t))) == 0) { free(crt->p); return -1;} if ((crt->pp = calloc(crt->n * crt->n, sizeof(uint32_t))) == 0) { free(crt->p); free(crt->c); return -1;} /* Copy số nguyên tố. */ for (i = 0; i p[i] = p[i]; }
15. P24 Phụ lục 3. MODULE CHƯƠNG TRÌNH TRAO ĐỔI KHÓA #include #include "FiniteFieldElement.hpp" #include "sha256.hpp" #include "rijndael.h" namespace Cryptography { template class EllipticCurve { public: typedef FiniteFieldElement ffe_t; class Point { friend class EllipticCurve ; typedef FiniteFieldElement ffe_t; ffe_t x_; ffe_t y_; EllipticCurve *ec_; void addDouble(int m, Point& acc) { if ( m > 0 ) { Point r = acc; for ( int n=0; n < m; ++n ) { r += r; // doubling step } acc = r; } } Point scalarMultiply(int k, const Point& a) {
16. P26 { s = (3*(x1.i()*x1.i()) + ec_->a()) / (2*y1); xR = ((s*s) - 2*x1); } else { //P+Q s = (y1 - y2) / (x1 - x2); xR = ((s*s) - x1 - x2); } if ( s != 0 ) { yR = (-y1 + s*(x1 - xR)); } else { xR = yR = 0; } } Point(int x, int y) : x_(x), y_(y), ec_(0) {} Point(int x, int y, EllipticCurve & EllipticCurve): x_(x), y_(y), ec_(&EllipticCurve) {} Point(const ffe_t& x, const ffe_t& y, EllipticCurve & EllipticCurve) : x_(x),y_(y), ec_(&EllipticCurve) {} public: static Point ONE; Point(const Point& rhs) {x_ = rhs.x_; y_ = rhs.y_; ec_ = rhs.ec_;} Point& operator=(const Point& rhs) {x_ = rhs.x_; y_ = rhs.y_; ec_ = rhs.ec_; return *this; } ffe_t x() const { return x_; }
17. P28 EllipticCurve(int a, int b) : a_(a), b_(b), m_table_(), void CalculatePoints() { int x_val[P]; int y_val[P]; for ( int n = 0; n a() const { return a_; } // the paramter b (as an element of Fp) FiniteFieldElement b() const { return b_; }
18. P30 for ( ; iter!=m_table_.end(); ++iter ) { os columns ) { os rk[256/8 + 28] = rk[60] := 60 phan tu unsigned char key[KEYLENGTH(KEYBITS)] = {0x60,0x3d,0xeb,0x10,0x15,0xca,0x71,0xbe,0x2b,0x73,0xAE,0xF0,0x85,0x7d,0x7 7,0x81,0x1F,0x35,0x2C,0x07,0x3B,0x61,0x08,0xD7,0x2D,0x98,0x10,0xA3,0x09, 0x14,0xDF,0xF4}; //0x2E unsigned char plaintext[16]; unsigned char ciphertext[16]= {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; unsigned char IV_InputE[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F}; unsigned char IV_InputD[16] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F}; unsigned char IV_Output[16]; int nrounds; char iv_count=0;
19. P32 // Calculate the Public key = Base point * random number int Private_key[N]; ec_t::Point Public_key[N]=G; for (int n=0; n 0 ; l1 ) { Public_key[l1] = Private_key[l1] * Public_key[l1-1]; } Public_key[0] = Private_key[0]*temp_point; /* xem qua trinh thoa thuan khoa*/ for (int n=0; n<=N; n++) { cout << "Public_key_" << n <<" = " << Public_key[n] << endl; } cout << endl; } std::stringstream sstr; sstr << Public_key[0].x(); std::string str1 = sstr.str(); string output1 = sha256(str1); // cout << output1 << endl;
20. P34 fwrite(ciphertext,16,1,f_out); } else { AES_OFB(rk,nrounds,IV_Output,IV_InputE,buffer,ciphertext); fwrite(ciphertext,16,1,f_out); } } fclose(f_in); fclose(f_out); cout > D; std::stringstream sstr2; sstr2 << Public_key[D].x(); str1 = sstr2.str(); output1 = sha256(str1); src = &output1[0]; dst = key; while (dst < end && sscanf(src,"%2x", &u) == 1) { *dst++ = u&0xff; src += 2; } for (int i=0;i<32;i++) {printf("%2.2x",key[i]); } nrounds = rijndaelSetupEncrypt(rk, key, KEYBITS); cout << endl; // Input image file f_in = fopen("encrypted.bin", "rb"); // Open the file in binary mode fseek(f_in, 0, SEEK_END); // Jump to the end of the file filelen = ftell(f_in); // Get the current byte offset in the file cryptlen = filelen / 16;