Hệ mật IDEA

Hệ mật IDEA
F
1
F
2

Z
5

Z
6

G
1
G
2

Hình 1: Cấu trúc Multiplication/Additio (MA)
Khối này nhận 16 bit từ bản rõ và 16 bit được lấy từ khoá ra theo một quy
tắc nào đó ( 16 bit này được gọi là subkey và quy tắc lấy subkey từ khoá sẽ
được trình bày ở sau)để tạo ra 16 bit đầu ra. Một chương trình kiểm tra trên máy
tính bằng phương pháp vét cạn xác định rằng mỗi bit ở đầu ra phụ thuộc vào
các bít rõ và bit subkey đầu vào. Cấu trúc này được sử dụng lặp lại 8 lần trong
thuật toán và tạo nên một sự phân bố có hiệu qủa.
IDEA được xây dựng sao cho việc thực hiện nó được dễ dàng cả trên
phần cứng và phần mềm . Việc thực hiện trên phần cứng, điển hình là trên vi
mạch VLSI (VLSI: mạch tích hợp cao) , được thiết kế để đạt được tốc độ cao.
Việc xây dựng trên phần mềm thì thuận tiện và giá thành thấp.
5
⊗
⊗


Hệ mật IDEA
Những điểm chủ yếu trong việc xây dựng phần mềm:
+ Sử dụng những khối nhỏ : những phép mã thực hiện trên những khối có độ
dài 8,16,32 bit phù hợp với việc xử lý trên máy tính.
+ Sử dụng thuật toán giản đơn :Phép toán mã dễ dàng trong lập ttình như phép
cộng , phép dịch chuyển (shift), , Cả 3 phép toán của IDEA đều thoả mãn
những yêu cầu này. Điểm khó khăn nhất là phép toán nhân modulo(2
16
+1) cũng
có thể dễ dàng xây dựng từ những phép toán sẵn có .
- Những điểm chủ yếu trong việc thực hiện trên phần cứng:
+ Sự tương tự trong mã hoá và giải mã : Mã hoá và giải mã chỉ nên khác
nhau trong việc sử dụng khoá và nhờ đó một phương tiện có thể dùng cho cả mã
hoá và giải mã.
+ Cấu trúc lặp lại : Phương pháp mã nên có cấu trúc modul lặp lại để các
mạch VLSI có thể thực hiện được dễ dàng. IDEA được xây dựng từ 2 khối
modulo đơn giản và sử dụng lặp lại nhiều lần.
I.1.3 Mã hoá và giải mã trong IDEA:
a. Mã hoá:
Giống như các sơ đồ mã hoá khác, hàm mã hoá có 2 tham số ở đầu vào là
Bản rõ cần mã và khoá. Trong trường hợp này là 64 bit rõ là 128 bit khoá .
Từ đầu vào đến đầu ra, các bit rõ lần lượt đi qua 8 modul và một hàm
biến đổi cuối cùng. Tám modul này có cấu trúc giống nhau và thực hiện các thao
tác như nhau với dữ liệu đầu vào. Mỗi modul nhận 4 khối 16 bit rõ ở đầu vào
cùng với các subkey và đưa ra 4 khối 16 bit đã được mã hoá. Do đó 64 bit rõ sẽ
được chia thành 4 khối nhỏ gọi là các subblock, mỗi subblock là 16 bit. Cùng
với các subblock này là 6 khối subkey cũng sẽ được đưa vào từng modul. Như
6
Hệ mật IDEA
vậy thêm 4 subkey cần thiết cho hàm biến đổi cuối cùng, ta cần tổng cộng 52
khối subkey cho một lần
64 bit rõ



Hình 2: Cấu trúc IDEA
Như đã nói ở trên, các modul có cấu trúc giống nhau và chỉ khác nhau ở
dữ liệu đầu vào. Trừ modul đầu tiên nhận 64 bit rõ đưa từ ngoài vào, các modul
đứng sau sẽ nhận 4 khối subblock 16 bit đầu ra của modul đứng trước nó làm các
bit rõ đầu vào. Trong quá trình đầu tiên các modul kết hợp 4 subblock với 4
subkey bằng các phép toán  và ⊗. Bốn khối đầu ra của quá trình này XOR với
nhau như trong sơ đồ để tạo ra 2 khối đầu vào cho cấu trúc MA sẽ kết hợp
chúng với 2 subkey còn lại để tạo ra 2 khối 16 bit mới.
7
X1 X2 X3 X4
W11

