LÝ THUYẾT SỐ TRONG MẬT MÃ HIỆN ĐẠI

 

LÝ THUYẾT SỐ TRONG MẬT MÃ HIỆN ĐẠI

THE NUMBER THEORY IN THE MODERN CRYPTOGRAPHY

TS. Lê Phê Đô, Ths. Trần Văn Mạnh, Ths. Mai Mạnh Trừng, Ths. Lê Trung Thực, Lê Thị Len, Đỗ Công Thành, Nguyễn Văn Thắng

Khoa Công nghệ thông tin

Trường Đại học Công nghệ, ĐHQG Hà Nội

E-mail: dolp@vnu.edu.vn

tvmanhqn@gmail.com

Dcthanh9@gmail.com

phalebl@gmail.com

Thangnv_560@vnu.edu.vn

Thuclt12a@gmail.com

thaoltt@vnu.edu.vn

Thuanddk56cc@gmail.com

Mmtrung.uneti@moet.edu.vn

Tóm tắt

Ngày nay việc ứng dụng những dãy số giả ngẫu nhiên vào việc thiết kế khóa bí mật trong hệ thống mật mã đang được quan tâm. Trong báo cáo này, nhóm tác giả giới thiệu một số vấn đề  lý thuyết về việc xác định chu kỳ của dãy số giả ngẫu nhiên Blum Blum Shub và tiến hành thực nghiệm tính chu kỳ của dãy số giả ngẫu nhiên trên. Kết quả chỉ rằng, chu kỳ thực tế thấp hơn rất nhiều so với chu kỳ lý thuyết. Vì vậy trong thực tế ứng dụng phải tính đến yếu tố này.

Ngoài ra, báo cáo còn trình bày ứng dụng lý thuyết nhóm, phép mã hóa từ điển và các thụật toán tạo số giả ngẫu nhiên để tạo ra cách lưu trữ và truyền dữ liệu an toàn.

Abstract

 The application of psedorandom Numbers into designing private  keys in the cryptography system are  widely studied by many researchers.  In this report, authors would like to introduce some theoretical foundations on identifying the period of the pseudorandom number sequence Blum Blum Shub, and simultaneously to undertake the tests of the above period. The results illustrate that the period of the pseudorandom number sequence in the tests are lower than the period in the theory. Therefore, the practice must consider this difference.

In addition, the report also presents applications of group theory, and encryption algorithms dictionary pseudo-random number generator to create a storage and secure data transmission.

1.Giới thiệu

Việc nghiên cứu các dãy số giả ngẫu nhiên đang rất được quan tâm ở thế giới, nhưng ở Việt nam còn ít nhà nghiên cứu quan tâm và hầu như không có những kết quả đáng kể. Điều này dẫn đến nhiều sản phẩm về an toàn thông tin phù thuộc vào yếu tố nước ngoài, dẫn đến không làm chủ được về mặt công nghệ và không hoàn toàn tin cậy. Ví như những chương trình tạo dãy ngẫu nhiên có cửa hậu mà Edward Snowden đã công bố. Từ thực tế đó Nhóm chúng tôi mong muốn tạo ra được những thuật toán giả ngẫu nhiên được nội địa hóa và an toàn, tin cậy

2.  Các khái niệm và định lý cơ sở

2.1 Các khái niệm

Ta nhắc lại một số khái niệm và ký hiệu về các tập hợp trong lý thuyết số như sau:

 ký hiệu một tập hữu hạn q phần tử ,  biểu diễn trường các số nguyên,  biểu diễn tập các số thực  và  biểu diễn tập các số phức. Cho một số thực  chúng ta xác định  và  như sau:    ⌊γ⌋  ≤ γ< ⌊γ⌋+ 1  và ⌈γ⌉- 1< γ ≤ ⌈γ⌉.

Ta sử dụng ký hiệu  để biểu diễn phần thập phân   =  - .

Cho một số nguyên  ta biểu diễn bởi  xác định vành đồng dư module m, tập các số nguyên k  ;  là tập con của  trong đó bao gồm các số nguyên k  với ước số chung lớn nhất .

Cho một số nguyên ,  biểu diễn số lượng các ước số nguyên dương của số nguyên m.  biểu thị hàm Euler của m,  ký hiệu số các ước nguyên tố của m.

