Bài 4 mã hóa khóa công khai rsa

Một số tính chất của Modulo:Cho a, b và n là các số nguyên, phép chia modulo có... Số nguyên tố cùng nhau:Hai số nguyên a, b được gọi là nguyên tố cùng nhau nếu USCLN của a và b

BÀI 4: MÃ HÓA KHÓA CÔNG

KHAI RSA

Nhóm 8

HỌC PHẦN : BẢO MẬT THÔNG TIN

KHOA: CÔNG NGHỆ THÔNG TIN

EIGHT TEAM NGUYỄN HOÀNG PHÚC

TRẦN HỮU NHẬT

NGUYỄN HẢI ĐĂNG

TRƯƠNG TRUNG TUẤN GIẢNG VIÊN HƯỚNG DẪN: TỐNG THANH VĂN

4.1 LÝ THUYẾT SỐ

4.1.1 Một Số Khái Niệm

1.Phép chia modulo:

Khái niệm: là phép chia lấy phần dư.

Tổng quát: a mod n = r với a ≥ 0; n > 0; 0 ≤ r ≤ n-1

Nếu 2 số a, b có cùng số dư trong phép chia cho n thì a

và b là đồng dư trong phép chia modulo cho n:

a ≡ b (mod n) hay viết tắt a ≡ b mod n

2 Một số tính chất của Modulo:

Cho a, b và n là các số nguyên, phép chia modulo có

3 Ước số:

Nếu a mod n = 0 (hoặc a ≡ n) có nghĩa là a chia hết cho

n, hay n là ước số của a.

USCLN của hai số: ký hiệu gcd(a, b) Để tìm USCLN của hai số a, b, chúng ta có thể dùng thuật toán Euclid.

4 Số nguyên tố:

Một số p được gọi là số nguyên tố nếu p chỉ chia hết

cho 1 và chính nó, ngoài ra không chia hết cho số nào khác từ 2 đến p – 1.

5 Số nguyên tố cùng nhau:

Hai số nguyên a, b được gọi là nguyên tố cùng nhau nếu

USCLN của a và b là 1 Ký hiệu: a ⊥ b

VD: 3 ⊥ 8, 7 ⊥ 9, 4 ⊥ 15 Hai số 20 và 15 không nguyên tố cùng nhau vì có USCLN là 5.

6 Phần tử nghịch đảo của phép nhân modulo:

Nếu hai số nguyên a và b nguyên tố cùng nhau, thì tồn

tại số nguyên w sao cho: a.w = 1 mod n

Ta gọi w là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu a^(-1)

4.1.2 Định Lý Fermat

Định lý: Nếu p là số nguyên tố và a là số nguyên tố

không chia hết cho p thì a^(n-1) ≡ 1 mod p

Chứng minh:(Sách)

VD:

p = 5, a = 7 => 7^4 = 2401, 2401 ≡ 1 mod 5

p = 7, a = 4 => 4^6 = 4096, 4096 ≡ 1 mod 5

Bảng sau minh họa các giá trị của phép lũy thừa modulovới n = 19, a và x từ 1 đến 18.

Việc tính logarith rời rạc đã được chứng minh là rất tốn kém về mặt thời gian Và được xem như là bất khả thi

nếu a và n là các số lớn

Do đó phép lũy thừa modulo cũng được xem là hàm

một chiều và được ứng dụng trong phương pháp trao

đổi khóa Diffie – Hellman.

4.2 MÃ KHÓA CÔNG KHAI

Sơ bộ về mã khóa công khai

Giới thiệu

- Ra đời năm 1970, là bước tiến quan trong lịch sử

- Sử dụng 2 khóa không đối xứng nhau gồm một khóa côngkhai và một khóa riêng :

Khóa công khai: Mọi người đều biết dùng để mã

hóa mẫu tin, kiểm chứng

Khóa riêng: Dùng riêng bí mật để giải mã bản tin, tạo

chữ ký

Tính chất bất đối xứng vì người mã hóa nhưng không

