Một phương pháp tính toán tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng

Số trang: 7 Loại file: pdf Dung lượng: 313.44 KB Lượt xem: 18 Lượt tải: 0

tailieu_vip

Phí lưu trữ: 1,000 VND

Xem trước 1 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Trong việc thực hiện các hệ mật mã khóa công khai, các phép tính toán số học trên các số nguyên lớn luôn là phép tính quan trọng và nặng nề nhất. Để đánh giá được mức độ tiêu tốn tài nguyên cũng như tốc độ thực hiện của các phép toán này, nội dung bài báo trình bày một phương pháp tính toán tính tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Một phương pháp tính toán tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng Nghiªn cøu khoa häc c«ng nghÖ MéT PH¦¥NG PH¸P TÝNH TO¸N T¦¥NG QUAN GI÷A XUNG NHÞP M¸Y Vµ PHÐP CéNG HAI Sè NGUYªN KHI THùC HIÖN TR£N PHÇN CøNG LỀU ĐỨC TÂN*, HOÀNG VĂN QUÂN**, HOÀNG NGỌC MINH* Tóm tắt: Trong việc thực hiện các hệ mật mã khóa công khai, các phép tính toán số học trên các số nguyên lớn luôn là phép tính quan trọng và nặng nề nhất. Để đánh giá được mức độ tiêu tốn tài nguyên cũng như tốc độ thực hiện của các phép toán này, nội dung bài báo trình bày một phương pháp tính toán tính tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng. Từ khóa: Phép cộng, Xung nhịp máy, ECC. 1. MỞ ĐẦU Khi thực hiện tính tổng hai số nguyên X, Y  [0, 2k) bằng mạch cộng m-bits thì số nhịp máy cần thiết để thực hiện phép cộng này, được ký hiệu là flops(X,Y), sẽ là một số xác định. Tuy nhiên nếu ký hiệu F(k) là số nhịp máy để thực hiện phép cộng hai số nguyên trong miền [0, 2k) thì đây sẽ là một đại lượng ngẫu nhiên [1,2]. Bài báo này trình bày kết quả nghiên cứu về số nhịp máy trung bình được ký hiệu là AAF(k) để thực hiện phép cộng hai số nguyên trong miền [0, 2k) và đó cũng chính là giá trị kỳ vọng của đại lượng F(k). Mục 2 mô tả hoạt động của mạch cộng làm cơ sở cho việc xác định các giá trị flops(X,Y) cũng như phân phối xác suất của đại lượng F(k), trong mục này trình bày thêm cách tiếp cận và các công cụ được sử dụng để tìm các giá trị AAF(k). Mục 3 liệt kê các kết quả tính toán được về các giá trị AAF(k) và quan trọng nhất là thu được kết quả AAF(k) trình bày trong kết quả 1 và đã được chứng minh trong mục 3.4. 2. MẠCH CỘNG HAI SỐ NGUYÊN VÀ PHÂN PHỐI XÁC SUẤT CỦA ĐẠI LƯỢNG F(k) 2.1. Hoạt động của mạch cộng m-bits và trạng thái các thanh ghi sau mỗi nhịp máy Mạch cộng bao gồm thanh ghi A được gọi là thanh ghi tổng (theo nghĩa giá trị tổng sẽ được lưu trong thanh ghi này khi mạch dừng hoạt động) còn C được gọi là thanh ghi điều kiển (mạch sẽ dừng khi tất cả các bít trong thanh ghi này bằng 0) [2]. Cho A và C là hai thanh ghi m-bits với m>k. Để tính tổng X+Y với X, Y  [0, 2k), xâu m bít biểu diễn nhị phân của hạng tử thứ nhất đưa vào thanh ghi A còn của hạng tử thứ hai đưa vào thanh ghi C. Tức là nếu biểu diễn nhị phân của X và Y lần lượt là X = (xm1, ..., xk, xk1, ..., x1, x0)2 và (2.1) Y = (ym1, ..., yk, yk1, ..., y1, y0)2 (2.2) thì bít thứ i (i=0, ..., k) của các thanh ghi A và C tương ứng, ký hiệu là A[i] và C[i], là A[i] = xi và C[i] = yi. (2.3) T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 75 Kỹ thuật điện tử & Khoa học máy tính Chú ý: Do X, Y  [0, 2k) nên trong vế phải của (2.1) và (2.2) ta luôn có xs = ys = 0 với mọi sk. Mỗi nhịp máy các giá trị ở bít thứ i của A và C được xử lý tại một khâu tương ứng, bit tổng (không nhớ) được đưa vào bít thứ i của A còn bit tràn được đưa vào bit thứ i+1 của C. Khi thanh ghi C có trị tất cả các bít bằng 0 thì giá trị X+Y có biểu diễn nhị phân chính là các bít tương ứng của thanh ghi A. Ký hiệu A', C' và A', C' là trạng thái của hai thanh ghi A và C trước và sau một nhịp máy nào đó thì C '[0]  0   C '[i ]  A '[i  1]C '[i  1] (0  i  m ) (2.4)  A '[i ]  A '[i ]  C '[i ] (0  i  m ) 2.2. Phân phối xác suất của đại lượng F(k) Tính chất: F(k) là một đại lượng ngẫu nhiên nhận giá trị nguyên từ 0 đến k+1 có phân bố Prob(F(k)=f) = N(k, f ) (f=0, 1, ..., k+1). (2.5) 4k k trong đó, N(k,f) = #{(X,Y): X, Y  [0, 2 ) và flops(X,Y) = f}. Chứng minh: Với Y = 0 thì trạng thái của thanh ghi C có giá trị tất cả các bít bằng 0 vì vậy mạch dừng và điều này có nghĩa flops(X,0) = 0. (2.6) f1 Với mọi f = 1, 2, ..., k+1; lấy X = 1 và Y = 2  1 thì trạng thái đầu tiên của C là có đúng f1 bít 1 từ các vị trí thấp nhất còn của A chỉ có đúng một bít 1 ở vị trí thấp nhất. Dễ dàng nhận ra rằng flops(1, 2f1  1) = f (f = 1, 2, ..., k+1). (2.7) k Bây giờ ta sẽ chứng tỏ với mọi X, Y  [0, 2 ) thì flops(X,Y)  k+1. (2.8) Thật vậy, từ X, Y < 2k nên X + Y < 2k+1 vì vậy trong suốt quá trình thực hiện của mạch cộng thanh ghi C có các bít 1 chỉ xuất hiện ở k+1 vị trí ...