Cho số nguyên , hàm Carmichael  được xác định là bậc lớn nhất có thể có của các phần tử trong một nhóm nhân của vành đồng dư theo modulo m. Rõ ràng hơn, ta có hàm Carmichael  cho các hệ số dạng :

Và cuối cùng , với m = ,  là phân tích thành tích của các thử  số nguyên tố của m.

2.2 Các định lý cơ sở

Cho , m, và e là các số nguyên sao cho  và . Định nghĩa dãy tuần tự ( bởi công thức truy toán:

Với giá trị khởi đầu  và số mũ e.

Dãy (2.2.1) được biết đến như là một máy sinh số giả ngẫu nhiên và có rất nhiều ứng dụng trong hệ mật mã.

 

Định lý 2.2.1. Cho bất kỳ số nguyên dương m và với mọi số , chúng ta gọi W biểu diễn số lượng cặp các số nguyên  với  và , nhờ đó mà chu kỳ sinh dãy ngẫu nhiên cho bởi (1) là . Khi đó

Về phần chứng minh cụ thệ định lý trên có thể xem chi tiết ở trang 250 của tài liệu [1].

Định lý 2.2 2. Cho Q là số đủ lớn và bất cứ  và , khẳng định sau cho tất cả các cặp , ngoại trừ hầu hết  của chúng (của cặp (p,l)). Cho tất cả các cặp  với

Với , ngoại trừ hầu hết  của chúng, chu kỳ t của dãy () cho bởi (2.2.1) thỏa mãn

Về phần chứng minh cụ thệ định lý trên có thể xem chi tiết ở trang 254 trong tài liệu [1].

3. Thuật toán xác định cận trên của chu kỳ dãy Blum Blum Shub

Dưới đây xin trình bày thuật toán dưới dạng giả mã tính cận trên của chu kỳ cho dãy (1) như sau với m = pl; k >= 1; k1, k2 >=1;

/*

            Thuật toán giả mã tính cần trên của chu kỳ dãy số được cho bởi (2.1.1);

*/

BigInteger getMostPeriod(BigInteger p, BigInteger l,

         BigInteger k, BigInteger k1, BigInteger k2) {

BigInteger result = BigInteger.ZERO;

            BigInteger lamdaM = BigInteger.ZERO;

            try {

                  BigInteger lamdaP = getLamda(p,k); // tính  theo (2.1.1);

                  BigInteger lamdaL = getLamda(l,k); // tính  theo (2.1.1);

                 lamdaM = getLcm(lamdaP, lamdaL); // tính giá trị ;

                 // Phân tích  lamdaM thành tích các thừa số nguyên tố

                 ArrayList primes = bigPrimeFactorization(lamdaM);

                 // Tính bội chung nhỏ nhất của các thừa số nguyên tố từ lamdaM

                  lamdaM = lcm(primes);            // đây chính là giá trị ;

                 result = lamdaM.divide(k1.multiply(k2)); // Tính giá trị

            } catch (Exception ex ) {

System.out.println(“Exc getMostPeriod() ”+ ex.getLocalizedMessage());

}

}

4. Thực nghiệm

4.1 Thực nghiệm tính chu kỳ

Để làm phần thực nghiệm này chúng tôi sử dụng môi trường và công cụ như sau để kiểm thử:

  • Môi trường thử nghiệm: Máy laptop HP 1000 với các thông số như sau:

-         Intel(R) Core ™ i5-3210M CPU @ 2.50GHz 2.50 GHz, 4.00 GB RAM.

-         Hệ điều hành Windows 64 bit (Win 8).

  • Công cụ và ngôn ngữ phát triển:

-         Chương trình sử dụng Java 2 Platform, Standard Edition (J2SE) của hãng Sun, JDK version 1.6 (J2SE Development Kit).

-         Sử dụng bộ công cụ phát triển Eclipse. Ngôn ngữ sử dụng Java, chương trình sử dụng gói dữ liệu chuẩn java.math.BigInteger của Java.

Dưới đây là kết quả thực nghiệm chạy sinh số giải ngẫu nhiên và tính toán chu kỳ của (2.2.1) với e = 2, m = pl theo thực tế chạy:

Bảng 4.1 Kết quả chạy với tính chu kỳ thực tế
Gia trị P Giá trị L Chu kỳ
101 127 60
19463 24851 165060
3523342351 3079833893 1065260

Dưới đây là kết quả tính chu kỳ của dãy (2.2.1) dựa trên định lý 2.2.1 với các P và L như ở trên. Với giả thiết m = pl, ;

Bảng 4.2 Kết quả chạy với tính chu kỳ lý thuyết
Gia trị P Giá trị L Chu kỳ
101 127 210
19463 24851 24181535
3523342351 3079833893 542565459132446310

Từ kết quả chạy tính chu kỳ theo thực tế và kết quả chạy tính cận trên của chu kỳ theo lý thuyết ta thây rằng giữa kết quả thực nghiệm và lý thuyết đang có một khoảng cách nhất định.  Điều này như một gợi ý giúp cho chúng ta chú ý trong quá trình sinh khóa bí mật cho hệ thống khóa mã dưới dạng dãy giả ngẫu nhiên..

4.2Mã hóa và giải mã dựa vào nhóm cyclic :

4.2.1        Yêu cầu

  • Đầu vào: chuỗi các số tự nhiên, được phân cách với nhau bằng khoảng trắng
  • Đầu ra: mỗi chuỗi các số tự nhiên (có số lượng số bằng với đầu vào) đã được mã hóa bằng phương pháp trình dưới đây, các số được phân cách với nhau bằng khoảng trắng

4.2.2        Cơ sở toán học

  • Sử dụng cơ sở toán học trong trường Cyclic

Cho p là số nguyên tố

-       Zp là trường chứa tất các số nguyên dương nhỏ hơn p

                                    Zp = {0, 1, 2, 3, …, p-1}

-       Phần tử nghịch đảo của x trong Zp là phần tử y thỏa mãn:

                                    x.y = 1 trong Zp

-       Zp* là trường chứa tất cả các phần tử khả nghịch trong Zp

                                    Zp* = {1, 2, 3, …., p-1}

  • Sử dụng bộ khóa được tạo ngẫu nhiên từ module tạo khóa ngẫu nhiên

4.2.3        Thuật toán

-          Đầu vào: chuỗi các số tự nhiên, được phân cách với nhau bằng khoảng trắng

-          Bộ khóa: đã được tạo ra ngẫu nhiên từ module tạo khóa ngẫu nhiên, với số lượng khóa bằng số lượng số trong chuỗi đầu vào

Các bước mã hóa

Bước 1:

-       Tách lấy số đầu tiên trong chuỗi đầu vào: ký hiệu ni

-       Lấy khóa đầu tiên trong bộ khóa: ký hiệu ki

-       Thực hiện mã hóa: ci = ni * ki mode p

-       Thêm ci vào chuỗi output

Bước 2:

-       Lặp bước 1 cho số và khóa tương ứng, cho đến cuối chuỗi đầu vào

=> Kết quả quá trình mã hóa ta được chuỗimã hóa

Các bước giải mã:

Bước 1:

-       Tách lấy số đầu tiên trong chuỗi đã mã đầu vào: ký hiệu ci

-       Lấy khóa đầu tiên trong bộ khóa: ký hiệu ki

-       Thực hiện tìm phần tử nghịch đảo của ki  bằng thuật toán Eculid mở rộng: ký hiệu kj

-       Thực hiện giải mã: ni = ci * kj mode p

-       Thêm ni vào chuỗi output

Bước 2:

-       Lặp bước 1 cho số và khóa tương ứng, cho đến cuối chuỗi mã

            => Kết quả quá trình giải mã được chuỗi ban đầu

4.3Thiết lập hệ mật kép an toàn :

4.3.1 Mô tả hệ thống

Trong quá trình truyền tin, nếu thông tin cần gửi đi có kích thước nhỏ, chỉ có một vài từ, một vài số liệu thì các phương pháp mã hóa thông thường như mã hóa RSA, AES, … sẽ phát huy hiệu quả. Nhưng nếu với một lượng thông tin lớn đến vài MB hay thậm chí GB thì chỉ với phương pháp mã hóa đơn giản sẽ không thể đem lại hiệu quả, hiệu suất cao. Dựa trên những phương pháp mã hóa thông tin cơ bản, hệ thống được xây dựng nhằm mã hóa một hay nhiều văn bản tiếng Việt với khối lượng thông tin lưu trữ lớn.

Để tăng tốc độ mã hóa cũng như tăng tính bảo mật, hệ thống sẽ xây dựng một từ điển các từ thường dùng với độ ưu tiên dựa vào tần suất xuất hiện của các từ trong thực tế và thực hiện mã hóa dựa trên từ điển đó. Với một văn bản đầu vào, hệ thống sẽ phân tách thành các từ, cụm từ, câu thông dụng trong tiếng Việt và lần lượt chuyển các câu, cụm từ, từ đó thành một chuỗi số dựa theo mã, độ ưu tiên của chúng trong từ điển. Sau khi có được một chuỗi số, hệ thống sẽ thực hiện quá trình mã hóa. Điểm mấu chốt của quá trình này là phải làm sao tạo ra được một bộ khóa đảm bảo tính chính xác và ngẫu nhiên tương ứng với bộ số vừa nhận được. Bài toán sinh khóa ngẫu nhiên được đặt ra. Dựa trên các phương pháp sinh dãy số giả ngẫu nhiên, hệ thống đã tạo ra được những bộ khóa ngẫu nhiên đảm bảo đáp ứng yêu cầu bài toán. Khi có trong tay bộ khóa ngẫu nhiên đó, việc mã hóa thông điệp trở lên rất dễ dàng. Vẫn sử dụng các phương pháp mã hóa thông thường như RSA, với từng khóa trong bộ khóa hệ thống thực hiện mã hóa cho từng số trong chuỗi số và thu được một bản mã có thể gửi đi. Bên phía người nhận sẽ thực hiện quá trình giải mã và dựa vào từ điển để có thể tìm ra được bản rõ ban đầu. Có thể tóm tắt cách thức mã hóa của hệ thống theo sơ đồ dưới đây:

4.3.2 .Môi trường và dữ liệu thực nghiệm

a)      Môi trường thực nghiệm

  • Chip: Intel Core i5 CPU 2.4GHz
  • Ram: 2.00 GB
  • Hệ điều hành: Microsoft Windows 8 32 bits
  • Công cụ lập trình: Visual Studio C++