W12 W13 W14
Modul 2
W21 W22
1
W23 W24
W71
W72
W73 W74
W81 W82 W83 W84
Modul 8
Hàm biến đổi
Z1 Z52
Modul 1
Tạo Subkey từ
khoá
128 bit khoá
Z
16 16
64 bit mã
Hệ mật IDEA
Cuối cùng, 4 khối được tạo ra từ quá trình đầu tiên sẽ được XOR với 2
khối đầu ra của cấu trúc MA để tạo ra 4 khối đầu ra của modul. Ta cũng cần chú
ý một điều là 2 khối đầu vào X
2
và X
3
được hoán đổi cho nhau để tạo ra 2 khối
W
12
và W
13
được đưa ra ngoài. Điều này làm tăng sự hoà trộn của các bit được
xử lý và tăng khả năng chống lại các phương pháp mã thám.
X1 X2 X3 X4



Hàm biến ở cuối cùng ta cũng có thể coi như một modul thứ 9. Hàm này
có cấu trúc giống như cấu trúc đã thực hiện trong quá trình đầu tiên của một
modul chỉ khác một điều là khối thứ 2 và thứ 3 ở đầu vào được đổi chỗ cho nhau
trước khi được đưa tới đơn vị phép toán. Thực ra đây chỉ là việc trả lại thứ tự đã
bị đổi sau modul thứ 8. Lý do của việc này là sự giống nhau về cấu trúc của quá
trình giải mã và quá trình mã hoá.
8
Hình 3: Cấu trúc một modul (Modul 1)
⊗
⊗
⊗

⊗

⊗
⊕
⊕ ⊕

⊗


⊕
W11 W12 W13 W14
Z6
Z5
Z3
Z4
Z1
Z2
Hệ mật IDEA




Y1 Y2 Y3 Y4
Hình 4: Hàm biến đổi của IDEA
* Quy tắc tạo ra subkey:
Như trên đã trình bày, cần thiết phải có 52 khối subkey 16 bit được tạo ra từ
128 bit khoá. Quy tắc tạo subkey như sau:
- 8 subkey đầu tiên , Z1 Z8, được lấy trực tiếp từ khoá với X1 là 16 bit đầu
( Bit có trọng số cao nhất ), Z2 là 16 bit tiếp theo và cứ tiếp tục như vậy
- Sau đó khoá được quay trái 25 bit và 8 subkey tiếp theo được tạo ra theo quy
tắc trên. Thao tác này được lặp lại cho đến khi có đủ 52 khối subkey.
Quy tắc này là một phương pháp hiệu quả cho việc đa dạng hoá các bit
khoá dùng cho các modul. Ta nhận thấy rằng những subkey đầu tiên dùng trong
mỗi modul sử dụng những tập hợp bit khác nhau của khoá. Nếu như khoá 128 bit
được ký hiệu là Z[ 1 128] thì subkey đầu tiên của modul sẽ là :
Z
1
= Z[ 1 16] Z
25
= Z[76 91]
Z
7
= Z[97 112] Z
31
= Z[44 59]
Z
13
= Z[90 105] Z
37
= Z[37 52]
Z
19
= Z[83 98]

Z
43
= Z[30 45]
Như vậy , 96 bit subkey sử dụng cho mỗi modul , trừ modul thứ nhất và
modul thứ 8, là không liên tục. Do đó không có một mối liên hệ dịch chuyển đơn
9