thể giải mã

SƠ ĐỒ VỀ ỨNG DỤNG MÃ KHÓA CÔNG KHAI

ỨNG DỤNG KHÓA CÔNG KHAI

Bảo mật Đây là ứng dụng bảo mật truyền thống giống như khóa đối xứng

Chữ ký điện tử.

Xác nhận được người gửi và có thể một lựa chọn để tạo chữ cái điện

tử của người gửi.

Cho phép chia sẻ khóa phiên bản trong mã đối xứng.

Chữ ký điện tử Trao đổi khóa

MÔ HÌNH ỨNG DỤNG KHÓA BÍ MẬT

Một số giải thuật công khai thích hợp

cả 3 loại ứng dụng hay một số khác

cũng có thể dung cho 1 và 2 loại.

TÍNH AN TOÀN CỦA SƠ ĐỒ KHÓA CÔNG KHAI

- Nếu khóa sử dụng là cỡ lớn hơn 512 bit thì tìm khóa riêng

là không khả thi khi biết khóa khóa công khai.

- Bởi vì nó đòi hỏi sử dụng số rất lớn, nên số phép toán

cần thực hiện là rất nhiều khi thám mã.

Kết luận:

Mã công khai thường chạy chậm hơn khá nhiều so với mã đối xứng nên thường được dung mã nhưng thông tin nhỏ quan trọng.

4.3 RSA

4.3 RSA

(*)Định nghĩa:

-RSA là một phương pháp mã hoá khoá công khai.

-Được xây dựng bởi các tác giả Ron Rivest, Adi Shamir và Len Adleman tại học viện MIT năm 1977.

-Về mặt tổng quát RSA là một phương pháp mã hoá theo

khối.

-RSA sử dụng hàm một chiều với độ khó của bài toán phân tích ra thừa số các số lớn.

(n, e) : Khoá công khai

Cơ chế hoạt động:

(d): Khoá bí mật

B

4.3.1 Khởi tạo khoá RSA

Mỗi người sử dụng tạo cặp khoá công khai -riêng:

-Chọn ngẫu nhiên 2 số nguyên tố lớn p và q

4.3.2 Sử dụng RSA

(.)Để mã hoá mẩu tin:

-Lấy khoá công khai theo thuật toán trên

4.3.3 Cơ sở RSA

-Theo định lý Ole: a^ø(n) mod N = trong đó (a, N) =1

-Ta có N = p.q, với ø(N) = (p-1).(q-1), e.d =1 mod ø(N) ->e.d = 1+k.ø(N) đối với giá trị K nào đó

=> C^d =(M^e)^d = M^1+k.ø(N) = M^1.(M^ø(N))^K

-Nên C^d mod N = M^1.(1)^K modN = M^1 mod N = M

mod N

VẬN HÀNH

4.3.5 : Sinh khóa RSA

Người sử dụng RSA cần phải xác định ngẫu nhiên 2 số

nguyên tố rất lỡn, thông thường khoảng 512 bit Do đó việc sinh ra ngẫu nhiên p, q và kiểm tra xác suất tính nguyên tố của chúng có nhiều giải pháp khác nhau với ø(n), dễ dàng tính được kháo kia chính là số nghịch đảo của nó qua thuật toán Euclide mở rộng.

4.3.6 : Độ an toàn của RSA

Người ta thường cho rằng RSA đảm bảo an

toàn với điều kiện n

được chọn đủ lớn.

Kích thước N phải khoảng 1024 bit (309 chữ số) thì bảo đảm

an thật sự

4.3.6 : Độ an toàn của RSA

2 Phân tích số nguyên tố

Phân tích N thành thừa số nguyên tố M= p.q để tìm d, tuy nhiên thực tế kích thước N với số bit lớn việc phân tích thừa số nguyên tố là bất khả thi.

3 Đo thời gian :

Dựa vào “hiệu ứng sinh lề” (thời gian thực hiện giải mã) sinh ra bởi quá trình giải mã RSA