b)      Dữ liệu thực nghiệm

Chương trình demo với dữ liệu đơn giản

Input: file test.txt với nội dung: “Đây là hệ thống mã hóa văn bản sử dụng từ điển của nhóm Bảo mật và an toàn thông tin số 1- Trường Đại học Công nghệ – Đại học Quốc Gia Hà Nội”

  • Sử dụng từ điển (phần chạy bên trong chương trình)

Từ chuỗi đầu vào sau khi qua từ điển được chuỗi số sau:

  • Sinh khóa ngẫu nhiên (phần chạy bên trong chương trình)
  • Mã hóa và giải mã (phần chạy bên trong chương trình)

Dựa vào từ điển ban đầu để dịch ngược bản rõ nhận được sau quá trình mã hóa thành văn bản lưu trong file plaintext.txt

4.3.3 Đánh giá

  • Việc thu thập dữ liệu được xử lý một cách ngẫu nhiên, qua đó có thể tin tưởng mẫu dữ liệu là đảm bảo tính ngẫu nhiên.
  • Việc xử lý ngôn ngữ tự nhiên sử dụng thư viện VNT giúp các từ phân tách ra có nghĩa, phù hợp với văn phong Việt Nam, tạo ra từ điển bao gồm số lượng từ lớn, đủ để mã hóa văn bản.
  • Việc đếm tần suất từ giúp việc gán mã ID sau này thuận tiện, tối ưu.
  • Việc đánh số định danh cho từng từ giúp quá trình mã hóa và giải mã văn bản dễ dàng, đồng nhất.
  • Việc sử dụng bộ sinh số ngẫu nhiên BBS đảm bảo độ an toàn và tính ngẫu nhiên cho dãy số được sinh ra.
  • Thuật toán mã hóa đơn giản, hiệu suất cao

