tailieunhanh - Giáo án an toàn bảo mật -8

Như vậy sử dụng thuật toán “bình phương và nhân” sẽ làm giảm số phép nhân modulo cần thiết, để tính x mod n nhiều nhất là 2, trong l là số bít trong biểu diễn nhị phân của b. Vì l ≤ k nên có thể coi xb mod n được thực hiện trong thời gian đa thức 0(k3). | Tính xb mod n Trước hết biểu diễn b 2l 0 b 2 2 trong đó bi 0 hoặc 1 0 i l-1. i z 1 ii cho i chạy từ giá trị l-1 về 0 z z2 mod n Nếu bi 1 thì z z x mod n iii giá trị cần tìm chính là giá trị z cuối cùng. Như vậy sử dụng thuật toán bình phương và nhân sẽ làm giảm số phép nhân modulo cần thiết để tính x mod n nhiều nhất là 2 trong l là số bít trong biểu diễn nhị phân của b. Vì l k nên có thể coi xb mod n được thực hiện trong thời gian đa thức 0 k3 . Thuật toán Ơclít mở rộng. Begin g0 O n g1 e uo 1 uf 0 vo 0 vù 1 While gi 0 do Begin y gi-1 div gi gi 1 gi-1 - u1 1 ui-1 - v1 1 vi-1 - i i 1 End x vi-1 If x 0 then d x else d x O n END. Vì vậy muốn xây dựng hệ RSA an toàn thì n pq phải là một số đủ lớn để không có khả năng phân tích nó về mặt tính toán. Để đảm bảo an toàn nên chọn các số nguyên tố p và q từ 100 chữ số trở lên. http 78 Tuy nhiên máy tính thông thường khó có thể tính toán với số nguyên lớn đến mức như vậy. Do đó cần phải có thư viện các thuật toán làm việc với các số nguyên lớn. Ta có thể lưu trữ số lớn như sau - Phân tích số lớn thành số nhị phân. - Chia số nhị phân thành các khối 32 bít lưu vào mảng mỗi phần tử của mảng lưu 32 bít. Ví dụ giả sử a là số lớn được phân tích thành số nhị phân a a0a1. an 32 bít 32 bít 32 bít a0 ai an Cộng hai số lớn Số a a0 ai an Số b b0 bi bn Số c c0 ci cn cn 1 Có một ô nhớ 32 bít để ghi số nhớ khi cộng 2 số ban đầu ô nhớ này bằng 0. Khi cộng thì các phần tử tương ứng cộng với nhau nhớ a0 b0 c0 nhớ a1 b1 c1 nhớ ai bi c Để xem kết quả có nhớ hay không khi tổng c ai thì nhớ 1 Mảng lưu trữ tổng bao giờ cũng lớn hơn mảng của các số hạng tổng một phần tử phần tử mảng cuối cùng này cn 1 lưu số nhớ. Nhân số lớn Khi nhân 2 số 32 bit sẽ tạo ra số 64 bít nhưng hiện nay máy tính không lưu được số 64 bít nên nó chia số 64 bít thành 2 số 32 bít 32 bít thấp và 32 bít cao . Ban đầu nhớ 0. http 79 32 bít low 32 bít high Như vậy khi nhân ao x bo nhớ Co c0 là số 64 bít số Co sẽ chia thành 2 số 32