⊗
⊗
Z52
Z51
Z49
Z50
Hệ mật IDEA
giản nào giữa các subkey của của một modul và giữa các modul với nhau.
Nguyên nhân có được kết quả này là việc chỉ có 6 khối subkey được sử dụng
trong khi có 8 khối subkeyđược tạo ra trong mỗi lần dịch chuyển khoá.
b. Giải mã : Quá trình giải mã về cơ bản giống quá trình mã hoá, giải mã nhận
bản mã ở đầu vào và cùng đi qua những cấu trúc như ở trên, chỉ khác ở sự lựa
chọn các subkey. Các subkey để giải mã U
1
, U
2
, U
52
nhận được từ khoá mã theo
quy tắc sau:
Đối với modul giải mã i ta lấy 4 subkey đầu của modul mã hóa thứ (10 - i
), ở đây hàm biến đổi được coi như modul thứ 9. Sau đó lấy nhân đảo modulo
(2
16
+1) của subkey thứ 1 và thứ 4 để dùng cho subkey giải mã thứ 1 và thứ 4
tương ứng. Đối với các modul từ thứ 2 đến thứ 8, subkey giải mã thứ 2 và thứ 3
là cộng đảo modulo2
16
của subkey thứ 3 và thứ 2 tương ứng. Đối với các modul
thứ 1 và thứ 9 , cho subkey giải mã thứ 2 và thứ 3 là cộng đảo modul2
16
của
subkey thứ 3 và thứ 2 tương ứng.
-Đối với 8 modul đầu tiên , 2 subkey cuối cùng của modul i là 2 subkey
cuối cùng của modul mã hoá thứ ( 9 - i ).
ở đây nhân đảo Z
j
-1
của Z
j
là:
Z
j
⊗ Z
j
-1
=1
Vì 2
16
+ 1 là một số nguyên tố nên mỗi số nguyên Z
j
<

2
16
có một số nhân đảo
modulo(2
16
+ 1) duy nhất.
Với cộng đảo hai modullo 2
16
ta có:
-Z
j
 Z
j
= 0
Hình sau hiện quá trình mã hoá ( theo chiều đi xuống bên trái) và quá trình
giải mã ( chiều đi lên bên phải) của thuật toán IDEA.