5. Kết luận

Trong bài báo này chúng tôi đề cập đến một số khái niệm và hai định lý dùng để tính toán cận dưới và cận trên của một dãnh số giả ngẫu nhiên. Mặt khác cũng đưa ra phần thực nhiệm tính chu kỳ của dãy (2.2.1) theo thực tế và phần tính cận trên của chu kỳ theo lý thiết qua đó đưa ra một số kết luật rằng về mặt thực nghiệm và lý thuyết đang có một khoảng cách nhất định về cách tính chu kỳ của dãy số giả ngẫu nhiên Blum Blum Shub.

Tài liệu tham khảo

[1]    Igor Sharlinski, Cryptographic Applications of Analytic number Theory, Springer, 2003.

[2]    Trịnh Nhật Tiến, Giáo trình An toàn thông tin, Trường ĐHCN, ĐHQG HN.

[3]    GS.TS Nguyễn Bình, TS. Trần Đức Sự.“Giáo trình cơ sở lý thuyết mật mã. Ban cơ  yếu chính phủ, học viện kỹ thuật mật mã”,  Hà nội năm 2000.

[4]    Phan Đình Diệu,Lý thuyết mật mã & an toàn thông tin. Đại học quốc gia Hà nội, Khoa công nghệ” , Nhà xuất bản Đại học quốc gia Hà nội năm 2002.


