M™t mã ˘ng dˆng Mã khËi
1 / 27
NÎi dung
1 Mã khËi là gì?
2 Hª mã chu©n DES
3 Tßn công vét c§n
4 Hª mã khËi AES
Mã khËi
AES: P C K = = 128 bit, = 128, 192, 256 bit. • | | | | | |
K
C P
P, C, và K ∑u có Î dài cË ‡nh.
DES: P C K = • | 3DES: | P | C | K = 64 bit, | = 64 bit, = 56 bit. = 168 bit. | = • | | | | | |
3 / 27
S˚ dˆng các mode khác nhau ∫ x˚ l˛ ¶u vào vÓi Î dài thay Íi.
Mã khËi
K
C P
P, C, và K ∑u có Î dài cË ‡nh.
3 / 27
DES: P C K = • | 3DES: | P | K | = • | AES: | P | C | K | = = 64 bit, | | = 64 bit, C | = 128 bit, = 56 bit. = 168 bit. = 128, 192, 256 bit. • | | | | | | S˚ dˆng các mode khác nhau ∫ x˚ l˛ ¶u vào vÓi Î dài thay Íi.
Mã khËi ˜Òc xây d¸ng b¨ng cách l∞p
Block$Ciphers$Built$by$Itera key$$k$ key$expansion$ k1$ k2$ k3$ kn$ c$ m$ $
)
⋅
$
,
1
k
(
R $
)
⋅
$
,
2
k
(
R $
)
⋅
$
,
3
k
(
R $
)
⋅
$
,
n
k
(
R $ $for$$3DES$(n=48),$$$$$$for$AES1128$$(n=10)$ Dan$Boneh$ R(k,m)$is$called$a$round$func • 4 / 27 • Phân tích hiªu n´ng1 KhËi/ Î dài khóa TËc Î (MB/sec) 1Crypto++ 5.6.0 [Wei Dai], ADM Opteron, 2.2GHz (Linux) 5 / 27 Hª mã
RC4
Salsa20/12
Sosemanuk
3DES
AES-128 64/168
128/128 126
643
727
13
109 NÎi dung 1 Mã khËi là gì? 2 Hª mã chu©n DES 3 Tßn công vét c§n 4 Hª mã khËi AES 1973: NBS kêu gÂi ∑ xußt hª mã khËi. IBM ã g˚i mÎt bi∏n • th∫ cıa Lucifer. 1976: NBF ã chßp nh™n DES nh˜ chu©n liên bang • Î dài khóa=56 bit; kích th˜Óc khËi=64 bit. Hª mã chu©n DES (Data Encryption
Standard) 1997: DES b‡ phá b¨ng tßn công vét c§n. • 2000: NIST chßp nh™n Rijndael nh˜ chu©n nâng cao (AES) ∫ • thay th∏ DES 7 / 27 ¶u nh˙ng n´m 1970: Horst Feistel thi∏t k∏ Lucifer t§i IBM • Î dài khóa=128 bit; kích th˜Óc khËi=128 bit. 1976: NBF ã chßp nh™n DES nh˜ chu©n liên bang • Î dài khóa=56 bit; kích th˜Óc khËi=64 bit. Hª mã chu©n DES (Data Encryption
Standard) 1997: DES b‡ phá b¨ng tßn công vét c§n. • 2000: NIST chßp nh™n Rijndael nh˜ chu©n nâng cao (AES) ∫ • thay th∏ DES ¶u nh˙ng n´m 1970: Horst Feistel thi∏t k∏ Lucifer t§i IBM • Î dài khóa=128 bit; kích th˜Óc khËi=128 bit. 7 / 27 • 1973: NBS kêu gÂi ∑ xußt hª mã khËi. IBM ã g˚i mÎt bi∏n
th∫ cıa Lucifer. Hª mã chu©n DES (Data Encryption
Standard) 1997: DES b‡ phá b¨ng tßn công vét c§n. • 2000: NIST chßp nh™n Rijndael nh˜ chu©n nâng cao (AES) ∫ • thay th∏ DES ¶u nh˙ng n´m 1970: Horst Feistel thi∏t k∏ Lucifer t§i IBM • Î dài khóa=128 bit; kích th˜Óc khËi=128 bit. • 1973: NBS kêu gÂi ∑ xußt hª mã khËi. IBM ã g˚i mÎt bi∏n
th∫ cıa Lucifer. 7 / 27 1976: NBF ã chßp nh™n DES nh˜ chu©n liên bang • Î dài khóa=56 bit; kích th˜Óc khËi=64 bit. Hª mã chu©n DES (Data Encryption
Standard) 2000: NIST chßp nh™n Rijndael nh˜ chu©n nâng cao (AES) ∫ • thay th∏ DES ¶u nh˙ng n´m 1970: Horst Feistel thi∏t k∏ Lucifer t§i IBM • Î dài khóa=128 bit; kích th˜Óc khËi=128 bit. • 1973: NBS kêu gÂi ∑ xußt hª mã khËi. IBM ã g˚i mÎt bi∏n
th∫ cıa Lucifer. 1976: NBF ã chßp nh™n DES nh˜ chu©n liên bang • Î dài khóa=56 bit; kích th˜Óc khËi=64 bit. 7 / 27 1997: DES b‡ phá b¨ng tßn công vét c§n. • Hª mã chu©n DES (Data Encryption
Standard) ¶u nh˙ng n´m 1970: Horst Feistel thi∏t k∏ Lucifer t§i IBM • Î dài khóa=128 bit; kích th˜Óc khËi=128 bit. • 1973: NBS kêu gÂi ∑ xußt hª mã khËi. IBM ã g˚i mÎt bi∏n
th∫ cıa Lucifer. 1976: NBF ã chßp nh™n DES nh˜ chu©n liên bang • Î dài khóa=56 bit; kích th˜Óc khËi=64 bit. 1997: DES b‡ phá b¨ng tßn công vét c§n. • 7 / 27 • 2000: NIST chßp nh™n Rijndael nh˜ chu©n nâng cao (AES) ∫
thay th∏ DES DES: fi t˜ng chính – M§ng Feistel DES:$$core$idea$–$Feistel$Network$ n Given$func 2n 2n. Goal:$$$$build$inver R0$ n
\
b
i
t
s
$ R1$ R2$ Rd\1$ Rd$ f1$ f2$ fd$ (cid:8)$ L0$ L1$ L2$ Ld\1$ Ld$ (cid:5)$ (cid:5)$ n
\
b
i
t
s
$ (cid:5)$ output$ input$
Nói cách khác In$symbols:$ Cho các hàm 0, 1 f1, . . . , fd : { } !{
Mˆc ích: Xây d¸ng hàm kh£ ngh‡ch F : 0, 1
}
0, 1 !{ { } 1 1) Dan$Boneh$ 1 8 / 27 Li Ri = fi(Ri
Li = Ri ® n \ b i t R0$ s $ R1$ R2$ Rd\1$ Rd$ f1$ f2$ fd$ n \ b i L0$ t L1$ L2$ Ld\1$ Ld$ s (cid:5)$ (cid:5)$ $ (cid:5)$ input$ output$ Bài t™p $Feistel$network$$$$F:${0,1}2n$$⟶$${0,1}2n$$$$is$inver Proof:$$$construct$inverse$ Ri\1$ Ri$ Ri\1$=$Li$ fi$ Hãy xây d¸ng hàm ngh‡ch £o cıa thành ph¶n m§ng sau: inverse$
1 = Li
1 = Li\1$=$fi(Li)$⨁$$Ri$ Li\1$ Li$ (cid:5)$ Dan$Boneh$ 9 / 27 ) ? Ri
Li ® M§ch gi£i mã Decryp (cid:5)$ (cid:5)$ (cid:5)$ Rd$ n
\
b
i
t
s
$ Rd\1$ Rd\2$ R1$ R0$ fd$ fd\1$ f1$ ˜Òc s˚ dˆng trong nhi∑u hª mã khËi... nh˜ng không ph£i • trong AES. Ld$ Ld\1$ Ld\2$ L1$ L0$ n
\
b
i
t
s
$ • Inversion$is$basically$the$same$circuit,$$ • • Used$in$many$block$ciphers$…$but$not$AES$ Dan$Boneh$ 10 / 27 • Hàm ngh‡ch £o có cùng cßu trúc m§ch, chø có th˘ t¸ áp dˆng
$with$$f1,$…,$fd$$applied$in$reverse$order$
các hàm f1, . . . , fd là ng˜Òc l§i.
ây là ph˜Ïng pháp tÍng quát xây d¸ng hàm kh£ ngh‡ch (hay
• General$method$for$building$inver M§ch gi£i mã Decryp (cid:5)$ (cid:5)$ (cid:5)$ Rd$ n
\
b
i
t
s
$ Rd\1$ Rd\2$ R1$ R0$ fd$ fd\1$ f1$ Ld$ Ld\1$ Ld\2$ L1$ L0$ n
\
b
i
t
s
$ • Inversion$is$basically$the$same$circuit,$$ • • Hàm ngh‡ch £o có cùng cßu trúc m§ch, chø có th˘ t¸ áp dˆng
$with$$f1,$…,$fd$$applied$in$reverse$order$
các hàm f1, . . . , fd là ng˜Òc l§i.
ây là ph˜Ïng pháp tÍng quát xây d¸ng hàm kh£ ngh‡ch (hay
• General$method$for$building$inver • Used$in$many$block$ciphers$…$but$not$AES$ Dan$Boneh$ 10 / 27 • ˜Òc s˚ dˆng trong nhi∑u hª mã khËi... nh˜ng không ph£i
trong AES. SÏ Á ¶y ı cıa DES 56 bit key k1 k2 k3 k16 · · · s
t
i s
t
i b b IP FP 16 round Feistel network 4
6 4
6 32 0, 1 32, 0, 1 Hình: f1, . . . , f16 : fi(x) = F (ki, x) { } } 11 / 27 Figure 4.9: The complete DES circuit
!{ Beyond the S-boxes, the mixing permutation P also plays an important role. It ensures that
the S-boxes do not always operate on the same group of 6 bits. Again, [21] lists a number of criteria
used to choose the permutation P . If the permutation P was simply chosen at random then DES would be far less secure. The key expansion function. The DES key expansion function G takes as input the 56-bit key k and outputs 16 keys k1, . . . , k16, each 48-bits long. Each key ki consists of 48 bits chosen from the 56-bit key, with each ki using a di erent subset of bits from k. 4.2.2 Exhaustive search on DES: the DES challenges The DES algorithm. The complete DES algorithm is shown in Fig. 4.9. It consists of 16 iterations of the DES round cipher plus initial and final permutations called IP and FP. These permutations simply rearrange the 64 incoming and outgoing bits. The permutation FP is the inverse of IP. IP and FP have no cryptographic significance and were included for unknown reasons. Since bit permutations are slow in software, but fast in hardware, one theory is that IP and FP are intended to deliberately slow down software implementations of DES. Recall that an exhaustive search attack on a block cipher (E, D) (Section 4.1.1) refers to the and following attack: the adversary is given a small number of plaintext blocks x1, . . . , xQ X . The adversary finds k by trying all their encryption y1, . . . , yQ using a block cipher key k in K until it finds a key that maps all the given plaintext blocks to the given possible keys k K ciphertext blocks. If enough ciphertext blocks are given, then k is the only such key, and it will be found by the adversary. For block ciphers like DES and AES-128 three blocks are enough to ensure that with high probability there is a unique key mapping the given plaintext blocks to the given ciphertext blocks. We will see why in Section 4.7.2 where we discuss ideal ciphers and their properties. For now it su ces to know that given three plaintext/ciphertext blocks an attacker can use exhaustive search to find the secret key k. In 1974, when DES was designed, an exhaustive search attack on a key space of size 256 was believed to be infeasible. With improvements in computer hardware it was shown that a 56-bit is woefully inadequate. 124 Hàm F (ki, x) 32-bit x 48-bit k E 48 bits 6 6 6 6 6 6 6 6 S1 S2 S3 S4 S5 S6 S7 S8 4 4 4 4 4 4 4 4 32 bits P output Figure 4.8: The DES round function F (k, x) 12 / 27 122 Các S-box The$S\boxes$ 6 4 Các S-box là có d§ng Dan$Boneh$ 13 / 27 !{ { Si :
0, 1
0, 1
Si:${0,1}6$⟶${0,1}4$$$
}
} Ví dˆ d˜Ói ây là S5. NÎi dung 1 Mã khËi là gì? 2 Hª mã chu©n DES 3 Tßn công vét c§n 4 Hª mã khËi AES Tßn công vét c§n ∫ tìm khóa cıa mã
khËi Bài toán 15 / 27 • Cho mÎt sË c∞p input/output (mi, ci = E(k, mi)) vÓi i = 1, 2, 3.
Hãy tìm khóa k. • 64 64) BÍ ∑
Gi£ s˚ DES là mÎt hª mã l˛ t˜ng (256 hàm kh£ ngh‡ch ng®u nhiên
⇡i : 0, 1 { } !{ 0, 1
} V™y thì vÓi mÈi c∞p m, c có nhi∑u nhßt mÎt khóa k th‰a mãn c = DES(k, m) 16 / 27 vÓi xác sußt 1 99.5%. 1/256 ⇡ Tìm ki∏m vét c§n ∫ tìm khóa cho mã
khËi • VÓi hai c∞p DES (m1, c1 = DES(k, m1)) và
(m2, c2 = DES(k, m2)) xác sußt ∫ có k có duy nhßt là 1 1/271. ⇡ VÓi AES-128: cho hai c∞p input/output, xác sußt có k duy nhßt • 1 1/2128 17 / 27 • ⇡
V™y hai c∞p input/output là ı thông tin ∫ tìm ki∏m vét c§n
cho khóa. Th˚ thách DES
Cho các c∞p b£n rõ và b£n mã msg = "The unknown messages is : XXXX ... "
CT = c1 c2 c3 c4 56 th‰a mãn DES(k, mi) = ci vÓi i = 1, 2, 3. 18 / 27 Hãy tìm khóa k 0, 1
} 2{ 1997: DESCHALL project vÓi internet search – 96 ngày • 1998: EFF dùng máy DeepCrack – 3 ngày (250K $) • 1999: K∏t hÒp c£ DeepCrack và internet search – 22 giÌ • 2006: COPACOBANA (120 FPGA) – 7 ngày (10K $). • (128-bit khóa 272 ) Không nên dùng mã khËi 56 bit khóa !!
ngày) C£i ti∏n DES chËng tßn công vét c§n:
Triple-DES ‡nh nghæa
Xét E : 3 là mÎt hª mã khËi. Ta ‡nh nghæa hª mã khËi K ⇥ X ! X 3E : K ⇥ X ! X bi: Chú ˛:
N∏u k1 = k2 = k3 thì 3E = E 19 / 27 3E((k1, k2, k3), m) := E (k3, D (k2, E(k3, m))) Triple-DES: MÎt sË nh™n xét 20 / 27 Kích th˜Óc khóa là 3 56 = 168 bit, • ⇥ Ch™m gßp 3 l¶n DES. • Có th∫ tßn công trong thÌi gian 2118. • ⇡ • Define$$$$$$$2E($(k1,k2),$m)$=$$$E(k1$,$E(k2$,$m)$)$ $$$$key\len$=$112$bits$for$DES$ m$ c$ E(k2,(cid:6))$ E(k1,(cid:6))$ $ Hình: 2E ( (k1, k2), m ) := E ( k1, E(k2, m) ) Apack:$$$$M$=$(m1,…,$m10)$$,$$$C$=$(c1,…,c10).$
fi t˜ng tßn công double-DES:
• step$1:$$$build$table.$ 256$$ entries$ k0$=$00…00$
k1$=$00…01$
k2$=$00…10$
(cid:7)$
kN$=$11…11$ E(k0$,$M)$
E(k1$,$M)$
E(k2$,$M)$
(cid:7)$
E(kN$,$M)$ Dan$Boneh$ 21 / 27 E(k2, m) = D(k1, m) , E(k1, E(k2, m)) = c
$sort$on$2nd$column$ NÎi dung 1 Mã khËi là gì? 2 Hª mã chu©n DES 3 Tßn công vét c§n 4 Hª mã khËi AES 1999: NIST chÂn 5 hª mã cho vòng lo§i cuËi cùng. • 2000: NIST chÂn Rijndael ∫ thành chu©n AES ( ˜Òc thi∏t k∏ • Bø) Quá trình l¸a chÂn AES Kích th˜Óc khóa 128, 192, 256. Kích th˜Óc khËi: 128 bit. • 1997: NIST kêu gÂi ∑ xußt hª mã khËi chu©n mÓi • 23 / 27 • 1998: Có 15 ∑ xußt. 5 ∑ xußt b‡ khØng ‡nh có th∫ tßn công
sau ó. 2000: NIST chÂn Rijndael ∫ thành chu©n AES ( ˜Òc thi∏t k∏ • Bø) Quá trình l¸a chÂn AES Kích th˜Óc khóa 128, 192, 256. Kích th˜Óc khËi: 128 bit. • 1997: NIST kêu gÂi ∑ xußt hª mã khËi chu©n mÓi • • 1998: Có 15 ∑ xußt. 5 ∑ xußt b‡ khØng ‡nh có th∫ tßn công
sau ó. 23 / 27 1999: NIST chÂn 5 hª mã cho vòng lo§i cuËi cùng. • Quá trình l¸a chÂn AES Kích th˜Óc khóa 128, 192, 256. Kích th˜Óc khËi: 128 bit. • 1997: NIST kêu gÂi ∑ xußt hª mã khËi chu©n mÓi • • 1998: Có 15 ∑ xußt. 5 ∑ xußt b‡ khØng ‡nh có th∫ tßn công
sau ó. 1999: NIST chÂn 5 hª mã cho vòng lo§i cuËi cùng. • 23 / 27 • 2000: NIST chÂn Rijndael ∫ thành chu©n AES ( ˜Òc thi∏t k∏
Bø) Quá trình l¸a chÂn AES 1997: NIST kêu gÂi ∑ xußt hª mã khËi chu©n mÓi • • 1998: Có 15 ∑ xußt. 5 ∑ xußt b‡ khØng ‡nh có th∫ tßn công
sau ó. 1999: NIST chÂn 5 hª mã cho vòng lo§i cuËi cùng. • • 2000: NIST chÂn Rijndael ∫ thành chu©n AES ( ˜Òc thi∏t k∏
Bø) 23 / 27 Kích th˜Óc khóa 128, 192, 256. Kích th˜Óc khËi: 128 bit. • AES là mÎt m§ng thay th∏ và hoán v‡
không ph£i m§ng Feistel
AES$is$a$Subs\Perm$network$(not$Feistel)$ kn$ k1$ k2$ S1$ S1$ S1$ $ $ $ S2$
S3$ S2$
S3$ S2$
S3$ ⨁ ⨁ ⨁ $
t
u
p
n i $
t
u
p
t
u
o (cid:8)$ (cid:8) (cid:8) (cid:8) S8$ S8$ inversion$ perm.$
layer$ S8$
subs.$
layer$ Dan$Boneh$ 24 / 27 SÏ Á cıa AES-128 AES\128$schema 10$rounds$ 4$ $ $ $ $ ⨁ ⨁ ⨁ 4$ ⨁ input$ (cid:8)$ (1) ByteSub$
(2) ShinRow$
$ (1) ByteSub$
(2) ShinRow$
(3) MixColumn$ (1) ByteSub$
(2) ShinRow$
(3) MixColumn$ inver $ k0$ k1$ k2$ k9$ ⨁ k10$ 4$ key$ output$ key$expansion:$ 16$bytes$⟶176$bytes$ 16$bytes$ 4$ Dan$Boneh$ 25 / 27 The$round$func MixColumns: • • ShiORows:$$$ • MixColumns:$
$ Dan$Boneh$ 26 / 27 • ByteSub: S-box kích th˜Óc 1byte. ∫ d§ng b£ng 256 giá tr‡
(dπ tính toán).
• ByteSub:$$$$a$1$byte$S\box.$$$$256$byte$table$$$$$(easily$computable)$$ ShiftRow: • The$round$func • • ShiORows:$$$
• ShiORows:$$$ ShiftRow: • • Dan$Boneh$ Dan$Boneh$ 26 / 27 MixColumns:
• MixColumns:$
• MixColumns:$
$
$ Chú thích 27 / 27 Các Hình trong slides ˜Òc lßy t¯ khóa hÂc Crypto I cıa Dan
Boneh. M™t mã ˘ng dˆng
The Advanced Encryption Standard (AES) 1 / 46 4.2 Overview of the AES Algorithm 89 On October 2, 2000, NIST announced that it had chosen Rijndael as the AES. On November 26, 2001, AES was formally approved as a US federal standard. It is expected that AES will be the dominant symmetric-key algorithm for many commercial applications for the next few decades. It is also remarkable that in 2003 the US National Security Agency (NSA) announced that it allows AES to encrypt classified documents up to the level SECRET for all key lengths, and up to the TOP SECRET level for key lengths of either 192 or 256 bits. Prior to that date, only non-public algorithms had been used for the encryption of classified documents. The AES cipher is almost identical to the block cipher Rijndael. The Rijndael block Hª AES and key size vary between 128, 192 and 256 bits. However, the AES standard only
calls for a block size of 128 bits. Hence, only Rijndael with a block length of 128
bits is known as the AES algorithm. In the remainder of this chapter, we only discuss
the standard version of Rijndael with a block length of 128 bits. x 128 128/192/256 k AES 128 y As mentioned previously, three key lengths must be supported by Rijndael as this
was an NIST design requirement. The number of internal rounds of the cipher is a
function of the key length according to Table 4.1. 2 / 46 AES ˜Òc xây d¸ng d¸a trên mÎt sË phép toán trên tr˜Ìng h˙u
h§n. key lengths # rounds = nr 128 bit 10 192 bit 12 14 256 bit In contrast to DES, AES does not have a Feistel structure. Feistel networks do not encrypt an entire block per iteration, e.g., in DES, 64/2 = 32 bits are encrypted ‡nh nghæa (Tr˜Ìng)
MÎt tr˜Ìng F là mÎt t™p vÓi các tính chßt sau: • Các ph¶n t˚ cıa F t§o thành mÎt nhóm vÓi phép toán + vÓi
ph¶n t˚ Ïn v‡ là 0. • vÓi ph¶n t˚ Ïn v‡ là 1. ⇥ th‰a mãn • ⇥ Các ph¶n t˚ cıa F ngo§i tr¯ 0 t§o thành mÎt nhóm vÓi phép
toán
Các ph¶n t˚ cıa F cùng vÓi hai phép toán + và
lu™t phân phËi, t˘c là: 3 / 46 a F. (b + c) = (a b) + (a c), vÓi mÂi a, b, c ⇥ ⇥ ⇥ 2 Ví dˆ t§o thành mÎt • ⇥ 4 / 46 theo modun nguyên tË p là • ⇥ T™p sË th¸c R cùng vÓi hai phép toán + và
tr˜Ìng.
T™p Fp vÓi hai phép toán + và
mÎt tr˜Ìng. Tr˜Ìng này có h˙u h§n ph¶n t˚. i∑u kiªn tÁn t§i tr˜Ìng h˙u h§n ‡nh l˛
TÁn t§i tr˜Ìng cßp n n∏u n = pm vÓi p là sË nguyên tË và m là mÎt
sË nguyên d˜Ïng. SË p ˜Òc gÂi là ∞c sË cıa tr˜Ìng h˙u h§n. Ví dˆ SË ph¶n t˚ cıa tr˜Ìng F ˜Òc gÂi là cßp hay l¸c l˜Òng cıa
tr˜Ìng F . • • ) (cÙng gÂi là • TÁn t§i tr˜Ìng h˙u h§n có 11 ph¶n t˚ GF (11).
TÁn t§i tr˜Ìng h˙u h§n có 81 ph¶n t˚ GF (81).
TÁn t§i tr˜Ìng h˙u h§n có 256 ph¶n t˚ GF (28
tr˜Ìng AES). 5 / 46 Không tÁn t§i tr˜Ìng vÓi 12 ph¶n t˚. T§i sao? • Ki∫u tr˜Ìng h˙u h§n GF (pm ) m > 1 m = 1 Nh™n xét
Hai tr˜Ìng hay ˜Òc dùng trong m™t mã là GF (p) và GF (2m GF (pm ): tr˜Ìng m rÎng GF (p): tr˜Ìng nguyên tË Fp 6 / 46 ). Tr˜Ìng m rÎng GF (2m ) 1 Các ph¶n t˚ cıa GF (2m ) là các a th˘c: 1 x m Ví dˆ
Các ph¶n t˚ cıa tr˜Ìng GF (23 am + + a1 x + a0 = A(x) GF (2m ) · · · 2 . vÓi ai GF (2) = 2 0, 1
} { ) = GF (8) là các a th˘c A(x) = a2 x 2 + a1 x + a0 GF (23 ) có 23 = 8 ph¶n t˚: 1, x, GF (23 ) = { x 2 x + 1
x 2 + 1, + x, 7 / 46 0,
x 2,
x 2 + x + 1 } Câu h‰i , Làm th∏ nào ∫ tính toán (+, , /) trên GF (2m )? ⇥ 8 / 46 Tính toán nh˜ trên a th˘c thông th˜Ìng vÓi các hª sË ˜Òc tính
trên GF (p). CÎng và tr¯ Ví dˆ (Tính toán trên GF (23 )) + x + 1
+ 1 9 / 46 A(x) = x 2
B(x) = x 2
A(x) + B(x) = x Nhân Ví dˆ (Tính toán trên GF (23 )) + 1) A(x) ⇥ A(x) = x 2
B(x) = x 2
B(x) = (x 2
= x 4 + x + 1
+ 1
+ x + 1)(x 2
+ x 3 GF (23 ) + x + 1 /
2 10 / 46 0, 1, . . . , 6 Nh≠c l§i: vÓi tr˜Ìng nguyên tË GF (7) = { } 3 4 = 12 = 5 mod 7 · Phép nhân trên tr˜Ìng m rÎng )) ‡nh nghæa (Phép nhân trên tr˜Ìng m rÎng GF (2m
) và xét
Xét A(x), B(x) Ta s≥ chia lßy d˜ cho mÎt a th˘c bßt kh£ quy, là a th˘c t˜Ïng t¸
nh˜ sË nguyên tË. m GF (2m 2 i=0
X pi x i, pi P(x) = GF (2) 2 là mÎt a th˘c bßt kh£ quy. Phép nhân cıa hai ph¶n t˚ A(x), B(x)
có k∏t qu£ là 11 / 46 C(x) = A(x) B(x) mod P(x). · Phép nhân trên tr˜Ìng m rÎng Ví dˆ (Tính toán trên GF (23
A(x) = x 2
B(x) = x 2
B(x) = (x 2
= x 4 ))
+ x + 1
+ 1
+ x + 1)(x 2
+ x 3 A(x) + 1) ⇥ GF (23 ) + x + 1 /
2 Ta chÂn a th˘c bßt kh£ quy là P(x) = x 3 + x + 1 Khi ó A(x) 12 / 46 ·
+ x + 1)/(x 3 B(x) = x 2
+ x mod P(x)
+ x + 1) = x + 1; và d˜ x 2 + x. vì (x 4 + x 3 a th˘c bßt kh£ quy Không ph£i mÂi a th˘c ∑u bßt kh£ quy. Ví dˆ, • x 4 + x 3 + x + 1 = (x 2 + x + 1)(x 2 + 1) không ph£i là bßt kh£ quy. Trong AES, ng˜Ìi ta s˚ dˆng a th˘c bßt kh£ quy • 13 / 46 P(x) = x 8 + x 4 + x 3 + x + 1 Ph¶n t˚ ngh‡ch £o trong m rÎng
tr˜Ìng 1 1 (x) cıa A(x) GF (2m ) là ph¶n t˚ • 2 Ph¶n t˚ ngh‡ch £o A
th‰a mãn A(x) (x) = 1 mod P(x) A · 14 / 46 • T˜Ïng t¸ nh˜ trong tr˜Ìng nguyên tË, ph¶n t˚ ngh‡ch £o có
th∫ tính dùng thu™t toán Euclid m rÎng. 4.4 Internal Structure of AES 99 an inverse does not exist. However, for the AES S-Box, a substitution table is needed that is defined for every possible input value. Hence, the designers defined the S-Box such that the input value 0 is mapped to the output value 0. Y
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
1 74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
2 3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
3 2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
4 1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
5 ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
6 16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
7 79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
X 8 83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
9 DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
A FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
B 0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
C 0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
D 7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
E B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
F 5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C B£ng trên tính ngh‡ch £o trong GF (28 ). Ví dˆ, ngh‡ch £o cıa Example 4.7. From Table 4.2 the inverse of
+ x 6
x7 + x6 + x = (1100 0010)2 = (C2)hex = (xy) x 7 + x = (11000010)2 = (C2)hex = (X Y ) is given by the element in row C, column 2: ˜Òc cho bi ô t§i dòng C, cÎt 2: 15 / 46 (2F)hex = (0010 1111)2 = x5 + x3 + x2 + x + 1. This can be verified by multiplication: (x7 + x6 + x) (x5 + x3 + x2 + x + 1) 1 mod P(x). · Note that the table above does not contain the S-Box itself, which is a bit more complex and will be described in Sect. 4.4.1. As an alternative to using lookup tables, one can also explicitly compute inverses. The main algorithm for computing multiplicative inverses is the extended Euclidean algorithm, which is introduced in Sect. 6.3.1. (2F )hex = (00101111)2 = x 5 + x 3 + x 2 + x + 1. In the following, we examine the internal structure of AES. Figure 4.3 shows the graph of a single AES round. The 16-byte input A0, . . . , A15 is fed byte-wise into the SÏ l˜Òc l‡ch s˚ 1 Mars bi IBM
2 RC6 bi RSA Laboratories
3 Rijndael bi Joan Daemen và Vincent Rijmen
4 Serpent bi Ross Anderson, Eli Biham và Lars Knudsen
5 Twofish bi Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall và Neils Ferguson 1997: Kêu gÂi ∑ xußt Chu©n mã hóa nâng cao AES bi NIST • 1998: Có 15 thu™t toán ∑ xußt • Tháng 8 n´m 1999: ChÂn 5 thu™t toán vào vòng cuËi • 16 / 46 Tháng 10 n´m 2000: Rijndael ã ˜Òc chÂn làm AES • 4.2 Overview of the AES Algorithm 89 On October 2, 2000, NIST announced that it had chosen Rijndael as the AES. On November 26, 2001, AES was formally approved as a US federal standard. It is expected that AES will be the dominant symmetric-key algorithm for many commercial applications for the next few decades. It is also remarkable that in 2003 the US National Security Agency (NSA) announced that it allows AES to encrypt classified documents up to the level SECRET for all key lengths, and up to the TOP SECRET level for key lengths of either 192 or 256 bits. Prior to that date, only non-public algorithms had been used for the encryption of classified documents. AES The AES cipher is almost identical to the block cipher Rijndael. The Rijndael block
and key size vary between 128, 192 and 256 bits. However, the AES standard only
calls for a block size of 128 bits. Hence, only Rijndael with a block length of 128
bits is known as the AES algorithm. In the remainder of this chapter, we only discuss
the standard version of Rijndael with a block length of 128 bits. x 128 128/192/256 k AES 128 y K
128
192
256 SË vòng
10
12
14 As mentioned previously, three key lengths must be supported by Rijndael as this
was an NIST design requirement. The number of internal rounds of the cipher is a
function of the key length according to Table 4.1. 17 / 46 key lengths # rounds = nr 128 bit 10 192 bit 12 14 256 bit In contrast to DES, AES does not have a Feistel structure. Feistel networks do not encrypt an entire block per iteration, e.g., in DES, 64/2 = 32 bits are encrypted 4.3 Some Mathematics: A Brief Introduction to Galois Fields 91 Key k Plaintext
x Cßu trúc mÎt vòng cıa AES 0k Transform 0 Key Addition Layer Byte Substitution Layer ShiftRows Layer round 1 Diffusion Layer MixColumn Layer 1k Transform 1 Key Addition Layer 18 / 46 Byte Substitution Layer ShiftRows Layer round −1 n r MixColumn Layer k rn −1 Transform n −1 Key Addition Layer r Byte Substitution Layer last round ShiftRows Layer rn rkn n Transform Key Addition Layer r Ciphertext x y=AES( ) Chú ˛: Riêng vòng cuËi cùng không có thao tác MixColumn. • can add, subtract, multiply and invert. Before we introduce the definition of a field, we first need the concept of a a simpler algebraic structure, a group. 100 4 The Advanced Encryption Standard (AES) S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer
and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is
1 vòng: 128 bit ˜Òc tách thành 16 bytes
XORed with the intermediate result. We note that AES is a byte-oriented cipher.
8 = 128) 0A 1A 2A 3A 6A5A4A 7A 8A 12A 13A 14A 15A (16
10A
9A Byte Substitution s s s s s s s s s s s s s s s ⇥
11A
s 0B 1B 2B 3B 4B 5B 6B 7B 8B 9B 10B 11B 12B 13B 14B 15B ShiftRows MixColumn 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C 14C 15C Key Addition k i 1 19 / 46 This is in contrast to DES, which makes heavy use of bit permutation and can thus be considered to have a bit-oriented structure. In order to understand how the data moves through AES, we first imagine that the state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged in a four-by-four byte matrix: A0 A4 A8 A12 A1 A5 A9 A13 A2 A6 A10 A14 A3 A7 A11 A15 As we will see in the following, AES operates on elements, columns or rows of the current state matrix. Similarly, the key bytes are arranged into a matrix with four rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here is, as an example, the state matrix of a 192-bit key: 4 The Advanced Encryption Standard (AES) 102 On a bit level — and remember, the only thing that is ultimate of interest in encryp- tion is the manipulation of bits — this substitution can be described as: S(1100 0010) = (0010 0101). Even though the S-Box is bijective, it does not have any fixed points, i.e., there aren’t any input values Ai such that S(Ai) = Ai. Even the zero-input is not a fixed point: S(0000 0000) = (0110 0011). Example 4.9. Let’s assume the input to the Byte Substitution layer is (C2,C2, . . . ,C2) in hexadecimal notation. The output state is then 100 4 The Advanced Encryption Standard (AES) (25, 25, . . . , 25). S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer
and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is
XORed with the intermediate result. We note that AES is a byte-oriented cipher. Byte Substitution layer 3A 2A 0A 7A 1A 12A 10A 11A 14A 13A 6A5A4A 15A Byte Substitution s s s s s s s s s s s s s s 13B 14B 10B 11B 12B 15B 1B 4B 5B 6B 7B 0B 2B 3B 9B ShiftRows Hình: Dùng 16 S-box giËng nhau: S(Ai) = Bi MixColumn 1
i = B0i ; sau ó 11C 4C 6C 7C 2C 3C 9C 12C 13C 14C 15C (cid:3)(cid:1) 1C
(cid:4)(cid:1) 8C
(cid:3)(cid:1) (cid:10)(cid:11)(cid:11)(cid:4)(cid:5)(cid:7)
(cid:12)(cid:10)(cid:13)(cid:13)(cid:4)(cid:5)(cid:14) (cid:1)(cid:2)(cid:1)(cid:2)(cid:1)(cid:3)
(cid:4)(cid:5)(cid:6)(cid:7)(cid:8)(cid:9)(cid:7) 20 / 46 • ) và tính ngh‡ch £o A • 2 H‰i: B£ng S-box ˜Òc xây d¸ng th∏ nào?
GF (28
Tr£ lÌi: Coi Ai
˜a qua mÎt phép bi∏n Íi tuy∏n tính.
0C
10C
5C Key Addition k i The first part of the substitution is a Galois field inversion, the mathematics of 1 which were introduced in Sect. 4.3.2. For each input element Ai, the inverse is com- 1 This is in contrast to DES, which makes heavy use of bit permutation and can thus puted: B i = A , where both Ai and B i are considered elements in the field GF(28) i be considered to have a bit-oriented structure. with the fixed irreducible polynomial P(x) = x8 + x4 + x3 + x + 1. A lookup table In order to understand how the data moves through AES, we first imagine that the with all inverses is shown in Table 4.2. Note that the inverse of the zero element does state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged in a four-by-four byte matrix: not exist. However, for AES it is defined that the zero element Ai = 0 is mapped to A0 A4 A8 A12 itself. A1 A5 A9 A13 In the second part of the substitution, each byte B i is multiplied by a constant bit- A2 A6 A10 A14 matrix followed by the addition of a constant 8-bit vector. The operation is described A3 A7 A11 A15 by: As we will see in the following, AES operates on elements, columns or rows of the current state matrix. Similarly, the key bytes are arranged into a matrix with four rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here is, as an example, the state matrix of a 192-bit key: Bi Phép bi∏n Íi tuy∏n tính B0i 4.4 Internal Structure of AES 103 ! mod 2. + 1 0 0 0 1 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 1 b0
b1
b2
b3
b4
b5
b6
b7 b 0
b 1
b 2
b 3
b 4
b 5
b 6
b 7
1
1
0
0
0
1
1
0
1 (x). i Note that B = (b 7, . . . , b 0) is the bitwise vector representation of B i(x) = A
This second step is referred to as affine mapping. Let’s look at an example of how
the S-Box computations work. 21 / 46 Example 4.10. We assume the S-Box input Ai = (1100 0010)2 = (C2)hex. From Ta-
ble 4.2 we can see that the inverse is: 1 A i = B i = (2F)hex = (0010 1111)2. We now apply the B i bit vector as input to the affine transformation. Note that the least significant bit (lsb) b 0 of B i is at the rightmost position. Bi = (0010 0101) = (25)hex Thus, S((C2)hex) = (25)hex, which is exactly the result that is also given in the S-Box Table 4.3. If one computes both steps for all 256 possible input elements of the S-Box and stores the results, one obtains Table 4.3. In most AES implementations, in particular in virtually all software realizations of AES, the S-Box outputs are not explicitly computed as shown here, but rather lookup tables like Table 4.3 are used. However, for hardware implementations it is sometimes advantageous to realize the S-Boxes as digital circuits which actually compute the inverse followed by the affine map- ping. The advantage of using inversion in GF(28) as the core function of the Byte Substitution layer is that it provides a high degree of nonlinearity, which in turn provides optimum protection against some of the strongest known analytical attacks. The affine step “destroys” the algebraic structure of the Galois field, which in turn is needed to prevent attacks that would exploit the finite field inversion. In AES, the Diffusion layer consists of two sublayers, the ShiftRows transformation and the MixColumn transformation. We recall that diffusion is the spreading of the influence of individual bits over the entire state. Unlike the nonlinear S-Box, the Ví dˆ Gi£ s˚ input • Ai = (11000010)2 = (C2)hex GF (28 ) 2 Ta có • 1
i = B0i = (2F ) = (00101111)2
A GF (28 ) 2 Qua phép bi∏n Íi tuy∏n tính ta ˜Òc • 22 / 46 Bi = (0010 0101)2 = (25)hex 4.4 Internal Structure of AES 101 k0 k4 k8 k12 k16 k20 k1 k5 k9 k13 k17 k21 k2 k6 k10 k14 k18 k22 k3 k7 k11 k15 k19 k23 We discuss now what happens in each of the layers. As shown in Fig. 4.3, the first layer in each round is the Byte Substitution layer. The Byte Substitution layer can be viewed as a row of 16 parallel S-Boxes, each with 8 input and output bits. Note that all 16 S-Boxes are identical, unlike DES where eight different S-Boxes are used. In the layer, each state byte Ai is replaced, i.e., substituted, by another byte Bi: S(Ai) = Bi. The S-Box is the only nonlinear element of AES, i.e., it holds that ByteSub(A) + ByteSub(B) = ByteSub(A + B) for two states A and B. The S-Box substitution is a bijective mapping, i.e., each of the 28 = 256 possible input elements is one-to-one mapped to one output element. This allows us to uniquely reverse the S-Box, which is needed for decryption. In software implementations the S-Box is usually realized as a 256-by-8 bit lookup table with fixed entries, as given in Table 4.3. S-box: S((C2)hex ) = S(C, 2) = (25)he x .
y 0 8 7 2 6 4 3 1 5 9 A B C D E F
0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76
1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0
2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15
3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75
4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84
5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF
6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8
7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2
x 8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73
9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB
A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79
B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08
C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A
D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E
E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF
F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16 23 / 46 Example 4.8. Let’s assume the input byte to the S-Box is Ai = (C2)hex, then the substituted value is S((C2)hex) = (25)hex. 100 4 The Advanced Encryption Standard (AES) S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer
and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is
XORed with the intermediate result. We note that AES is a byte-oriented cipher. Diffusion Layer = Shift Rows và Mix
Column
14A
13A
12A 6A5A4A 10A 11A 1A 3A 7A 0A 8A 9A 2A 15A Byte Substitution s s s s s s s s s s s s s s s s 0B 1B 2B 3B 4B 5B 6B 7B 8B 9B 10B 11B 12B 13B 14B 15B ShiftRows MixColumn 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C 14C 15C Key Addition 24 / 46 k i 1 This is in contrast to DES, which makes heavy use of bit permutation and can thus be considered to have a bit-oriented structure. In order to understand how the data moves through AES, we first imagine that the state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged in a four-by-four byte matrix: A0 A4 A8 A12 A1 A5 A9 A13 A2 A6 A10 A14 A3 A7 A11 A15 As we will see in the following, AES operates on elements, columns or rows of the current state matrix. Similarly, the key bytes are arranged into a matrix with four rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here is, as an example, the state matrix of a 192-bit key: 104 4 The Advanced Encryption Standard (AES) 100 4 The Advanced Encryption Standard (AES) diffusion layer performs a linear operation on state matrices A, B, i.e., DIFF(A) + DIFF(B) = DIFF(A + B). S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is XORed with the intermediate result. We note that AES is a byte-oriented cipher. 104 4 The Advanced Encryption Standard (AES) 6A5A4A 13A 10A 1A 8A 0A 3A 7A 9A 2A 15A diffusion layer performs a linear operation on state matrices A, B, i.e., DIFF(A) +
12A
11A
14A
Shift Rows
DIFF(B) = DIFF(A + B).
Byte Substitution s s s s s s s s s s s s s s s 13B 10B 14B 11B 12B 15B 8B 7B 9B 6B 0B 1B 2B 3B 4B The ShiftRows transformation cyclically shifts the second row of the state matrix
by three bytes to the right, the third row by two bytes to the right and the fourth
row by one byte to the right. The first row is not changed by the ShiftRows trans-
s
formation. The purpose of the ShiftRows transformation is to increase the diffusion
properties of AES. If the input of the ShiftRows sublayer is given as a state matrix
5B
B = (B0, B1, . . . , B15): ShiftRows B0 B4 B8 B12
B1 B5 B9 B13
B2 B6 B10 B14
B3 B7 B11 B15 MixColumn The ShiftRows transformation cyclically shifts the second row of the state matrix
by three bytes to the right, the third row by two bytes to the right and the fourth
row by one byte to the right. The first row is not changed by the ShiftRows trans-
formation. The purpose of the ShiftRows transformation is to increase the diffusion
properties of AES. If the input of the ShiftRows sublayer is given as a state matrix
B = (B0, B1, . . . , B15): the output is the new state: 0C 1C 2C 7C 8C 5C 10C 13C (4.1) no shift
14C
15C
one position left shift
two positions left shift
three positions left shift B0 B4 B8 B12
9C
12C
11C
B5 B9 B13 B1
B10 B14 B2 B6
B15 B3 B7 B11 B0 B4 B8 B12
3C
6C
4C
B1 B5 B9 B13
B2 B6 B10 B14
B3 B7 B11 B15
the output is the new state: 25 / 46 ! no shift B0 B4 B8 B12 Key Addition k i one position left shift B5 B9 B13 B1 The MixColumn step is a linear transformation which mixes each column of the (4.1) two positions left shift B10 B14 B2 B6 state matrix. Since every input byte influences four output bytes, the MixColumn three positions left shift B15 B3 B7 B11 operation is the major diffusion element in AES. The combination of the ShiftRows 1 and MixColumn layer makes it possible that after only three rounds every byte of the state matrix depends on all 16 plaintext bytes. This is in contrast to DES, which makes heavy use of bit permutation and can thus In the following, we denote the 16-byte input state by B and the 16-byte output be considered to have a bit-oriented structure. state by C: The MixColumn step is a linear transformation which mixes each column of the MixColumn(B) = C, In order to understand how the data moves through AES, we first imagine that the state matrix. Since every input byte influences four output bytes, the MixColumn state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged where B is the state after the ShiftRows operation as given in Expression (4.1). operation is the major diffusion element in AES. The combination of the ShiftRows in a four-by-four byte matrix: Now, each 4-byte column is considered as a vector and multiplied by a fixed and MixColumn layer makes it possible that after only three rounds every byte of 4 4 matrix. The matrix contains constant entries. Multiplication and addition of the state matrix depends on all 16 plaintext bytes. A0 A4 A8 A12 In the following, we denote the 16-byte input state by B and the 16-byte output the coefficients is done in GF(28). As an example, we show how the first four output A1 A5 A9 A13 bytes are computed: state by C: A2 A6 A10 A14 MixColumn(B) = C, A3 A7 A11 A15 where B is the state after the ShiftRows operation as given in Expression (4.1). Now, each 4-byte column is considered as a vector and multiplied by a fixed As we will see in the following, AES operates on elements, columns or rows of 4 4 matrix. The matrix contains constant entries. Multiplication and addition of the current state matrix. Similarly, the key bytes are arranged into a matrix with four the coefficients is done in GF(28). As an example, we show how the first four output rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here bytes are computed: is, as an example, the state matrix of a 192-bit key: Mix Column Là mÎt phép bi∏n Íi tuy∏n tính bi∏n Íi • MixColumn(B) = C • MÈi cÎt 4 byte ˜Òc xem nh˜ mÎt vector, và ˜Òc nhân vÓi
mÎt ma tr™n cË ‡nh tr˜Óc. • ). Phép cÎng và phép nhân các hª sË ˜Òc th¸c hiªn trong
GF (28
Ma tr™n cıa phép bi∏n Íi tuy∏n tính MixColumn là • 1 0 26 / 46 02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02 C
A B
@ 100 4 The Advanced Encryption Standard (AES) S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is XORed with the intermediate result. We note that AES is a byte-oriented cipher. 0A 1A 2A 3A 6A5A4A 7A 8A 9A 10A 11A Ví dˆ
14A
13A
12A 15A Byte Substitution s s s s s s s s s s s s s s s s 0B 1B 2B 3B 4B 5B 6B 7B 8B 9B 10B 11B 12B 13B 14B 15B ShiftRows MixColumn 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C 14C 15C Key Addition 1 27 / 46 This is in contrast to DES, which makes heavy use of bit permutation and can thus be considered to have a bit-oriented structure. In order to understand how the data moves through AES, we first imagine that the state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged in a four-by-four byte matrix: A0 A4 A8 A12 A1 A5 A9 A13 A2 A6 A10 A14 A3 A7 A11 A15 As we will see in the following, AES operates on elements, columns or rows of the current state matrix. Similarly, the key bytes are arranged into a matrix with four rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here is, as an example, the state matrix of a 192-bit key: = 0 1 0 1 1 0
k i 02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02 B0
B5
B10
B15 C
A B
@ C
A B
@ C
A C0
C1
C2
C3
B
@
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr Ví dˆ Gi£ s˚ input cıa MixColumn là • B = (25, 25, . . . , 25). • 25 và 03 25: Do ma tr™n MixColumn, ta chø c¶n tính toán theo a th˘c
trong GF (28 ) vÓi 02 02 + 1) · 03 + 1) · + 1) 28 / 46 ·
(x 5
25 = x
·
= x 6
+ x 3
25 = (x + 1)
·
+ x 3
= (x 6
+ x 5
= x 5 ·
+ x 2
+ x,
(x 5
+ x 2
+ x) + (x 5
+ x 2
+ x 3 + x 2
+ x + 1 Ví dˆ (ti∏p) Th¸c hiªn phép cÎng trong GF (28 ) ta ˜Òc k∏t qu£ cıa C: • 01 1 + + · 01 x 5
x 5 x 2
x 2 1 + + · 02 x + + · 03 x 5 + · x 3
+x 3
x 5 x 2
x 2 1
1 25 =
25 =
25 = x 6
25 = x 6
Ci = + +x+
+ V™y output cıa C là: • 29 / 46 C = (25, 25, . . . , 25). 100 4 The Advanced Encryption Standard (AES) S-Box. The 16-byte output B0, . . . , B15 is permuted byte-wise in the ShiftRows layer and mixed by the MixColumn transformation c(x). Finally, the 128-bit subkey ki is XORed with the intermediate result. We note that AES is a byte-oriented cipher. 0A 1A 2A 3A 6A5A4A 7A 8A 9A 10A 11A 12A 13A 14A 15A Byte Substitution s s s s s s s s s s s s s s s s 0B 1B 2B 3B 4B 5B 6B 7B 8B 9B 10B 11B 12B 13B 14B 15B ShiftRows MixColumn Key Addition Layer 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C 14C 15C Key Addition k i 1
Input: GÁm 16-byte ma tr™n C và 16-byte khóa con ki
Output: C • ki • This is in contrast to DES, which makes heavy use of bit permutation and can thus
Các khóa con ˜Òc sinh trong thı tˆc m rÎng khóa (Key
be considered to have a bit-oriented structure.
schedule). 30 / 46 In order to understand how the data moves through AES, we first imagine that the
state A (i.e., the 128-bit data path) consisting of 16 bytes A0, A1, . . . , A15 is arranged
in a four-by-four byte matrix: A0 A4 A8 A12 A1 A5 A9 A13 A2 A6 A10 A14 A3 A7 A11 A15 As we will see in the following, AES operates on elements, columns or rows of the current state matrix. Similarly, the key bytes are arranged into a matrix with four rows and four (128-bit key), six (192-bit key) or eight (256-bit key) columns. Here is, as an example, the state matrix of a 192-bit key: • 4.4 Internal Structure of AES 107 K KKK K K K K K K K K K K K K 0 1 2 3 11 12 13 7 4 5 6 8 9 15 10 14 32 32 32 32 W[0] W[1] W[2] W[3] round key 0 g g i function of round 32 W[4] W[5] W[6] W[7] round key 1 3V2V1V0V 8 8 8 8 4.4 Internal Structure of AES 107 Key schedule cho AES vÓi khóa 128 bit .
.
.
. .
.
.
. .
.
.
. K KKK 0 1 2 3 K K K K K K K K K K K K
9 10 11 12 13 14 4 5 6 7 8 15 2V 1V 3V 0V 32 32 32 32 W[36] W[37] W[38] W[39] round key 9 W[0] W[1] W[2] W[3] round key 0 S S S S g RC[i] g 8 32 · · · i
g
function of round 32 W[40] W[41] W[42] W[43] round key 10 W[4] W[5] W[6] W[7] round key 1 3V2V1V0V 8 8 8 8 .
.
.
. .
.
.
. .
.
.
. 2V 0V 3V 1V W[36] W[39] W[38] W[37] round key 9 S S • g computed as follows. As can be seen in the figure, the leftmost word of a subkey
W [4i], where i = 1, . . . , 10, is computed as:
S
)) bi S
W [4i] = W [4(i 1)] + g(W [4i 1]). RC[i] 8 32 Here g() is a nonlinear function with a four-byte input and output. The remaining
three words of a subkey are computed recursively as: • Có 10 vòng và 11 l¶n Key Addition Layer; mÈi Key Addition
Layer c¶n khóa con 128 bit;
Các khóa con này ˜Òc chia thành W [0], W [1], . . . , W [43],
và ˜Òc tính (trên GF (28 1] +W [4(i 1) + j],
31 / 46 W[40] W[41] W[42] W[43] round key 10
where i = 1, . . . , 10 and j = 1, 2, 3. The function g() rotates its four input bytes, W [4i] = W [4(i
W [4i + j] = W [4i + j 1)] + g(W [4i
1] + W [4(i 1]).
1) + j]
W [4i + j] = W [4i + j performs a byte-wise S-Box substitution, and adds a round coefficient RC to it. The round coefficient is an element of the Galois field GF(28), i.e, an 8-bit value. It is only added to the leftmost byte in the function g(). The round coefficients vary from computed as follows. As can be seen in the figure, the leftmost word of a subkey round to round according to the following rule: W [4i], where i = 1, . . . , 10, is computed as: W [4i] = W [4(i 1)] + g(W [4i 1]). Here g() is a nonlinear function with a four-byte input and output. The remaining three words of a subkey are computed recursively as: W [4i + j] = W [4i + j 1] +W [4(i 1) + j], where i = 1, . . . , 10 and j = 1, 2, 3. The function g() rotates its four input bytes, performs a byte-wise S-Box substitution, and adds a round coefficient RC to it. The round coefficient is an element of the Galois field GF(28), i.e, an 8-bit value. It is only added to the leftmost byte in the function g(). The round coefficients vary from round to round according to the following rule: 4.4 Internal Structure of AES 107 K KKK K K K K K K K K K K K K 0 1 2 3 12 13 11 7 5 4 6 9 8 15 10 14 32 32 32 32 W[0] W[1] W[2] W[3] round key 0 g Hàm g vòng th˘ i s˚ dˆng RC[i] i
g
function of round 32 W[4] W[5] W[6] W[7] round key 1 3V2V1V0V 8 8 8 8 . . . . . . . . . . . . 2V 1V 3V 0V = (00000001)2,
= (00000010)2,
= (00000100)2, W[36] W[37] W[38] W[39] round key 9 S S S S g RC[i] 8 32 32 / 46 W[40] W[41] W[42] W[43] round key 10 RC[1] = x 0
RC[2] = x 1
RC[3] = x 2
...
RC[10] = x 9 = (00110110)2. computed as follows. As can be seen in the figure, the leftmost word of a subkey W [4i], where i = 1, . . . , 10, is computed as: W [4i] = W [4(i 1)] + g(W [4i 1]). Here g() is a nonlinear function with a four-byte input and output. The remaining three words of a subkey are computed recursively as: W [4i + j] = W [4i + j 1] +W [4(i 1) + j], where i = 1, . . . , 10 and j = 1, 2, 3. The function g() rotates its four input bytes, performs a byte-wise S-Box substitution, and adds a round coefficient RC to it. The round coefficient is an element of the Galois field GF(28), i.e, an 8-bit value. It is only added to the leftmost byte in the function g(). The round coefficients vary from round to round according to the following rule: 4.4 Internal Structure of AES 109 KKKK K KKKKKKKKKKKKKKK K K K K 2 1 0 3 4 11 12 13 17 18 19 15 16 6 8 5 9 7 22 20 21 23 10 14 32 32 32 32 32 32 W[0] W[1] W[2] W[3] W[4] W[5] g g i function of round 32 AES-192: Key schedule 3V2V1V0V W[6] W[7] W[8] W[9] W[10] W[11] 8 8 8 8 4.4 Internal Structure of AES 109 2V 1V 3V 0V .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. K KKKKKKKKKKKKKKK KKKK
1 0 2 3 4 11 12 13 18 19 16 15 17 7 8 6 9 5 K K K K
21 20 22 23 10 14 32 32 32 32 32 32 S S S S W[0] W[1] W[2] W[3] W[4] W[5] RC[i] W[42] W[43] W[44] W[45] W[46] W[47] 8 g g 32 · · · 32 W[48] g
i
function of round
W[49] W[50] W[51] 3V2V1V0V W[6] W[7] W[8] W[9] W[10] W[11] 8 8 8 8 2V 1V 3V 0V .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. why such an implementation on a device with limited memory resources, such as a
smart card, is sometimes not desireable. S S S S RC[i] W[47] W[46] W[44] W[45] W[43] W[42] AES vÓi 192 bit có 12 vòng, v™y c¶n 13 Key Addition layer. • 8 g 32 • MÈi Key Addition Layer c¶n 128 bit khóa; V™y c¶n 52 khóa
con W [0], . . . , W [51] khóa con 32 bit = 4 byte (4 13 = 52). ⇥ W[48] W[49] W[50] W[51] 33 / 46 why such an implementation on a device with limited memory resources, such as a smart card, is sometimes not desireable. (decryption) of a plaintext (ciphertext). Please note that when decrypting cipher- texts, the last subkey is XORed first with the ciphertext. Therefore, it is required to recursively derive all subkeys first and then start with the decryption of a ciphertext and the on-the-fly generation of subkeys. As a result of this overhead, the decryption of a ciphertext is always slightly slower than the encryption of a plaintext when the on-the-fly generation of subkeys is used. AES-256: Key schedule vòng 1 110 4 The Advanced Encryption Standard (AES) KKKK
1
3 0 2 K K K K K K K K K K K K K K K K K K K K K K K K K K K K31
17 18 30 29 28 11 13 14 20 21 22 23 24 25 26 10 12 15 16 19 27 9 4 5 6 7 8 32 32 32 32 32 32 32 32 W[0] W[1] W[2] W[3] W[4] W[5] W[6] W[7] g h W[8] W[9] W[10] W[11] W[12] W[13] W[14] W[15] .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. .
.
.
. W[48] W[49] W[50] W[51] W[52] W[53] W[54] W[55] 34 / 46 g g i function of round h −function 32 32 V0 V1 V2 V3 V0 V1 V2 V3 8 8 8 8 S S S S V1 V2 V3 V0 W[56] W[57] W[58] W[59] 32 S S S S RC[i] 8 32 Because AES is not based on a Feistel network, all layers must actually be in- verted, i.e., the Byte Substitution layer becomes the Inv Byte Substitution layer, the ShiftRows layer becomes the Inv ShiftRows layer, and the MixColumn layer becomes Inv MixColumn layer. However, as we will see, it turns out that the inverse layer operations are fairly similar to the layer operations used for encryption. In ad- AES-256: Key schedule vòng cuËi 35 / 46 110 4 The Advanced Encryption Standard (AES) KKKK 1 0 2 3 K K K K K K K K K K K K K K K K K K K K K K K K K K K K31 24 27 26 16 15 14 12 11 10 13 30 29 19 17 22 21 20 28 18 23 25 6 5 7 9 8 4 32 32 32 32 32 32 32 32 W[0] W[1] W[2] W[3] W[4] W[5] W[6] W[7] g h W[8] W[9] W[10] W[11] W[12] W[13] W[14] W[15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . W[48] W[49] W[50] W[51] W[52] W[53] W[54] W[55] AES256: hàm g và h g i
g
function of round h
−function 32 32 V0 V1 V2 V3 V0 V1 V2 V3 8 8 8 8 S S S S V1 V2 V3 V0 W[56] W[57] W[58] W[59] 32 S S S S RC[i] 8 32 36 / 46 Because AES is not based on a Feistel network, all layers must actually be in- verted, i.e., the Byte Substitution layer becomes the Inv Byte Substitution layer, the ShiftRows layer becomes the Inv ShiftRows layer, and the MixColumn layer becomes Inv MixColumn layer. However, as we will see, it turns out that the inverse layer operations are fairly similar to the layer operations used for encryption. In ad- 4.5 Decryption 111 dition, the order of the subkeys is reversed, i.e., we need a reversed key schedule. A block diagram of the decryption function is shown in Fig. 4.8. Ciphertext y knr Transform Key Addition Layer rn Inv ShiftRows Layer inverse of round n r Inv Byte Substitution 4.5 Decryption 111 n k r −1 n Transform −1 Key Addition Layer r dition, the order of the subkeys is reversed, i.e., we need a reversed key schedule. A Inv MixColumn Layer block diagram of the decryption function is shown in Fig. 4.8. inverse of round −1 n r Inv ShiftRows Layer Ciphertext Inv Byte Substitution y Transform Key Addition Layer rn 4.5 Decryption knr
111 SÏ Á gi£i mã Inv ShiftRows Layer inverse of round n r k1 dition, the order of the subkeys is reversed, i.e., we need a reversed key schedule. A
block diagram of the decryption function is shown in Fig. 4.8. Transform 1 Key Addition Layer Inv Byte Substitution Inv MixColumn Layer k r −1
n inverse of round 1 Ciphertext
y Transform −1 Key Addition Layer n
r Inv ShiftRows Layer Inv MixColumn Layer knr Inv Byte Substitution Transform rn Key Addition Layer
inverse of round −1 n r Inv ShiftRows Layer Inv ShiftRows Layer inverse of round n r k0 Transform 0 Key Addition Layer Inv Byte Substitution · · · Inv Byte Substitution k Key k r −1
n Hình: Vòng n 1 Plaintext
−1
y
AES ( ) x= Transform −1 n
r Hình: Vòng n
Key Addition Layer Inv MixColumn Layer Hình: Vòng 1 inverse of round −1 n r k1 Inv ShiftRows Layer Transform 1 Key Addition Layer Inv Byte Substitution Inv MixColumn Layer inverse of round 1 37 / 46 Since the last encryption round does not perform the MixColum operation, the
first decryption round also does not contain the corresponding inverse layer. All
other decryption rounds, however, contain all AES layers. In the following, we dis-
Inv ShiftRows Layer
cuss the inverse layers of the general AES decryption round (Fig. 4.9). Since the Inv Byte Substitution k1 k0 Transform 1 Key Addition Layer Transform 0 Key Addition Layer Inv MixColumn Layer k Key inverse of round 1 Inv ShiftRows Layer Plaintext −1 y AES ( ) x= Inv Byte Substitution k0 Transform 0 Key Addition Layer Since the last encryption round does not perform the MixColum operation, the k Key first decryption round also does not contain the corresponding inverse layer. All Plaintext other decryption rounds, however, contain all AES layers. In the following, we dis- −1 y AES ( ) x= cuss the inverse layers of the general AES decryption round (Fig. 4.9). Since the Since the last encryption round does not perform the MixColum operation, the first decryption round also does not contain the corresponding inverse layer. All other decryption rounds, however, contain all AES layers. In the following, we dis- cuss the inverse layers of the general AES decryption round (Fig. 4.9). Since the 112 4 The Advanced Encryption Standard (AES) XOR operation is its own inverse, the key addition layer in the decryption mode is the same as in the encryption mode: it consists of a row of plain XOR gates. Key Addition k i 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 10C 11C 12C 13C 14C 15C InvMixColumn InvShiftRows 0B 13B 10B 7B 14B1B4B 11B 8B 5B 2B 15B 12B 9B 6B 3B InvSubBytes s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 s−1 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 10A 11A 12A 13A 14A 15A 1 Hình: MÈi vòng trong sÏ Á gi£i mã 38 / 46 After the addition of the subkey, the inverse MixColumn step is applied to the state (again, the exception is the first decryption round). In order to reverse the MixCol- umn operation, the inverse of its matrix must be used. The input is a 4-byte column of the State C which is multiplied by the inverse 4 4 matrix. The matrix contains constant entries. Multiplication and addition of the coefficients is done in GF(28). 0E 0B 0D 09 B0 C0 09 0E 0B 0D B1 C1 = 0D 09 0E 0B B2 C2 0B 0D 09 0E B3 C3 The second column of output bytes (B4, B5, B6, B7) is computed by multiplying the four input bytes (C4,C5,C6,C7) by the same constant matrix, and so on. Each value InvMixColumn: Hàm ng˜Òc cıa
MixColumn Là phép bi∏n Íi ng˜Òc cıa MixColumn • InvMixColumn(C) = B • ); Phép cÎng và phép nhân các hª sË ˜Òc th¸c hiªn trong
GF (28
Ma tr™n cıa phép bi∏n Íi tuy∏n tính InvMixColumn là • 1 0 39 / 46 0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E C
A B
@ 4.5 Decryption 113 Bi and Ci is an element from GF(28). Also, the constants are elements from GF(28). The notation for the constants is hexadecimal and is the same as was used for the MixColumn layer, for example: 4.5 Decryption 113 0B = (0B)hex = (0000 1011)2 = x3 + x + 1. Bi and Ci is an element from GF(28). Also, the constants are elements from GF(28). Additions in the vector–matrix multiplication are bitwise XORs. The notation for the constants is hexadecimal and is the same as was used for the MixColumn layer, for example: 0B = (0B)hex = (0000 1011)2 = x3 + x + 1. In order to reverse the ShiftRows operation of the encryption algorithm, we must Additions in the vector–matrix multiplication are bitwise XORs. shift the rows of the state matrix in the opposite direction. The first row is not changed by the inverse ShiftRows transformation. If the input of the ShiftRows sublayer is given as a state matrix B = (B0, B1, . . . , B15): B0 B4 B8 B12 InvShiftRows: Hàm ng˜Òc cıa ShiftRows B1 B5 B9 B13
In order to reverse the ShiftRows operation of the encryption algorithm, we must
B2 B6 B10 B14
shift the rows of the state matrix in the opposite direction. The first row is not
B3 B7 B11 B15
changed by the inverse ShiftRows transformation. If the input of the ShiftRows
sublayer is given as a state matrix B = (B0, B1, . . . , B15): the inverse ShiftRows sublayer yields the output: ! no shift
one position right shift
two positions right shift
three positions right shift B0 B4 B8 B12
B13 B1 B5 B9
B10 B14 B2 B6
B7 B11 B15 B3 B0 B4 B8 B12
B1 B5 B9 B13
B2 B6 B10 B14
B3 B7 B11 B15
the inverse ShiftRows sublayer yields the output: 40 / 46 two positions right shift B0 B4 B8 B12
B13 B1 B5 B9
B10 B14 B2 B6 such that: three positions right shift B7 B11 B15 B3 Ai = S 1(Bi) = S 1(S(Ai)), where Ai and Bi are elements of the state matrix. The entries of the inverse S-Box are given in Table 4.4. For readers who are interested in the details of how the entries of inverse S-Box The inverse S-Box is used when decrypting a ciphertext. Since the AES S-Box is are constructed, we provide a derivation. However, for a functional understanding a bijective, i.e., a one-to-one mapping, it is possible to construct an inverse S-Box of AES, the remainder of this section can be skipped. In order to reverse the S- such that: Box substitution, we first have to compute the inverse of the affine transformation. For this, each input byte Bi is considered an element of GF(28). The inverse affine Ai = S 1(Bi) = S 1(S(Ai)), transformation on each byte Bi is defined by: where Ai and Bi are elements of the state matrix. The entries of the inverse S-Box are given in Table 4.4. For readers who are interested in the details of how the entries of inverse S-Box are constructed, we provide a derivation. However, for a functional understanding of AES, the remainder of this section can be skipped. In order to reverse the S- Box substitution, we first have to compute the inverse of the affine transformation. For this, each input byte Bi is considered an element of GF(28). The inverse affine transformation on each byte Bi is defined by: 4 The Advanced Encryption Standard (AES) 102 On a bit level — and remember, the only thing that is ultimate of interest in encryp- tion is the manipulation of bits — this substitution can be described as: S(1100 0010) = (0010 0101). Even though the S-Box is bijective, it does not have any fixed points, i.e., there aren’t any input values Ai such that S(Ai) = Ai. Even the zero-input is not a fixed point: S(0000 0000) = (0110 0011). Example 4.9. Let’s assume the input to the Byte Substitution layer is (C2,C2, . . . ,C2) in hexadecimal notation. The output state is then (25, 25, . . . , 25). the S-Box entries are constructed, a more detailed description now follows. This description, however, is not necessary for a basic understanding of AES, and the
remainder of this subsection can be skipped without problem. Unlike the DES S-
Boxes, which are essentially random tables that fulfill certain properties, the AES
InvSubBytes: Hàm ng˜Òc cıa SubBytes
S-Boxes have a strong algebraic structure. An AES S-Box can be viewed as a two-
step mathematical transformation (Fig. 4.4). (cid:3)(cid:1) (cid:4)(cid:1) (cid:3)(cid:1) (cid:10)(cid:11)(cid:11)(cid:4)(cid:5)(cid:7)
(cid:12)(cid:10)(cid:13)(cid:13)(cid:4)(cid:5)(cid:14) (cid:1)(cid:2)(cid:1)(cid:2)(cid:1)(cid:3)
(cid:4)(cid:5)(cid:6)(cid:7)(cid:8)(cid:9)(cid:7) Ta nh≠c l§i phép toán SubBytes: • ∫ tính InvSubBytes, ta tính ng˜Òc l§i: • 1 41 / 46 Bi Ai B0i ! not exist. However, for AES it is defined that the zero element Ai = 0 is mapped to itself. In the second part of the substitution, each byte B i is multiplied by a constant bit- matrix followed by the addition of a constant 8-bit vector. The operation is described by: !
The first part of the substitution is a Galois field inversion, the mathematics of
which were introduced in Sect. 4.3.2. For each input element Ai, the inverse is com-
, where both Ai and B i are considered elements in the field GF(28)
puted: B i = A
i
with the fixed irreducible polynomial P(x) = x8 + x4 + x3 + x + 1. A lookup table
with all inverses is shown in Table 4.2. Note that the inverse of the zero element does 114 4 The Advanced Encryption Standard (AES) y 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB 1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E 3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92 5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84 6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06 7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B x 8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E Bi A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B
B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4
C 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F
InvSubBytes: Bi∏n Íi tuy∏n tính ng˜Òc
D 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF
E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61
B0i
F 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D ! + mod 2, 0 1 0 1 0 0 1 0
0 0 1 0 1 0 0 1
1 0 0 1 0 1 0 0
0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1
1 0 0 1 0 0 1 0
0 1 0 0 1 0 0 1
1 0 1 0 0 1 0 0 b0
b1
b2
b3
b4
b5
b6
b7 b 0
b 1
b 2
b 3
b 4
b 5
b 6
b 7
0
0
0
0
0
1
0
1
where (b7, . . . , b0) is the bitwise vector representation of Bi(x), and (b 7, . . . , b 0) the
result after the inverse affine transformation. 42 / 46 1 be reversed. For this, note that Ai = (A In the second step of the inverse S-Box operation, the Galois field inverse has to
1. This means that the inverse operation
) i is reversed by computing the inverse again. In our notation we thus have to compute 1 GF(28) Ai = (B i) with the fixed reduction polynomial P(x) = x8 + x4 + x3 + x + 1. Again, the zero ele- ment is mapped to itself. The vector Ai = (a7, . . . , a0) (representing the field element a7x7 + + a1x + a0) is the result of the substitution: · · · Ai = S 1(Bi). Since decryption round one needs the last subkey, the second decryption round needs the second-to-last subkey and so on, we need the subkey in reversed order as shown in Fig. 4.8. In practice this is mainly achieved by computing the entire key schedule first and storing all 11, 13 or 15 subkeys, depending on the number or Ai InvSubByte: B0i ! 1 GF (28) • 2 Ta có Ai = (B0i )
Ví dˆ, ngh‡ch £o cıa • (2F )hex = (00101111)2 = x 5 + x 3 + x 2 + x + 1. 43 / 46 là x 7 + x 6 + x = (11000010)2 = (C2)hex 114 4 The Advanced Encryption Standard (AES) B£ng tính InvSubBytes y 8 5 6 2 1 3 0 4 9 A B C D E F
7
0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB
1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB
2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E
3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25
4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92
5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84
6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06
7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B
x 8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73
9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E
A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B
B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4
C 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F
D 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF
E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61
F 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D 44 / 46 0 1 0 1 0 0 1 0 0 b0 b 0 0 0 1 0 1 0 0 1 0 b1 b 1 1 0 0 1 0 1 0 0 0 b2 b 2 0 1 0 0 1 0 1 0 0 b3 b 3 + mod 2, 0 0 1 0 0 1 0 1 0 b4 b 4 1 0 0 1 0 0 1 0 1 b5 b 5 0 1 0 0 1 0 0 1 0 b6 b 6 1 0 1 0 0 1 0 0 1 b7 b 7 where (b7, . . . , b0) is the bitwise vector representation of Bi(x), and (b 7, . . . , b 0) the result after the inverse affine transformation. In the second step of the inverse S-Box operation, the Galois field inverse has to 1 1. This means that the inverse operation be reversed. For this, note that Ai = (A ) i is reversed by computing the inverse again. In our notation we thus have to compute 1 GF(28) Ai = (B i) with the fixed reduction polynomial P(x) = x8 + x4 + x3 + x + 1. Again, the zero ele- ment is mapped to itself. The vector Ai = (a7, . . . , a0) (representing the field element a7x7 + + a1x + a0) is the result of the substitution: · · · Ai = S 1(Bi). Since decryption round one needs the last subkey, the second decryption round needs the second-to-last subkey and so on, we need the subkey in reversed order as shown in Fig. 4.8. In practice this is mainly achieved by computing the entire key schedule first and storing all 11, 13 or 15 subkeys, depending on the number or 1 Key Schedule cıa AES 1, ta c¶n khóa con cuËi cùng, 1, ta c¶n khóa con tr˜Óc khóa con • 1 cıa AES • – vòng th˘ n cıa AES
– vòng th˘ n
cuËi, · · · 1, th˘ t¸ ta c¶n là • Tóm l§i, ta c¶n tính các khóa con theo th˘ t¸ ng˜Òc l§i. Ví dˆ,
vÓi AES (W [40], W [41], W [42], W [43]) (W [0], W [1], W [2], W [3]) ! • 45 / 46 Trên th¸c t∏, ta s≥ tính tr˜Óc toàn bÎ
11 khóa con (n∏u cho AES-128),
13 khóa con (n∏u cho AES-192), ho∞c
15 khóa con (n∏u cho AES-256) và l˜u l§i. 46 / 46 M™t mã ˘ng dˆng
Tßn công vét c§n 1 / 23 Cài ∞t hoán v‡ ng®u nhiên if xi == x j vÓi j < i then yi = y j $ X else yi X t¯ k¥ tßn công : Khi nh™n truy vßn xi 2 A 1 Hª mã l˛ t˜ng y1, . . . , yi } \ { . G˚i yi cho A Xét hª mã khËi E(k, x) = y. N∏u gi˙ bí m™t k, ta xác ‡nh hoán v‡
f nh˜ sau: f (x) = E(k, x) = y 2 / 23 N∏u hª mã E là an toàn thì f giËng nh˜ mÎt hoán v‡ ng®u nhiên. Hª mã l˛ t˜ng Xét hª mã khËi E(k, x) = y. N∏u gi˙ bí m™t k, ta xác ‡nh hoán v‡
f nh˜ sau: f (x) = E(k, x) = y N∏u hª mã E là an toàn thì f giËng nh˜ mÎt hoán v‡ ng®u nhiên. Cài ∞t hoán v‡ ng®u nhiên
Khi nh™n truy vßn xi if xi == x j vÓi j < i
then yi = y j
else yi
$ X X t¯ k¥ tßn công : 2 A 1 2 / 23 y1, . . . , yi } \ { . G˚i yi cho A Hoán v‡ ng®u nhiên x f (x)
10101
01110
01011
10001 x
00101
11111
10111
00011 f (x) Figure 4.3: A faithful gnome implementing random permutation f 3 / 23 1(yi) to the challenger, who sends xi := f inverse queries: the adversary sends a value yi X to the adversary (in Experiment 0 in the attack game, this is done using algorithm D). One then defines a corresponding advantage for this attack game. A block cipher is then called strongly secure if for all e cient adversaries, this advantage is negligible. We leave it to the reader to work out the details of this definition (see Exercise 4.9). We will not make use of this notion in this text, other than an example application in a later chapter (Exercise 9.12). 4.1.4 Using a block cipher directly for encryption Since a block cipher is a special kind of cipher, we can of course consider using it directly for encryption. The question is: is a secure block cipher also semantically secure? The answer to this question is “yes,” provided the message space is equal to the data block space. This will be implied by Theorem 4.1 below. However, data blocks for practical block ciphers are very short: as we mentioned, data blocks for AES are just 128-bits long. If we want to encrypt longer messages, a natural idea would be to break up a long message into a sequence of data blocks, and encrypt each data block separately. This use of a block cipher to encrypt long messages is called electronic codebook mode, or ECB mode for short. More precisely, suppose = (E, D) is a block cipher defined over ( , ). For any poly-bounded E K X 1, we can define a cipher , , ), as follows. E = (E , D ), defined over ( K X X For k and m , with v := m , we define K X • | | E(k, m[0]), . . . , E(k, m[v 1]) . E (k, m) := For k and c , with v := , we define c • K X | | D(k, c[0]), . . . , D(k, c[v 1]) . D (k, c) := 100 Tßn công vét c§n ∫ tìm khóa cıa mã
khËi Bài toán K¥ tßn công A bi∏t E : K X Y ⇥ ! và k là khóa c¶n tìm. • 4 / 23 Cho mÎt sË c∞p input/output (mi, ci = E(k, mi)) vÓi
i = 1, 2, . . . , q.
Hãy tìm khóa k. • Câu h‰i Rõ ràng A có th∫ bi∏t c1, . . . , cq. Nh˜ng t§i sao A l§i bi∏t m1, . . . , mq? Do ti∏t lÎ (v∑ sau) cıa d˙ liªu • Do ki∏n th˘c có t¯ tr˜Óc v∑ ng˙ c£nh. • 5 / 23 Bài toán càng ch∞t ch≥ s≥ càng phù hÒp cho nhi∑u tình huËng th¸c
t∏! Ti∏t lÎ d˙ liªu S và R chia s¥ khóa chung • Vào ngày 10 tháng 1, S mã hóa thông iªp • m = Hµn g∞p ngày mai lúc 5 giÌ chi∑u và g˚i b£n mã c ∏n cho R. K¥ tßn cËng lßy ˜Òc c • 6 / 23 • Vào ngày 11 tháng 1, k¥ tßn công quan sát thßy có cuÎc hÂp
gi˙a S và R lúc 5 giÌ chi∑u và do ó bi∏t thông iªp m. Bi∏t v∑ ng˙ c£nh 7 / 23 S và R chia s¥ khóa vÓi nhau. • Bi∏t r¨ng Email luôn b≠t ¶u b¨ng From • S mã hóa email • K¥ tßn công bi∏t b£n mã c • Và anh ta bi∏t t¯ From là mÎt ph¶n cıa b£n rõ. • Ki∫u tßn công Cho (m1, c1), . . . , (mq, cq) vÓi ci = E(k, mi). 1, ci Tßn công chÂn thông iªp: K¥ cßn công A có th∫ lßy m1, . . . , mq,
mÎt cách thích nghi, t˘c là chÂn mi nh˜ mÎt hàm theo 1). (m1, c1), . . . , (mi m1 c1 = E(k, m1) m2 c2 = E(k, m2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 / 23 K Tßn công vét c§n ∫ tìm khóa
tßn-công-vét-c§n (m1, c1)
for k = 1, 2, . . . , 2| | if E(k, m1) == c1 then return k 9 / 23 Câu h‰i: Thu™t toán trên liªu có giúp tìm khóa k úng? BÍ ∑
Gi£ s˚ DES là mÎt hª mã l˛ t˜ng 64 64) (256 hoán v‡ ng®u nhiên ⇡i : 0, 1
} !{ { 0, 1
}
Khi ó, vÓi mÈi c∞p x, y có nhi∑u nhßt mÎt khóa k th‰a mãn y = DES(k, x) vÓi xác sußt 1 99.5%. 1/256 ⇡ 56 k 0,1
X 02{
256 Pr[ k0 = k th‰a mãn c = DES(k, m) = DES(k0, m)] 9 6 Pr[DES(k, m) = DES(k0, m)] }
1
264 = 10 / 23 . 1
28 · Tìm ki∏m vét c§n ∫ tìm khóa cho mã
khËi • VÓi hai c∞p DES (m1, c1 = DES(k, m1)) và
(m2, c2 = DES(k, m2)) xác sußt ∫ có k có duy nhßt là 1 1/271. ⇡ VÓi AES-128: cho hai c∞p input/output, xác sußt có k duy nhßt • 1 1/2128 11 / 23 • ⇡
V™y hai c∞p input/output là ı thông tin ∫ tìm ki∏m vét c§n
cho khóa. Th˚ thách DES
Cho các c∞p b£n rõ và b£n mã msg = "The unknown messages is : XXXX ... "
CT = c4 c1 c3 c2 56 th‰a mãn DES(k, mi) = ci vÓi i = 1, 2, 3. 12 / 23 Hãy tìm khóa k 0, 1
} 2{ 1997: DESCHALL project vÓi internet search – 96 ngày • 1998: EFF dùng máy DeepCrack – 3 ngày (250K $) • 1999: K∏t hÒp c£ DeepCrack và internet search – 22 giÌ • 2006: COPACOBANA (120 FPGA) – 7 ngày (10K $). • (128-bit khóa 272 ) Không nên dùng mã khËi 56 bit khóa !!
ngày) C£i ti∏n DES chËng tßn công vét c§n:
Triple-DES Ph˜Ïng pháp 1: Triple-DES Xét E : K X X là mÎt hª mã khËi. • ⇥ ! Ta ‡nh nghæa hª mã khËi • 3E : K 3 X X ⇥ ! bi: Nh™n xét
N∏u k1 = k2 = k3 thì 3E = E 13 / 23 3E((k1, k2, k3), m) := E (k3, D (k2, E(k3, m))) Triple-DES: MÎt sË nh™n xét 14 / 23 Kích th˜Óc khóa là 3 56 = 168 bit, • ⇥ Ch™m gßp 3 l¶n DES. • Có th∫ tßn công trong thÌi gian 2118. • ⇡ $$$$key\len$=$112$bits$for$DES$ m$ c$ E(k2,(cid:6))$ E(k1,(cid:6))$ $ Hình: 2E ( (k1, k2), m ) := E ( k1, E(k2, m) ) Apack:$$$$M$=$(m1,…,$m10)$$,$$$C$=$(c1,…,c10).$
fi t˜ng tßn công double-DES: Tìm (k1, k2) th‰a mãn
• step$1:$$$build$table.$ 256$$ $sort$on$2nd$column$ entries$ E(k1, E(k2, m)) = c k0$=$00…00$
k1$=$00…01$
k2$=$00…10$
(cid:7)$
kN$=$11…11$ E(k0$,$M)$
E(k1$,$M)$
E(k2$,$M)$
(cid:7)$
E(kN$,$M)$ Dan$Boneh$ t˜Ïng ˜Ïng vÓi 15 / 23 E(k2, m) = D(k1, c). fi t˜ng tßn công 0 k
2 = = 0 k 1 1 k
2 = =1 1 k T k
1 = 25 1
6 5 6
2 = 1 k 2 Hình: E(k1, E(k2, m)) = c E(k2, m) = D(k1, c). , 16 / 23 c m ... ... 256 56 256 ⇥ 256 Thu™t toán 1 Xây d¸ng b£ng 56 ⇥ k0 = 00 . . . 0
k1 = 00 . . . 1 E(k0, m)
E(k1, m) E(kN , m) 3 for k · · ·
kN = 11 . . . 1
2 S≠p x∏p các ph¶n t˚ cıa b£ng theo côt th˘ hai E(k, m) 56: 0, 1 • Define$$$$$$$2E($(k1,k2),$m)$=$$$E(k1$,$E(k2$,$m)$)$ } 2{
ki∫m tra liªu D(k, c) có n¨m trong cÎt th˘ hai cıa b£ng $$$$key\len$=$112$bits$for$DES$ m$ c$ E(k2,(cid:6))$ E(k1,(cid:6))$ $ 17 / 23 Apack:$$$$M$=$(m1,…,$m10)$$,$$$C$=$(c1,…,c10).$ k0$=$00…00$ E(k0$,$M)$ • step$1:$$$build$table.$ k1$=$00…01$ E(k1$,$M)$ 256$$ k2$=$00…10$ E(k2$,$M)$ $sort$on$2nd$column$ entries$ (cid:7)$ (cid:7)$ kN$=$11…11$ E(kN$,$M)$ Dan$Boneh$ n∏u có thì E(ki, m) = D(k, c) (ki, k) = (k1, k2). ) Thu™t toán 1 Xây d¸ng b£ng 256 k0 = 00 . . . 0
k1 = 00 . . . 1 E(k0, m)
E(k1, m) E(kN , m) · · ·
kN = 11 . . . 1
2 S≠p x∏p các ph¶n t˚ cıa b£ng theo côt th˘ hai E(k, m) 56 256 56: ⇥
3 for k 0, 1 256 • Define$$$$$$$2E($(k1,k2),$m)$=$$$E(k1$,$E(k2$,$m)$)$ $$$$key\len$=$112$bits$for$DES$ m$ c$ E(k2,(cid:6))$ E(k1,(cid:6))$ $ 17 / 23 Apack:$$$$M$=$(m1,…,$m10)$$,$$$C$=$(c1,…,c10).$ k0$=$00…00$ E(k0$,$M)$ • step$1:$$$build$table.$ k1$=$00…01$ E(k1$,$M)$ 256$$ k2$=$00…10$ E(k2$,$M)$ $sort$on$2nd$column$ entries$ (cid:7)$ (cid:7)$ kN$=$11…11$ E(kN$,$M)$ Dan$Boneh$ } 2{
ki∫m tra liªu D(k, c) có n¨m trong cÎt th˘ hai cıa b£ng 56 ⇥ n∏u có thì E(ki, m) = D(k, c) (ki, k) = (k1, k2). ) Chi phí tính toán
• Define$$$$$$$2E($(k1,k2),$m)$=$$$E(k1$,$E(k2$,$m)$)$ $$$$key\len$=$112$bits$for$DES$ m$ c$ E(k2,(cid:6))$ E(k1,(cid:6))$ $ 256 56 256 • step$1:$$$build$table.$ ThÌi gian = Xây d¸ng b£ng và s≠p x∏p
Apack:$$$$M$=$(m1,…,$m10)$$,$$$C$=$(c1,…,c10).$ + Tìm ki∏m nh‡ phân trong b£ng
56 ⇥
{z 256$$ < 263
| } | } entries$ ⇥
k0$=$00…00$
{z
k1$=$00…01$
k2$=$00…10$
(cid:7)$
kN$=$11…11$ E(k0$,$M)$
E(k1$,$M)$
E(k2$,$M)$
(cid:7)$
E(kN$,$M)$ Dan$Boneh$ 18 / 23 Không gian 256
$sort$on$2nd$column$ ⇡ Ph˜Ïng pháp 2: DESX n n Xét hª mã khËi E : K 0, 1 • 0, 1
} ⇥{ !{ } ‡nh nghæa EX bi • EX ( (k1, k2, k3), m) = k1 E(k2, m k3) 19 / 23
VÓi DESX: Î dài khóa = 64 + 56 + 64 = 184 bit • Bài t™p
Liªu cách xây d¸ng E2((k1, k2), m) nh˜ d˜Ói ây có hiªu qu£ hay
không?
k1
E(k2, m 20 / 23 • E(k2, m)
k1) • GiÓi h§n cıa tính an toàn 128 128 128 Xét hª mã E : 0, 1 0, 1 { } ⇥{ 0, 1
} !{ } ‡nh nghæa bi E(k, m) = m. 21 / 23 Không th∫ tìm khóa n∏u cho mÎt sË c∞p b£n rõ/b£n mã. • Nh˜ng hª này là không an toàn! • Th∏ nào là hª mã khËi “tËt”? C¶n?
Có
Có ı?
Không!
Không! Tính chßt
an toàn chËng l§i vét c§n khóa
khó tìm m khi cho c = E(k, m)
... Ta không th∫ nào ‡nh nghæa ho∞c hi∫u tính an toàn n∏u ˜a ra
mÎt danh sách không xác ‡nh 22 / 23 Ta muËn mÎt tính chßt “chı §o” cıa hª mã khËi ∫ £m b£o an
toàn cho viªc s˚ dˆng mã khËi! 23 / 23 M™t mã ˘ng dˆng
S˚ dˆng mã khËi 1 / 33 Mã khËi l˛ t˜ng • Trên th¸c t∏, ng˜Ìi ta xem AES ho∞c 3DES nh˜ mÎt hª mã
khËi l˛ t˜ng; T˘c là, vÓi mÈi khóa k, ánh x§ • Fk(x) = e(k, x) 128 lên chính nó. 2 / 33 là mÎt hoán v‡ ng®u nhiên Îc l™p t¯ 0, 1
} { Các ch∏ Î và mode s˚ dˆng Câu h‰i: Làm th∏ nào ∫ mã hóa thông iªp vÓi Î dài bßt k˝?
(dùng AES) Tr£ lÌi: Dùng mÎt trong các mode sau: “ECB” = “Electronic code book” • “CTR” = “Counter mode” • “CBC” = “Cipher Block Chaining” • “OFB” = “Output Feedback” • ... • 3 / 33 Ch∏ Î s˚ dˆng: Khoá chø s˚ dˆng mÎt l¶n và khoá dùng nhi∑u
l¶n. Ÿng dˆng cıa khoá dùng nhi∑u l¶n Mã hóa hª thËng file Mã hóa nhi∑u file dùng AES vÓi cùng khóa • IPSec 4 / 33 Nhi∑u gói tin cùng ˜Òc mã hóa b¨ng AES vÓi cùng mÎt khóa • ECB (Electronic code book) Phép toán padding này cho có tính kh£ ngh‡ch. Nó cho phép • gi£i mã. xn x0 x1 x2 Enc Enc Enc Enc k k k k · · · · · · yn y0 y1 y2 • D˙ liªu ˜Òc chia thành các khËi khËi b bit, vÓi b = kích
th˜Óc khËi. 5 / 33 • VÓi d˙ liªu không chia h∏t cho b bit: Thêm dãy “10..0” ∫ Î
dài thông iªp chia h∏t cho b. ECB (Electronic code book) xn x0 x1 x2 Enc Enc Enc Enc k k k k · · · · · · yn y0 y1 y2 • D˙ liªu ˜Òc chia thành các khËi khËi b bit, vÓi b = kích
th˜Óc khËi. • VÓi d˙ liªu không chia h∏t cho b bit: Thêm dãy “10..0” ∫ Î
dài thông iªp chia h∏t cho b. 5 / 33 • Phép toán padding này cho có tính kh£ ngh‡ch. Nó cho phép
gi£i mã. ECB: Làm th∏ nào ∫ gi£i mã? yn y0 y1 y2 Dec Dec Dec Dec k k k k · · · · · · 6 / 33 xn x0 x1 x2 Private-Key Encryption 89 #$ #& #’ !" !" !" %& %’ %$ FIGURE 3.5: Electronic Code Book (ECB) mode. 1 Figure 3.5. Decryption is done in the obvious way, using the fact that F is k e ciently computable. ECB mode is deterministic and therefore cannot be CPA-secure. Worse, ECB-mode encryption does not even have indistinguishable encryptions in the presence of an eavesdropper. This is because if a block is repeated in the plaintext, it will result in a repeating block in the ciphertext. Thus, it is easy to distinguish an encryption of a plaintext that consists of two identical blocks from an encryption of a plaintext that consists of two di erent blocks. This is not just a theoretical problem. Consider encrypting an image in which small groups of pixels correspond to a plaintext block. Encrypting using ECB mode may reveal a significant amount of information about patterns in the image, something that should not happen when using a secure encryption scheme. Figure 3.6 demonstrates this. For these reasons, ECB mode should never be used. (We include it only because of its historical significance.) ECB là không an toàn • FIGURE 3.6: An illustration of the dangers of using ECB mode. The
Hình: Énh gi˙a là ECB mode, £nh bên ph£i là mã hóa an toàn
middle figure is an encryption of the image on the left using ECB mode; the
figure on the right is an encryption of the same image using a secure mode.
(Taken from http://en.wikipedia.org and derived from images created
Vßn ∑: N∏u xi = x j thì yi = y j.
by Larry Ewing (lewing@isc.tamu.edu) using The GIMP.)
ECB chø an toàn khi mã hóa d˙ liªu ng®u nhiên (ví dˆ, các
khóa). 7 / 33 • 126 5 More About Block Ciphers blocks can easily be manipulated. We demonstrate how a substitution attack could work in the real world. Imagine the following example of an electronic wire transfer betweens banks. Example 5.1. Substitution attack against electronic bank transfer Let’s assume a protocol for wire transfers between banks (Fig. 5.2). There are five Ví dˆ: Chuy∫n ti∑n gi˙a hai ngân hàng
dùng ECB fields which specify a transfer: the sending bank’s ID and account number, the re-
ceiving bank’s ID and account number, and the amount. We assume now (and this
is a major simplification) that each of the fields has exactly the size of the block
cipher width, e.g., 16 bytes in the case of AES. Furthermore, the encryption key be-
tween the two banks does not change too frequently. Due to the nature of the ECB,
an attacker can exploit the deterministic nature of this mode of operation by simple
substitution of the blocks. The attack details are as follows: Block # 1 2 3 4 5 Sending
Bank A Sending
Account # Receiving
Bank B Receiving
Account # Amount
$ Hình: Giao th˘c trao Íi gi˙a các ngân hàng: 1. The attacker, Oscar, opens one account at bank A and one at bank B.
1 Gi£ s˚: MÈi tr˜Ìng ∑u là n-bit (ví dˆ 128 bit)
2. Oscar taps the encrypted line of the banking communication network.
2 Gi£ s˚: Khoá kAB ∫ trao Íi thông tin gi˙a hai ngân hàng A
3. He sends $1.00 transfers from his account at bank A to his account at bank B
repeatedly. He observes the ciphertexts going through the communication net-
work. Even though he cannot decipher the random-looking ciphertext blocks, he
can check for ciphertext blocks that repeat. After a while he can recognize the
five blocks of his own transfer. He now stores blocks 1, 3 and 4 of these transfers.
These are the encrypted versions of the ID numbers of both banks as well as the
8 / 33
encrypted version of his account at bank B. 4. Recall that the two banks do not change the key too frequently. This means that the same key is used for several other transfers between bank A and B. By com- paring blocks 1 and 3 of all subsequent messages with the ones he has stored, Oscar recognizes all transfers that are made from some account at bank A to some account at bank B. He now simply replaces block 4 — which contains the receiving account number — with the block 4 that he stored before. This block contains Oscar’s account number in encrypted form. As a consequence, all trans- fers from some account of bank A to some account of bank B are redirected to go into Oscar’s B account! Note that bank B now has means of detecting that the block 4 has been replaced in some of the transfers it receives. 5. Withdraw money from bank B quickly and fly to a country that has a relaxed attitude about the extradition of white-collar criminals. What’s interesting about this attack is that it works completely without attack- ing the block cipher itself. So even if we would use AES with a 256-bit key and if và B là cË ‡nh. 126 5 More About Block Ciphers blocks can easily be manipulated. We demonstrate how a substitution attack could work in the real world. Imagine the following example of an electronic wire transfer betweens banks. Example 5.1. Substitution attack against electronic bank transfer Let’s assume a protocol for wire transfers between banks (Fig. 5.2). There are five fields which specify a transfer: the sending bank’s ID and account number, the re- ceiving bank’s ID and account number, and the amount. We assume now (and this is a major simplification) that each of the fields has exactly the size of the block cipher width, e.g., 16 bytes in the case of AES. Furthermore, the encryption key be- tween the two banks does not change too frequently. Due to the nature of the ECB,
an attacker can exploit the deterministic nature of this mode of operation by simple
substitution of the blocks. The attack details are as follows: Oscar tßn công Block # 1 2 3 4 5 Sending
Bank A Sending
Account # Receiving
Bank B Receiving
Account # Amount
$ 1 Oscar m mÎt tài kho£n t§i ngân hàng A và mÎt tài kho£n t§i 2 Oscar chuy∫n nhi∑u l¶n 1$ t¯ tài kho£n cıa anh ta ngân ngân hàng B; hàng A sang tài kho£n ngân hàng B; giËng nhau B5 B2 B4 B1
1. The attacker, Oscar, opens one account at bank A and one at bank B.
2. Oscar taps the encrypted line of the banking communication network.
3. He sends $1.00 transfers from his account at bank A to his account at bank B
3 Oscar b≠t gói tin trên ˜Ìng truy∑n và nh™n ˜Òc các b£n mã
repeatedly. He observes the ciphertexts going through the communication net-
work. Even though he cannot decipher the random-looking ciphertext blocks, he
can check for ciphertext blocks that repeat. After a while he can recognize the
B3
five blocks of his own transfer. He now stores blocks 1, 3 and 4 of these transfers.
và anh ta gi˙ l§i b£n mã B4.
These are the encrypted versions of the ID numbers of both banks as well as the
4 Trong t˜Ïng lai, mÈi khi thßy lªnh chuy∫n ti∑n t¯ B1 tÓi B3,
encrypted version of his account at bank B.
4. Recall that the two banks do not change the key too frequently. This means that
the same key is used for several other transfers between bank A and B. By com-
9 / 33
paring blocks 1 and 3 of all subsequent messages with the ones he has stored, Oscar recognizes all transfers that are made from some account at bank A to some account at bank B. He now simply replaces block 4 — which contains the receiving account number — with the block 4 that he stored before. This block contains Oscar’s account number in encrypted form. As a consequence, all trans- fers from some account of bank A to some account of bank B are redirected to go into Oscar’s B account! Note that bank B now has means of detecting that the block 4 has been replaced in some of the transfers it receives. 5. Withdraw money from bank B quickly and fly to a country that has a relaxed attitude about the extradition of white-collar criminals. What’s interesting about this attack is that it works completely without attack- ing the block cipher itself. So even if we would use AES with a 256-bit key and if thay block th˘ 4 bi B4. Bài toán Ta c¶n gi£i quy∏t hai vßn ∑: 10 / 33 Làm cho hª mã tr thành hª mã xác sußt; • Énh h˜ng cıa viªc mã hoá trên mÂi khËi. • Mã hoá xác sußt • Mã hóa hai l¶n cıa cùng mÎt thông iªp s≥ cho hai b£n mã
khác nhau B£n mã ph£i dài hÏn b£n rõ • Nói mÎt cách nôm na: • 11 / 33 Kích th˜Óc b£n mã = Kích th˜Óc b£n rõ + “sË bit ng®u
nhiên” Bài t™p
Hãy vi∏t hàm gi£i mã D cho hàm mã hoá E ˜Òc ‡nh nghæa bi: E(k, m): 12 / 33 m r = random()
c = AES(k, r)
return (r, c) D§ng mã hoá Mã hoá Ïn ‡nh Xác sußt 13 / 33 ECB CBC CTR OFB CBC (Cipher Block Chaining mode) xn
xn x0 x1 I V Enc Enc Enc
Enc k k k
k · · · · · ·
· · · · · · yn
yn y0 y1 Thu™t toán. ChÂn IV (“initialization value”) mÎt cách ng®u nhiên,
sau ó dùng yi nh˜ “I V ” cho Mi+1. G˚i IV cùng vÓi b£n mã 14 / 33 I V . . . y0 y1 yn k k k k S˚ dˆng I V nh˜ th∏ nào? I V không c¶n gi˙ bí m™t • Nh˜ng ph£i là “nonce” = “number used only once” 1 Là ng®u nhiên “th™t” •
Ví dˆ 2 Là bÎ ∏m “counter” (ph£i ˜Òc l˜u tr˙ bi Alice)
3 IDA 15 / 33 time IDB k k MÎt kˇ thu™t padding cho CBC Padding theo t¯ng byte; • ... | DD DD DD DD 04 04 04 04 | • Giá tr‡ mÈi byte ˜Òc thêm là sË byte c¶n ˜Òc thêm.
Ví dˆ, n∏u kích th˜Óc block là 8 và ta c¶n padding 4 byte: 16 / 33 n∏u không c¶n padding, ta thêm mÎt block gi£. • CBC: Gi£i mã yn
yn y0 y1 Dec Dec Dec
Dec k k k
k · · · · · ·
· · · · · · I V 17 / 33 xn
xn x0 x1 Output Feedback Mode (OFB) I V Enc Enc Enc k k k · · · · · · xn x0 x1 yn y0 y1 18 / 33 Thu™t toán. T˜Ïng t¸ nh˜ CBC mode. S˚ dˆng IV ng®u nhiên
truy∑n cùng b£n mã.
N∏u kích th˜Óc cıa b£n rõ M không chia h∏t cho b, ta chø c¶n
truy∑n b£n mã rút gÂn (không c¶n padding). OFB: Gi£i mã I V Enc Enc Enc k k k · · · · · · yn y0 y1 19 / 33 xn x0 x1 Cipher Feedback Mode (CFB) I V Enc Enc Enc k k k · · · · · · xn x0 x1 20 / 33 yn y0 y1 Bài t™p
Hãy mô t£ m§ch gi£i mã CFB I V Enc Enc Enc k k k · · · · · · xn x0 x1 21 / 33 yn y0 y1 Counter Mode (CTR) Nonce, Ctr Nonce, Ctr Nonce, Ctr Nonce, Ctr Enc Enc Enc Enc k k k k · · · · · · xn x0 x1 x2 yn y0 y1 y2 22 / 33 £m b£o c∞p Nonce Ctr c∞p không bao giÌ l∞p l§i. • k
Ctr ˜Òc b≠t ¶u t¯ 0 cho mÂi thông iªp. • Bài t™p
Hãy mô t£ m§ch gi£i mã CTR Nonce, Ctr Nonce, Ctr Nonce, Ctr Nonce, Ctr Enc Enc Enc Enc k k k k · · · · · · xn x0 x1 x2 23 / 33 yn y0 y1 y2 Bài t™p
Xét thông iªp m gÁm ` khËi AES (ví dˆ ` = 100). Alice mã hóa m
dùng CBC mode và truy∑n b£n mã k∏t qu£ tÓi Bob. Do m§ng lÈi,
khËi b£n mã sË `/2 b‡ mßt trong khi truy∑n. MÂi b£n mã khác ˜Òc
truy∑n và nh™n úng. Khi Bob gi£i mã b£n mã nh™n ˜Òc, bao
nhiêu khËi b£n rõ s≥ b‡ mßt? 24 / 33 Bài t™p
Xét thông iªp m bao gÁm ` khËi AES (ví dˆ ` = 100). Alice mã
hóa m dùng randomized counter mode và truy∑n b£n mã k∏t qu£
tÓi Bob. Do m§ng lÈi, b£n mã sË `/2 b‡ mßt trong khi truy∑n. MÂi
khËi b£n mã khác ˜Òc truy∑n và nh™n úng. Khi Bob gi£i mã b£n
mã nh™n ˜Òc, bao nhiêu khËi b£n rõ b‡ mßt? 25 / 33 Nên s˚ dˆng mode nào? Mˆc ích. N∏u hª mã khËi là không th∫ phân biªt vÓi hª mã khËi
l˛ t˜ng, thì mode s˚ dˆng nên £m b£o tính không th∫ phân biªt
d¸a trên tßn công chÂn b£n mã: ‡nh nghæa trò chÏi vÓi k¥ tßn công. • • 26 / 33 Mode là IND-CCA an toàn n∏u k¥ tßn công có th∫ th≠ng trong
trò chÏi vÓi xác sußt nhi∑u nhßt chø là 1/2 + ✏ vÓi ✏ là nh‰
“không áng k∫”. K¥ tßn công nh™n Y , và có th∫ ti∏p tˆc truy c™p vào EK và DK • (ngo§i tr¯ trên Y ). Th˚ nghiªm IND-CCA K¥ tßn công tính toán và ˜a ra d 0 là gÒi ˛ cho d. • Xét K là khóa ˜Òc chÂn ng®u nhiên. EK là hàm mã hóa vÓi
khóa K. DK là hàm gi£i mã. Pha I. (“Tìm ki∏m”) • K¥ tßn công có th∫ truy c™p vào EK , DK nh˜ các hÎp en.
(Có th∫ mã hóa/gi£i mã mÂi thông iªp anh ta muËn)
K¥ tßn công ˜a ra hai thông iªp M0, M1 cùng Î dài. • Pha II. (“GÒi ˛”) $ 27 / 33 Ta bí m™t chÂn d và tính Y = EK (Md ). • 0, 1
} { Th˚ nghiªm IND-CCA K¥ tßn công tính toán và ˜a ra d 0 là gÒi ˛ cho d. • Xét K là khóa ˜Òc chÂn ng®u nhiên. EK là hàm mã hóa vÓi
khóa K. DK là hàm gi£i mã. Pha I. (“Tìm ki∏m”) • K¥ tßn công có th∫ truy c™p vào EK , DK nh˜ các hÎp en.
(Có th∫ mã hóa/gi£i mã mÂi thông iªp anh ta muËn)
K¥ tßn công ˜a ra hai thông iªp M0, M1 cùng Î dài. • Pha II. (“GÒi ˛”) $ và tính Y = EK (Md ). • 0, 1
} { 27 / 33 • Ta bí m™t chÂn d
K¥ tßn công nh™n Y , và có th∫ ti∏p tˆc truy c™p vào EK và DK
(ngo§i tr¯ trên Y ). Th˚ nghiªm IND-CCA Xét K là khóa ˜Òc chÂn ng®u nhiên. EK là hàm mã hóa vÓi
khóa K. DK là hàm gi£i mã. Pha I. (“Tìm ki∏m”) • K¥ tßn công có th∫ truy c™p vào EK , DK nh˜ các hÎp en.
(Có th∫ mã hóa/gi£i mã mÂi thông iªp anh ta muËn)
K¥ tßn công ˜a ra hai thông iªp M0, M1 cùng Î dài. • Pha II. (“GÒi ˛”) $ và tính Y = EK (Md ). • 0, 1
} { • 27 / 33 Ta bí m™t chÂn d
K¥ tßn công nh™n Y , và có th∫ ti∏p tˆc truy c™p vào EK và DK
(ngo§i tr¯ trên Y ).
K¥ tßn công tính toán và ˜a ra d 0 là gÒi ˛ cho d. • IND-CCA an toàn Hª mã gÂi là an toàn chËng l§i tßn công CCA (hay IND-CCA) n∏u
trong th˚ nghiªm IND-CCA, lÒi th∏ cıa k¥ tßn công 28 / 33 1/2 Adv = Pr(d = d 0) | | là nh‰ “không áng k∫”. INC-CCA an toàn S¸ kiªn. ∫ là IND-CCA an toàn, ph˜Ïng pháp mã hóa ph£i ng®u
nhiên. ! 29 / 33 Ng˜Òc l§i, k¥ tßn công có th∫ mã hóa M0 và M1 rÁi so sánh vÓi y. CBC. T˜Ïng t¸ CTR: IV ng®u nhiên nh˜ng ˜Òc truy∑n d˜Ói • d§ng b£n rõ. K¥ tßn công có th∫ dùng kˇ thu™t gi£i mã khúc ¶u. Các mode ã bi∏t là không an toàn! OFB. T˜Ïng t¸. K¥ tßn công có th∫ s˚ dˆng kˇ thu™t gi£i mã • khúc ¶u. ECB. Không ng®u nhiên. • • 30 / 33 CTR. Giá tr‡ C t r b≠t ¶u là ng®u nhiên, nh˜ng nó ˜Òc
truy∑n d˜Ói d§ng b£n rõ. Trong tr˜Ìng hÒp này, k¥ tßn công
có th∫ yêu c¶u gi£i mã mÎt khúc ¶u cıa Y , và anh ta ˜Òc
khúc ¶u cıa Md . Các mode ã bi∏t là không an toàn! OFB. T˜Ïng t¸. K¥ tßn công có th∫ s˚ dˆng kˇ thu™t gi£i mã • khúc ¶u. ECB. Không ng®u nhiên. • • • 30 / 33 CTR. Giá tr‡ C t r b≠t ¶u là ng®u nhiên, nh˜ng nó ˜Òc
truy∑n d˜Ói d§ng b£n rõ. Trong tr˜Ìng hÒp này, k¥ tßn công
có th∫ yêu c¶u gi£i mã mÎt khúc ¶u cıa Y , và anh ta ˜Òc
khúc ¶u cıa Md .
CBC. T˜Ïng t¸ CTR: IV ng®u nhiên nh˜ng ˜Òc truy∑n d˜Ói
d§ng b£n rõ. K¥ tßn công có th∫ dùng kˇ thu™t gi£i mã khúc
¶u. Các mode ã bi∏t là không an toàn! ECB. Không ng®u nhiên. • • • CTR. Giá tr‡ C t r b≠t ¶u là ng®u nhiên, nh˜ng nó ˜Òc
truy∑n d˜Ói d§ng b£n rõ. Trong tr˜Ìng hÒp này, k¥ tßn công
có th∫ yêu c¶u gi£i mã mÎt khúc ¶u cıa Y , và anh ta ˜Òc
khúc ¶u cıa Md .
CBC. T˜Ïng t¸ CTR: IV ng®u nhiên nh˜ng ˜Òc truy∑n d˜Ói
d§ng b£n rõ. K¥ tßn công có th∫ dùng kˇ thu™t gi£i mã khúc
¶u. 30 / 33 • OFB. T˜Ïng t¸. K¥ tßn công có th∫ s˚ dˆng kˇ thu™t gi£i mã
khúc ¶u. Xét Z = n˚a ¶u cıa Y . • Vì Y = Z nên k¥ tßn công ˜Òc phép yêu c¶u tính DK (Z) trong • 6 Pha II. IND-CCA an toàn V™y nó cho phép tính ˜Òc mÎt n˚a ¶u cıa Md . • V™y k¥ tßn công luôn th≠ng. • ‡nh l˛. Các mode ECB, CTR, CBC, OFB không ph£i IND-CCA an
toàn. Ch˘ng minh. 31 / 33 • K¥ tßn công chÂn M0 = 0x và M1 = 1x vÓi x lÓn.
Khi ó Y = EK (Md ). • Vì Y = Z nên k¥ tßn công ˜Òc phép yêu c¶u tính DK (Z) trong • 6 Pha II. IND-CCA an toàn V™y nó cho phép tính ˜Òc mÎt n˚a ¶u cıa Md . • V™y k¥ tßn công luôn th≠ng. • ‡nh l˛. Các mode ECB, CTR, CBC, OFB không ph£i IND-CCA an
toàn. Ch˘ng minh. • 31 / 33 • K¥ tßn công chÂn M0 = 0x và M1 = 1x vÓi x lÓn.
Khi ó Y = EK (Md ).
Xét Z = n˚a ¶u cıa Y . • IND-CCA an toàn V™y nó cho phép tính ˜Òc mÎt n˚a ¶u cıa Md . • V™y k¥ tßn công luôn th≠ng. • ‡nh l˛. Các mode ECB, CTR, CBC, OFB không ph£i IND-CCA an
toàn. Ch˘ng minh. • • 31 / 33 • = Z nên k¥ tßn công ˜Òc phép yêu c¶u tính DK (Z) trong • 6 K¥ tßn công chÂn M0 = 0x và M1 = 1x vÓi x lÓn.
Khi ó Y = EK (Md ).
Xét Z = n˚a ¶u cıa Y .
Vì Y
Pha II. IND-CCA an toàn V™y k¥ tßn công luôn th≠ng. • ‡nh l˛. Các mode ECB, CTR, CBC, OFB không ph£i IND-CCA an
toàn. Ch˘ng minh. • • • = Z nên k¥ tßn công ˜Òc phép yêu c¶u tính DK (Z) trong • 6 31 / 33 K¥ tßn công chÂn M0 = 0x và M1 = 1x vÓi x lÓn.
Khi ó Y = EK (Md ).
Xét Z = n˚a ¶u cıa Y .
Vì Y
Pha II.
V™y nó cho phép tính ˜Òc mÎt n˚a ¶u cıa Md . • IND-CCA an toàn ‡nh l˛. Các mode ECB, CTR, CBC, OFB không ph£i IND-CCA an
toàn. Ch˘ng minh. • • • = Z nên k¥ tßn công ˜Òc phép yêu c¶u tính DK (Z) trong • 6 31 / 33 • K¥ tßn công chÂn M0 = 0x và M1 = 1x vÓi x lÓn.
Khi ó Y = EK (Md ).
Xét Z = n˚a ¶u cıa Y .
Vì Y
Pha II.
V™y nó cho phép tính ˜Òc mÎt n˚a ¶u cıa Md .
V™y k¥ tßn công luôn th≠ng. • Có th∫ xây d¸ng IND-CCA an toàn? Tr£ lÌi: Có. Yêu c¶u khi xây d¸ng. ˜a ra b£n mã Y cıa thông iªp M , k¥ tßn
công không th∫ t§o ˜Òc b£n mã Z cho mÎt thông iªp có liên
quan. Kˇ thu™t. S˚ dˆng k∏t hÒp tính bí m™t và tính toàn vµn thông iªp. 32 / 33 Hª mã IND-CCA an toàn. Hª mã có xác th¸c.
Ví dˆ: SÏ Á UFE = “Unbalanced Feistel Encryption” cıa Desai
(Crypto 2006). 33 / 33(cid:8)$
Claim:$$$for$all$$$$f1,$…,$fd:$$${0,1}n$$⟶$${0,1}n$$
(cid:8)$
(cid:8)$
Why$not$double$DES?$
T§i sao không dùng double-DES?
4.2 Overview of the AES Algorithm
Fig. 4.1 AES input/output parameters
Table 4.1 Key lengths and number of rounds for AES
Table 4.2 Multiplicative inverse table in GF(28) for bytes xy used within the AES S-Box
4.4 Internal Structure of AES
4.2 Overview of the AES Algorithm
Fig. 4.1 AES input/output parameters
Table 4.1 Key lengths and number of rounds for AES
Fig. 4.2 AES encryption block diagram
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr
8A
9A
Mathematical description of the S-Box For readers who are interested in how
the S-Box entries are constructed, a more detailed description now follows. This
s
s
description, however, is not necessary for a basic understanding of AES, and the
8B
remainder of this subsection can be skipped without problem. Unlike the DES S-
Boxes, which are essentially random tables that fulfill certain properties, the AES
S-Boxes have a strong algebraic structure. An AES S-Box can be viewed as a two-
step mathematical transformation (Fig. 4.4).
Fig. 4.4 The two operations within the AES S-Box which computes the function Bi = S(Ai)
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr
4.4.2 Diffusion Layer
4.4.1 Byte Substitution Layer
Table 4.3 AES S-Box: Substitution values in hexadecimal notation for input byte (xy)
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr
ShiftRows Sublayer
ShiftRows Sublayer
MixColumn Sublayer
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr
MixColumn Sublayer
Fig. 4.3 AES round function for rounds 1, 2, . . . , nr
Fig. 4.5 AES key schedule for 128-bit key size
Fig. 4.5 AES key schedule for 128-bit key size
Fig. 4.5 AES key schedule for 128-bit key size
Fig. 4.6 AES key schedule for 192-bit key sizes
2. On-the-fly A new subkey is derived for every new round during the encryption
(decryption) of a plaintext (ciphertext). Please note that when decrypting cipher-
texts, the last subkey is XORed first with the ciphertext. Therefore, it is required to
recursively derive all subkeys first and then start with the decryption of a ciphertext
and the on-the-fly generation of subkeys. As a result of this overhead, the decryption
of a ciphertext is always slightly slower than the encryption of a plaintext when the
on-the-fly generation of subkeys is used.
Fig. 4.6 AES key schedule for 192-bit key sizes
2. On-the-fly A new subkey is derived for every new round during the encryption
Fig. 4.7 AES key schedule for 256-bit key size
4.5 Decryption
Fig. 4.7 AES key schedule for 256-bit key size
4.5 Decryption
Fig. 4.8 AES decryption block diagram
Fig. 4.8 AES decryption block diagram
Fig. 4.8 AES decryption block diagram
Fig. 4.9 AES decryption round function 1, 2, . . . , nr
Inverse MixColumn Sublayer
Inverse ShiftRows Sublayer
Inverse ShiftRows Sublayer
Inverse Byte Substitution Layer
no shift
The inverse S-Box is used when decrypting a ciphertext. Since the AES S-Box is
one position right shift
a bijective, i.e., a one-to-one mapping, it is possible to construct an inverse S-Box
Inverse Byte Substitution Layer
Mathematical description of the S-Box For readers who are interested in how
Fig. 4.4 The two operations within the AES S-Box which computes the function Bi = S(Ai)
Table 4.4 Inverse AES S-Box: Substitution values in hexadecimal notation for input byte (xy)
Decryption Key Schedule
Table 4.4 Inverse AES S-Box: Substitution values in hexadecimal notation for input byte (xy)
Decryption Key Schedule
Alice
K¥ tßn công
Why$not$double$DES?$
T§i sao không dùng double-DES?
• Define$$$$$$$2E($(k1,k2),$m)$=$$$E(k1$,$E(k2$,$m)$)$
Why$not$double$DES?$
Why$not$double$DES?$
Why$not$double$DES?$
Fig. 5.2 Example for a substitution attack against ECB encryption
Fig. 5.2 Example for a substitution attack against ECB encryption