10
X
1
X
2
X
3
X
4
Biến đổi
I
11
I
12
I
13
I
14
Mã hoá
W
11
W
12
W
13
W
14
Biến đổi
I
21
I
22
I
23
I
24
Mã hoá
W
21
W
22
W
23
W
24
W
71
W
72
W
73
W
74
Mã hoá
I
81
I
82
I
83
I
84
W
81
W
82
W
83
W
84
Biến đổi đầu ra
Y
1
Y
2
Y
4
Y
4
Y
4
Y
4
Y
4
Y
3
Biến đổi
X
1
X
2
X
3
X
4
Biến đổi đầu ra
Mã hoá
V
81
V
82
V
83
V
84
Biến đổi
J
14
J
13
J
12
J
11
J
24
J
23
J
22
J
21
J
81
J
82
J
83
J
84
V
71
V
72
V
73
V
74
Biến đổi
Biến đổi
V
24
V
23
V
22
V
21
V
71
V
14
V
13
V
12
V
11
V
21
Mã hoá
Mã hoá
Modul1
Modul2Modul8
Modul8
Modul2Modul1
{
{
{
{
{
{
{
Z
1
Z
4
Z
5
Z
6
Z
11
Z
12
Z
7
Z
10
Z
1
Z
4
Z
42
Z
46
Z
47
Z
48
Z
49
Z
52
Z
5
Z
6
U
1
U
4
U
5
U
6
U
1
U
10
U
11
U
12
U
43
U
46
U
47
U
48
U
1
U
4
U
49
U
52
Hệ mật IDEA

Hình 5: Mã hoá và giải mã trong IDEA.
Mỗi modul được chia thành 2 khối nhỏ: khối biến đổi và khối mã hoá.
Khối biến đổi tương ứng với quá trình đầu tiên trong mỗi modul, còn khối mã
hoá tương ứng với các quá trình còn lại. Ở phía cuối của sơ đồ, bên mã hoá ta
nhận được các mối quan hệ giữa các đầu ra và đầu vào của hàm biến đổi:
Y
1
= W
81
⊗ Z
49
Y
3
= W
82
 Z
51
Y
2
= W
83
 Z
50
Y
4
= W
82
⊗ Z
52
Tại khối biến đổi của modul thứ nhất trong quá trình giải mã, đầu ra và
đầu vào có mối quan hệ sau:
J
11
= Y
1
⊗ U
1
J
13
= Y
3
 U
3


J
12
= Y
2
 U
2
J
14
= Y
4
⊗ U
4

Ta có:
J
11
= Y
1
⊗ Z
49

–1
= W
81
⊗ Z
49
⊗ Z
49
-1
=W
81
J
12
= Y
2
 -Z
50
= W
83
 Z
50
 -Z
50
= W
83
11
Hệ mật IDEA

J
13
= Y
3
 -Z
51
= W
82
 Z
51
 -Z
51
= W
82
J
11
= Y
4
⊗ Z
50

–1
= W
84
⊗ Z
50
⊗ Z
50
-1
=W
84
Như vậy, kết quả thu được sau khối biến đổi thứ nhất của quá trình giải
mã chính là dữ liệu rõ đưa vào khối mã hoá cuối cùng của quá trình mã hoá chỉ
khác là khối dữ liệu thứ 2 và khối dữ liệu thứ 3 đã đổi chỗ cho nhau. Bây giờ ta
sẽ xét đến mối quan hệ thu được theo Hình 3
W
81
= I
81
⊕ MA
R
( I
81
⊕ I
83
, I
82
⊕ I
84
)
W
82
= I
83
⊕ MA
R
( I
81
⊕ I
83
, I
82
⊕ I
84
)
W
83
= I
82
⊕ MA
L
( I
81
⊕ I
83
, I
82
⊕ I
84
)
W
84
= I
84
⊕ MA
L
( I
81
⊕ I
83
, I
82
⊕ I
84
)
Trong đó MA
R
(X,Y) là đầu ra phía bên phải còn MA
L
(X,Y) là đầu ra phía bên
trái của cấu trúc MA trong hình 1 khi đầu vào là X và Y. Và:
V
11
= J
11
⊕ MA
R
(J
11
⊕ J
13
, J
12
⊕ J
14
)
= W
81
⊕ MA
R
(W
81
⊕ W
82
, W
83
⊕ W
84
)
= I
81
⊕ MA
R
( I
81
⊕ I
83
, I
82
⊕ I
84
) ⊕ MA
R
[I
81
⊕ MA
R
( I
81
⊕
I
83
, I
82
⊕ I
84
) ⊕ I
83
⊕ MA
R
( I
81
⊕ I
83
, I
82
⊕ I
84
),
I
82
⊕ MA
L
( I
81
⊕ I
83
, I
82
⊕ I
84
) ⊕ I
84
⊕ MA
L
( I
81
⊕ I
83
, I
82
⊕ I
84
)]
= I
81
⊕ MA
R
( I
81
⊕ I
83
, I
82
⊕ I
84
) ⊕ MA
R
(W
81
⊕ W
82
, W
83
⊕ W
84
)
=I
81
Tương tự ta có :
V
12
= I
82
V
13
= I
83
V
14
= I
84
12
Hệ mật IDEA
Như vậy kết quả thu được sau khối mã hoá thứ nhất của quá trình giải mã
lại là dữ liệu đưa vào khối biến đổi của modul cuối cùng của quá trình mã hoá
chỉ khác là khối dữ liệu thứ 2 và khối dữ liệu thứ 3 đã đổi chỗ cho nhau. Cứ như
vậy ta sẽ thu được:
V
81
= I
11
V
82
= I
13
V
83
= I
12
V
84
=I
14
Vì hàm biến đổi cuối cùng của quá trình giải mã cũng giống như khối biến
đổi trong modul đầu tiên của quá trình mã hoá chỉ khác là có đổi chỗ của khối
dữ liệu thứ 2 và khối dữ liệu thứ 3 nên ta có bản rõ thu được sau bản mã giống
bản rõ đưa vào mã hoá .
I.1.4 Quá trình làm việc của một Modul
Để dễ dàng nhìn thấy hơn về quá trình làm việc của 1 modul. Theo như hình 3
( Cấu trúc của 1 modul). Ta thấy 4 khối được đưa vào là X1, X2, X3, X4 cùng
với các khoá Z1, Z2, Z3, Z4, Z5, Z6 thì sau các quá trình biến đổi sẽ đưa ra các
khối là W1, W2, W3, W4 .
Giả sử ta quy ước các kết quả của mỗi phép toán là : K1, K2, K3, K4, K5,
K6, K7, K8, K9, K10, K11, K12 thì ta có:
13
Hệ mật IDEA
X1 X2 X3 X4

Z1 Z3
Z2 Z4


Z5

Z6



W11 W12 W13 W14
• Với W11:
W11 = K1 ⊕ K2
Trong đó :
K1 = Z1 ⊗ X1
14
Hình 3: Cấu trúc một modul (Modul 1)
⊗
⊗
⊗

⊗

⊗
⊕
⊕
⊕ ⊕

⊗


K2
K11
K1
K3
K9
K7
K10
K8
K4
K5K6
K12

Xem chi tiết: Hệ mật IDEA