Hội nghị tổng kết 2016-2017
Hội nghị tổng kết 2016-2017
Tiến tới kỷ niệm 10 năm ĐHHB
Tiến tới kỷ niệm 10 năm ĐHHB
Kỷ yếu 10 năm xây dựng
Kỷ yếu 10 năm xây dựng
Lễ Bế mạc đánh giá ngoài
Lễ Bế mạc đánh giá ngoài

Lễ bế mạc

Kiểm định chất lượng GD
Kiểm định chất lượng GD
Bóng đá nữ Đại học Hòa Bình
Bóng đá nữ Đại học Hòa Bình
Phòng PA83 CA Hà Nội chúc mừng ….
Phòng PA83 CA Hà Nội chúc mừng ….
Chúc mừng Ngày 20/11/2017!
Chúc mừng Ngày 20/11/2017!
Tường thuật lễ Khai giảng
Tân Sinh viên Khoa Pr nói về ĐHHB
Lễ Khai Giảng 2017
Lễ Khai Giảng 2017
Ảnh lưu niệm Ngày Khai Giảng
Ảnh lưu niệm Ngày Khai Giảng
Sinh viên Biểu diễn nhân ngày Khai giảng 2017
Thực hành CNTT…
Thực hành CNTT…
Biểu diên thời trang-Lễ phát bằng
Nhóm Sinh viên lớp 4
Nhóm Sinh viên lớp 4
Lễ trao bằng tốt nghiệp-2017
Lễ trao bằng tốt nghiệp-2017
Phóng sự của TV Hà Nội về ĐHHB
9 lợi thế của sinh viên ĐHHB
9 lợi thế của sinh viên ĐHHB
Bản đồ Hà Nội-Đại học Hòa Bình
Video về Đại học Hòa bình
Ngày khai giảng ĐHHB
Ngày khai giảng ĐHHB
Đại Học Hòa Bình & doanh nghiệp
Sinh viên ĐHHB thực hành
Sinh viên ĐHHB thực hành
Một số Trang cần lưu ý
5 Thông tin mới nhất
Bảo vệ luận văn thạc sỹ CNTT
Bảo vệ luận văn thạc sỹ CNTT
Trường Đại Học Hòa Bình
*CHÀO MỪNG VÀ CÁM ƠN BẠN ĐÃ GHÉ THĂM TRƯỜNG ĐẠI HỌC HÒA BÌNH QUA WEBSITE hbuniv.edu.vn. CHÚC BẠN MỌI SỰ TỐT LÀNH*>
Sinh viên ĐHHB được tuyên dương
Nhấn chuột phải-view image để xem ảnh

Nhấn chuột phải-view image để xem ảnh

Lễ ký kết hợp tác toàn diện
TIN TỨC - SỰ KIỆN
THÔNG BÁO
Giới thiệu Đại học Hòa Bình
Vi du the marquee trong HTML

Mời các bạn yêu thích Video vào mục Video để xem