-
Notifications
You must be signed in to change notification settings - Fork 0
/
The DES Algorithm Illustrated.html
1849 lines (1829 loc) · 65.5 KB
/
The DES Algorithm Illustrated.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<title>The DES Algorithm Illustrated</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<!--设置一下超链接的格式-->
<style>
a {
text-decoration: none; /* 去掉下划线 */
color: blue; /* 设置链接颜色为蓝色 */
}
a:hover {
text-decoration: underline; /* 鼠标悬停时显示下划线 */
}
.highlight {
background-color: yellow;
}
code {
background-color: #ccc;
border: 1px solid #ccc;
padding: 2px 5px;
border-radius: 3px;
font-family: Consolas, monospace;
user-select: text;
}
</style>
<style>
table {
border-collapse: collapse;
width: 100%;
}
th, td {
text-align: center;
padding: 8px;
border: 1px solid #ddd;
}
th {
background-color: #f2f2f2;
}
tr:nth-child(even) {
background-color: #f2f2f2;
}
tr:hover {
background-color: #ddd;
}
</style>
<script>
window.onload = function () {
const links = document.querySelectorAll('a[href^="#"]');
for (let i = 0; i < links.length; i++) {
links[i].addEventListener('click', function (event) {
event.preventDefault();
const targetId = this.getAttribute('href').substring(1);
const targetElement = document.getElementById(targetId);
if (targetElement) {
const highlighted = document.querySelector('.highlight');
if (highlighted) {
highlighted.classList.remove('highlight');
}
targetElement.classList.add('highlight');
}
});
}
};
</script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script>
MathJax = {
tex: {inlineMath: [['$', '$'], ['\\(', '\\)']]}
};
</script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js"></script>
<script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
</head>
<body style="background-color: white;font-family: 'Times New Roman', 'SimSun', 'sans-serif';font-size: 14pt; line-height: 2em">
<h2 style="text-align: center"> <a href="https://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm">The DES Algorithm Illustrated</a></h2>
<h3 style="text-align: center"><i> by <a href="https://en.wikipedia.org/wiki/James_Orlin_Grabbe">J. Orlin Grabbe</a>
翻译: <a href="https://github.com/Chinese-Coding">中文编程</a></i>
</h3>
<div style="text-align: justify; display: flex;flex-direction: column;justify-items: center;margin-left: 20%;margin-right: 20%">
DES (Data Encryption Standard) 算法是世界上使用最为广泛的加密算法. 多年来, 对许多人来说, "secret
code making"
和 DES 一直算是同义词. 虽然电子前哨基金会 (Electronic Frontier Foundation) 在最近发明了一台价值 22
万美元的机器用以破解 DES 加密的信息,
但是 DES 将通过一个名为 "triple-DES" 的延寿版使其能够在政府和银行领域继续存在多年.
`inline code`
<p>
那么, DES 是如何工作的呢? 本文解释了 DNS 加密中涉及的各个步骤, 并通过一个简单的示例说明了每个步骤如何工作.
自 DES 创建以来, 基于与 DES 类似的设计原则, 出现了许多其他算法 (<a href="#改变数据的方法">改变数据的方法</a>)
一旦您理解了 DES 中的基本转换, 您就会发现 <a
href="#跟上这些最新算法所涉及的步骤">跟上这些最新算法所涉及的步骤</a>是容易的.
<p>
但是, 首先我们应该了解一下 DES 的历史, 以及对未来的展望.
<h3 style="text-align: center"><a href="#The National Bureau of Standards Coaxes the Genie from the Bottle">The
National Bureau of Standards Coaxes the Genie from the Bottle</a></h3>
<p>
在 <a href="#Richard Nixon">Richard Nixon</a> 执政期间的 1973 年 5 月 15 日, 美国国家标准局 (National Bureau
of Standards, NBS) 在《联邦公报》(Federal Register) 上发布了一份征求用来保护传输和存储过程中的数据的加密算法提议的公告.
同时, 该公告解释了加密的重要性.
<blockquote>
在过去的十年中, 政府, 工业和<a href="#私营部门的其他组织">私营部门的其他组织</a>在数字数据的积累和交流方面正在加速增长.
<a href="#这些通信和存储的数据内容通常具有非常重要的价值, 同时可能有着较高的敏感程度.">这些通信和存储的数据的内容通常具有非常重要的价值,
同时可能有着较高的敏感程度.</a>
现在常见的数据传输包括数百万美元的资金转移, 证券的买卖, <a
href="#执法机构之间传送的逮捕或逮捕令和定罪记录">执法机构之间传送的逮捕或逮捕令和定罪记录</a>,
<a href="#对航空公司和乘客来说代表投资和价值的机票预订业务">对航空公司和乘客来说代表投资和价值的机票预订业务</a>,
<a href="#以及医生和治疗中心之间传送的病人健康状况和护理记录">以及医生和治疗中心之间传送的病人健康状况和护理记录</a>.
<p>
随着商业机构和政府部门传输和存储的数据的数量, 价值和机密性的不断增加,
人们对这些记录在未经授权的情况下被访问和使用的风险有了更高的认识和关注.
这种滥用的形式可以是盗窃或篡改代表金钱的数据记录, 恶意修改商业库存或截取和滥用有关个人的机密信息. 因此,
数据保护的需求是显而易见的, 也是迫在眉睫的. <a href="#1">1</a>
<p>
人们认识到, <a href="#encryption">encryption (scrambling, enciphering or privacy transformation)</a>
是在传输过程中保护此类数据的唯一方法, 也是保护存储在各种介质上的数据内容的有用方法,
但前提是可以设计和验证足够强度的加密方式, 并且其本身可集成到系统架构中.
NBS 征求有关计算机数据加密技术和算法的建议.
<a href="#2"> NBS 还征求为实现加密功能的推荐技术的实现, 推荐技术有: 生成,
评估和保护加密密钥; 维护过期密钥下的加密文件; 对加密文件进行部分更新; 为实现数据的标记,
轮询和路由而混合明文和加密数据等技术.
</a>
该局在制定标准和协助政府和行业评估技术方面发挥着作用, 并将安排对加密方法进行评估, 以便制定指导方针.
</blockquote>
NBS 一直在等待回应. 直到 1974 年 8 月 6 日, 也就是 Nixon 辞职的前三天, IBM 公司提交了其内部开发的一种名为
LUCIFER 算法作为候选者. 在美国国家安全局 (National Security Agency, NSA) 的帮助下对算法进行评估后, NBS 于
1977 年 7 月 15 日采用了 LUCIFER 算法的修改版作为新的 Data Encryption Standard (DES).
<p>
DES 很快被用于非数字媒体, 如音频电话线 (voice-grade public telephone lines). <a href="#举个例子">举个例子</a>,
在几年内, 美国国际香精香料公司
(International Flavors and Fragrances, IFF) 使用 DES 来保护其通过电话传输的宝贵配方 ("With Data Encryption,
Scents Are Safe at IFF," <i>Computerworld</i> 14, No. 21, 95 (1980).)
<p>
与此同时, 银行业作为政府之外最大的加密用户, 采用了 DES 作为<a
href="https://wiki.mbalib.com/wiki/批发银行">批发银行</a>标准. 批发银行业的标准由美国国家标准协会
(American National Standards Institute, ANSI) 制定. 1980 年通过的 <i>ANSI X3.92</i> 规定了 DES 算法的使用.
<h3 style="text-align: center">DES 的一些初步示例</h3>
DES 处理位 (bit) 或者说二进制数, 即数字计算机中常见的 0 和 1. 每组四个比特组成一个十六进制数.
二进制的 "0001" 等于十六进制数 "1", 二进制 "1000" 等于十六进制数 "8",
"1001" 等于十六进制数 "9", "1010" 等于十六进制数 "A"，"1111" 等于十六进制数 "F".
<p>
DES 对 64 个信息比特组 (相当于 16 个十六进制数) 进行加密. 为了进行加密, DES 使用 "keys", 其长度显然也是 16
个十六进制数 (64-bits). 但是, 在 DES 算法中, 每个密钥中有 8-bits 会被忽略, 因此密钥的有效长度为 56 位.
<a href="#3"> 但是, 无论如何, 64-bits (16 个十六进制数) 是 DES 组织的整数.</a>
<p>
例如, 如果我们将明文 "8787878787878787" 用 DES 密钥 "0E329232EA6D0D73" 进行加密, 最终得到密文
"0000000000000000". 如果使用相同的 DES 密钥 "0E329232EA6D0D73" 对密文进行解密, 则将得到原始明文
"8787878787878787".
<p>
这个例子之所以整齐有序, 是因为我们的明文长度正好是 64-bits. 如果明文恰好是 64-bits 的倍数, 情况也是如此.
但大多数的信息不属于这一情况. 它们不会是 64-bits 的整数倍 (16 个十六进制数的整数倍).
<p>
例如，"Your lips are smoother than vaseline", 这个明文信息长 38 个字节 (76 个十六进制数字).
因此, 必须在信息尾部添加一些额外字节进行加密.
一旦加密信息被解密, 这些额外的字节将被丢弃. 当然, 有不同的填充方案 (添加额外字节的不同方法).
在这里，我们只需在末尾添加 0 即可，使得信息总量是 8 字节 (16 个十六进制数字，或 64-bits) 的倍数.
<p>
明文信息 "Your lips are smoother than vaseline" 的十六进制编码为: <br>
<code>596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A</code> <br>
(请注意, 前 72 位十六进制数字表示英文报文, 十六进制数 "0D" 表示回车, 十六进制数 "0A" 表示换行, 表示报文文件已结束)
<a href="#换行符"><sup>换行符</sup></a>
然后, 我们在报文末尾填充一些 0, 得到总共 80 位十六进制数字: <br>
<code>596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A0000</code>
<p>
如果我们使用与之前相同的 DES 密钥 "0E329232EA6D0D73" 对该明文信息进行加密, 每次加密 64 位 (16 位十六进制数字),
就可以得到密文: <br>
<code>C0999FDDE378D7ED 727DA00BCA5A84EE 47F269A4D6438190 9DD52F78F5358499 828AC9B453E0E653</code>
<p>
这就是可以传输或存储的密文. 对密文进行解密, 就可以恢复原来的信息----"Your lips are smoother than vaseline".
<a href="#克林顿">(Think how much better off Bill Clinton would be today, if Monica Lewinsky had used
encryption on her Pentagon computer!)</a>
<h3 style="text-align: center">DES 工作原理详解</h3>
<p>
DES 是一种<b>分块密码 (<i>block cipher</i>)</b>, 这意味着它对给定大小 (64 bits) 的明文块进行操作,
并返回相同大小的密文块.
因此, DES 会产生 $2^{64}$ 种可能的 64 位<b>排列 (<i>permutation</i>)</b>, 每个位可能是 0 或 1. 每个 64
位块被分为两个各 32 位块----左半块 $L$ 和右半块 $R$. (这种划分仅在某些操作中使用.)
<p>
<b>Example:</b> 明文 $M$ = <code>0123456789ABCDEF</code>, 其中 $M$ 为十六进制格式.
将其改写为二进制格式，我们得到-64 bits 的文本块:
<p>
$M$ = <code>0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111</code><br>
$L$ = <code>0000 0001 0010 0011 0100 0101 0110 0111</code><br>
$R$ = <code>1000 1001 1010 1011 1100 1101 1110 1111</code>
<p>
从左向右读取: $M$ 的第一位为 0, 最后一位为 1.
<p>
DES 使用 56-bits 大小的密钥对 64-bits 的数据块进行操作. 密钥实际上被存储为 64-bits, 但是每个密钥中有 8-bits
没有被使用
(<a href="#未使用的位">即8, 16, 24, 32, 40, 48, 56 和 64位</a> )
<p>
然而, 在下面的计算中, 我们将左至右对每位依次编号为 1 到 64. 但是, 正如您所看到的, 当我们创建子密钥时, 刚才提到的
8 位将被删除.
<p>
<b>Example:</b> 十六进制密钥 $K$ = <code>133457799BBCDFF1</code> 这样就得到了二进制密钥 (1 = 0001,
3=0011等, 每 8 位位 1 组, 每组的最后一位未使用): <br>
$K$ = <code>00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001</code>
<p>
DES 算法有以下几个步骤:
<h2 style="text-align: center">步骤1: 创建 16 个子密钥, 每个子密钥长度为 48 位</h2>
<p>
64 bits 密钥按照下表 (<b>PC-1</b>) 进行排列. 由于表中的第一个条目是 "57", 这意味着原始密钥 $K$ 的第 57
位变成了置换密钥 $K+$
的第 1 位. 原始密钥的第 49 位成为置换密钥的第 2 位. 原始密钥的第 4 位成为了置换密钥的最后一位. 请注意, 只有
56 bits 的原始密钥出现在置换密钥中.
<table cellspacing="0" style="text-align:right">
<caption align="top"><b>PC-1</b></caption>
<tbody>
<tr>
<td>57</td>
<td>49</td>
<td>41</td>
<td>33</td>
<td>25</td>
<td>17</td>
<td>9
</td>
</tr>
<tr>
<td>1</td>
<td>58</td>
<td>50</td>
<td>42</td>
<td>34</td>
<td>26</td>
<td>18
</td>
</tr>
<tr>
<td>10</td>
<td>2</td>
<td>59</td>
<td>51</td>
<td>43</td>
<td>35</td>
<td>27
</td>
</tr>
<tr>
<td>19</td>
<td>11</td>
<td>3</td>
<td>60</td>
<td>52</td>
<td>44</td>
<td>36
</td>
</tr>
<tr>
<td>63</td>
<td>55</td>
<td>47</td>
<td>39</td>
<td>31</td>
<td>23</td>
<td>15
</td>
</tr>
<tr>
<td>7</td>
<td>62</td>
<td>54</td>
<td>46</td>
<td>38</td>
<td>30</td>
<td>22
</td>
</tr>
<tr>
<td>14</td>
<td>6</td>
<td>61</td>
<td>53</td>
<td>45</td>
<td>37</td>
<td>29
</td>
</tr>
<tr>
<td>21</td>
<td>13</td>
<td>5</td>
<td>28</td>
<td>20</td>
<td>12</td>
<td>4
</td>
</tr>
</tbody>
</table>
<p>
<b>Example:</b> 原始的 64-bits 密钥:
<p>
$K$ = <code>00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001</code>
<p>
我们得到 56-bits 的置换密钥:
<p>
$K+$ = <code>1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111</code>
<p>
然后, 将密钥分成左右两半, 即 $C_0$ 和 $D_0$, 每半有 28-bits.
<p>
<b>Example:</b> 从置换密钥 $K+$ 我们得到:
<p>
$C_0$ = <code>1111000 0110011 0010101 0101111</code>, $D_0$ = <code>0101010 1011001 1001111 0001111</code>
<p>
在定义了 $C_0$ 和 $D_0$ 之后, 我们现在构造 16 个 $C_n, D_n, 1 \leq n \leq 16$. 在 $n = 1, 2, ..., 16$ 的情况下,
每一对 $C_n 和 D_n$ 分别由上一对 $C_{n-1} 和 D_{n-1}$ 使用下面表进行左移操作完成. 左移时, 除第一位外,
每一位向左移动一位, 第一位则循环到块的末尾.
<table>
<tr>
<th>Iteration</th>
<td> 1</td>
<td> 2</td>
<td> 3</td>
<td> 4</td>
<td> 5</td>
<td> 6</td>
<td> 7</td>
<td> 8</td>
<td> 9</td>
<td>10</td>
<td>11</td>
<td>12</td>
<td>13</td>
<td>14</td>
<td>15</td>
<td>16</td>
</tr>
<tr>
<th>Number of Left Shifts</th>
<td>1</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>2</td>
<td>1</td>
</tr>
</table>
<p>
例如, $C_3 和 D_3$ 分别由 $C_2 和 D_2$ 通过左移两次得到, $C_{16} 和 D_{16}$ 分别由 $C_{15} 和 D_{15}$
通过左移一次得到.
<a href="#循环左移">在所有情况下, 一次左移是指将比特向左旋转一位.</a> 这样, 经过一次左移后, 28-bits 块上的比特就是之前2,
3, ..., 28,1 位上的比特.
<p>
<b>Example:</b> 由原始配对 $C_0$ 和 $D_0$ 可得:
<p>
$C_0$ = <code>1111000011001100101010101111</code>, $D_0$ = <code>0101010101100110011110001111</code> <br>
$C_1$ = <code>1110000110011001010101011111</code>, $D_1$ = <code>1010101011001100111100011110</code> <br>
$C_2$ = <code>1100001100110010101010111111</code>, $D_2$ = <code>0101010110011001111000111101</code> <br>
$C_3$ = <code>0000110011001010101011111111</code>, $D_3$ = <code>0101011001100111100011110101</code> <br>
$C_4$ = <code>0011001100101010101111111100</code>, $D_4$ = <code>0101100110011110001111010101</code> <br>
$C_5$ = <code>1100110010101010111111110000</code>, $D_5$ = <code>0110011001111000111101010101</code> <br>
$C_6$ = <code>0011001010101011111111000011</code>, $D_6$ = <code>1001100111100011110101010101</code> <br>
$C_7$ = <code>1100101010101111111100001100</code>, $D_7$ = <code>0110011110001111010101010110</code> <br>
$C_8$ = <code>0010101010111111110000110011</code>, $D_8$ = <code>1001111000111101010101011001</code> <br>
$C_9$ = <code>0101010101111111100001100110</code>, $D_9$ = <code>0011110001111010101010110011</code> <br>
$C_{10}$ = <code>0101010111111110000110011001</code>, $D_{10}$ = <code>1111000111101010101011001100</code> <br>
$C_{11}$ = <code>0101011111111000011001100101</code>, $D_{11}$ = <code>1100011110101010101100110011</code> <br>
$C_{12}$ = <code>0101111111100001100110010101</code>, $D_{12}$ = <code>0001111010101010110011001111</code> <br>
$C_{13}$ = <code>0111111110000110011001010101</code>, $D_{13}$ = <code>0111101010101011001100111100</code> <br>
$C_{14}$ = <code>1111111000011001100101010101</code>, $D_{14}$ = <code>1110101010101100110011110001</code> <br>
$C_{15}$ = <code>1111100001100110010101010111</code>, $D_{15}$ = <code>1010101010110011001111000111</code> <br>
$C_{16}$ = <code>1111000011001100101010101111</code>, $D_{16}$ = <code>0101010101100110011110001111</code> <br>
<p>
现在, 我们通过对每个<a href="#连接的密钥对">连接的密钥对</a> $C_nD_n$ 应用下面的置换表来形成密钥
$K_n (1 \leq n \leq 16)$. 每对密钥有 56 位, 但 <b>PC-2</b> 只使用其中的 48 位.
<table cellspacing="0" style="text-align:right">
<caption align="top"><b>PC-2</b></caption>
<tbody>
<tr>
<td>14</td>
<td>17</td>
<td>11</td>
<td>24</td>
<td>1</td>
<td>5
</td>
</tr>
<tr>
<td>3</td>
<td>28</td>
<td>15</td>
<td>6</td>
<td>21</td>
<td>10
</td>
</tr>
<tr>
<td>23</td>
<td>19</td>
<td>12</td>
<td>4</td>
<td>26</td>
<td>8
</td>
</tr>
<tr>
<td>16</td>
<td>7</td>
<td>27</td>
<td>20</td>
<td>13</td>
<td>2
</td>
</tr>
<tr>
<td>41</td>
<td>52</td>
<td>31</td>
<td>37</td>
<td>47</td>
<td>55
</td>
</tr>
<tr>
<td>30</td>
<td>40</td>
<td>51</td>
<td>45</td>
<td>33</td>
<td>48
</td>
</tr>
<tr>
<td>44</td>
<td>49</td>
<td>39</td>
<td>56</td>
<td>34</td>
<td>53
</td>
</tr>
<tr>
<td>46</td>
<td>42</td>
<td>50</td>
<td>36</td>
<td>29</td>
<td>32
</td>
</tr>
</tbody>
</table>
<p>
因此, $K_n$ 的第 1 位是 $C_nD_n$ 的第 14 位, 第 2 位是第 17 位, 以此类推, $K_n$ 的第 48 位是 $C_nD_n$ 的第
32 位.
<p>
<b>Example:</b> 对于第一个密钥, 我们有
$C_1D_1$ = <code>1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110</code>
应用置换表 <b>PC-2</b> 后,
$K_1$ = <code>000110 110000 001011 101111 111111 000111 000001 110010</code>
<p>
其他密钥:
<p>
$K_2$ = <code>011110 011010 111011 011001 110110 111100 100111 100101 </code> <br>
$K_3$ = <code> 010101 011111 110010 001010 010000 101100 111110 011001 </code> <br>
$K_4$ = <code>011100 101010 110111 010110 110110 110011 010100 011101 </code> <br>
$K_5$ = <code>011111 001110 110000 000111 111010 110101 001110 101000 </code> <br>
$K_6$ = <code>011000 111010 010100 111110 010100 000111 101100 101111 </code> <br>
$K_7$= <code>111011 001000 010010 110111 111101 100001 100010 111100 </code> <br>
$K_8$= <code>111101 111000 101000 111010 110000 010011 101111 111011 </code> <br>
$K_9$= <code>111000 001101 101111 101011 111011 011110 011110 000001 </code> <br>
$K_{10}$= <code>101100 011111 001101 000111 101110 100100 011001 001111 </code> <br>
$K_{11}$= <code>001000 010101 111111 010011 110111 101101 001110 000110 </code> <br>
$K_{12}$= <code>011101 010111 000111 110101 100101 000110 011111 101001 </code> <br>
$K_{13}$= <code>100101 111100 010111 010001 111110 101011 101001 000001 </code> <br>
$K_{14}$= <code>010111 110100 001110 110111 111100 101110 011100 111010 </code> <br>
$K_{15}$= <code>101111 111001 000110 001101 001111 010011 111100 001010 </code> <br>
$K_{16}$= <code>110010 110011 110110 001011 000011 100001 011111 110101 </code> <br>
<p>
子密钥就介绍到这里. 现在我们来看看信息本身.
<h2 style="text-align: center">步骤 2: 对每个 64 位数据块进行加密编码</h2>
<p>
对需加密的信息 $M$ 的 64-bits 进行 初始置换 (initial permutation, <b>IP</b>).
根据下表重新排列比特位, 表中条目表示比特位在初始顺序基础上的新排列. $M$ 的第 58 位成为 $IP$ 的第 1 位.
$M$ 的第 50
位成为 $IP$ 的第 2 位. $M$ 的第 7 位是 $IP$ 的最后一位.
<table cellspacing="0" style="text-align:right">
<caption align="top"><b>IP</b></caption>
<tbody>
<tr>
<td>58</td>
<td>50</td>
<td>42</td>
<td>34</td>
<td>26</td>
<td>18</td>
<td>10</td>
<td>2
</td>
</tr>
<tr>
<td>60</td>
<td>52</td>
<td>44</td>
<td>36</td>
<td>28</td>
<td>20</td>
<td>12</td>
<td>4
</td>
</tr>
<tr>
<td>62</td>
<td>54</td>
<td>46</td>
<td>38</td>
<td>30</td>
<td>22</td>
<td>14</td>
<td>6
</td>
</tr>
<tr>
<td>64</td>
<td>56</td>
<td>48</td>
<td>40</td>
<td>32</td>
<td>24</td>
<td>16</td>
<td>8
</td>
</tr>
<tr>
<td>57</td>
<td>49</td>
<td>41</td>
<td>33</td>
<td>25</td>
<td>17</td>
<td>9</td>
<td>1
</td>
</tr>
<tr>
<td>59</td>
<td>51</td>
<td>43</td>
<td>35</td>
<td>27</td>
<td>19</td>
<td>11</td>
<td>3
</td>
</tr>
<tr>
<td>61</td>
<td>53</td>
<td>45</td>
<td>37</td>
<td>29</td>
<td>21</td>
<td>13</td>
<td>5
</td>
</tr>
<tr>
<td>63</td>
<td>55</td>
<td>47</td>
<td>39</td>
<td>31</td>
<td>23</td>
<td>15</td>
<td>7
</td>
</tr>
</tbody>
</table>
<p>
<b>Example:</b> 将初始置换应用于之前给出的文本块 $M$, 我们得到:
<p>
$M$ = <code>0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 </code><br>
$IP$ = <code>1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010</code>
<p>
这里 $M$ 的第 58 位为 "1", 成为 $IP$ 的第 1 位. $M$ 的第 50 位为 "1", 成为 $M$ 的第 2 位.
$M$ 的第 7 位为 "0"，成为 $IP$ 的最后一位.
<p>
接下来, 将置换块 $IP$ 分成左半部分 $L_0$ (32 bits) 和右半部分 $R_0$ (32 bits).
<p>
<b>Example:</b> 从 $IP$, 我们得到 $L_0 和 R_0$:
<p>
$L_0$ = <code>1100 1100 0000 0000 1100 1100 1111 1111</code> <br>
$R_0$ = <code>1111 0000 1010 1010 1111 0000 1010 1010</code>
<p>
在 $1 \leq n \leq 16$ 时, 我们使用函数 $f$ 对两个数据块 (一个 32-bits 的数据块和一个 48-bits 的密钥 $K_n$)
进行 16 次迭代, 以产生一个 32-bits 的数据块. <a href="#XOR"><b>让 + 表示 XOR 加法 (逐位加法 2 模).</b></a> 对于
n 从 1 到 16, 我们可以计算出:
<p>
$L_n = R_{n-1}$ <br>
$R_n = L_{n-1} \oplus f (R_{n-1}, K_n)$
<p>
最终块即为 $n = 16$ 时的 $L_{16}R_{16}$. 也就是说, 在每一次迭代中, 我们取前一次运算结果的右 32 位作为当前运算步骤的左
32 位.
对于当前步骤的右 32 位, 我们将上一步骤的左 32 位与计算结果 $f$ 进行 XOR 运算.
<p>
<b>Example:</b> 对 $n = 1$, 我们有:
<p>
$K_1$ = <code>000110 110000 001011 101111 111111 000111 000001 110010</code> <br>
$L_1$ = $R_0$ = <code>1111 0000 1010 1010 1111 0000 1010 1010</code> <br>
$R_1$ = $L_0 \oplus f(R_0, K_1)$
<p>
下面将解释函数 $f$ 的工作原理. 为了计算 $f$, 我们首先将每个块 $R_{n-1}$ 从 32 bits 扩展到 48 bits.
为此, 我们使用一个选择表来重复 $R_{n-1}$ 中的某些位的比特. 我们将这个选择表称为函数 $E$.
因此, $E(R_{n-1})$ 需要 32-bits 的输入, 并且输出 48-bits 的块.
<p>
$E$ 的 48 位输出 (写成 8 块, 每块 6 bits) 是通过按照下表的顺序选择其输入的位而得到的 :
<table cellspacing="0" style="text-align:right">
<caption align="top"><a href="#E-Table"><b>E BIT-SELECTION TABLE</b></a></caption>
<tbody>
<tr>
<td>32</td>
<td>1</td>
<td>2</td>
<td>3</td>
<td>4</td>
<td>5
</td>
</tr>
<tr>
<td>4</td>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
<td>9
</td>
</tr>
<tr>
<td>8</td>
<td>9</td>
<td>10</td>
<td>11</td>
<td>12</td>
<td>13
</td>
</tr>
<tr>
<td>12</td>
<td>13</td>
<td>14</td>
<td>15</td>
<td>16</td>
<td>17
</td>
</tr>
<tr>
<td>16</td>
<td>17</td>
<td>18</td>
<td>19</td>
<td>20</td>
<td>21
</td>
</tr>
<tr>
<td>20</td>
<td>21</td>
<td>22</td>
<td>23</td>
<td>24</td>
<td>25
</td>
</tr>
<tr>
<td>24</td>
<td>25</td>
<td>26</td>
<td>27</td>
<td>28</td>
<td>29
</td>
</tr>
<tr>
<td>28</td>
<td>29</td>
<td>30</td>
<td>31</td>
<td>32</td>
<td>1
</td>
</tr>
</tbody>
</table>
<p>
因此, $E(R_{n-1})$ 的前三位是 $R_{n-1}$ 的第 32, 1 和 2位, 而 $E(R_{n-1})$ 的后两位是$R_{n-1}$ 第 32 和 1 位.
<p>
<b>Example:</b> 我们根据 $R_0$ 计算 $E(R_0)$ 如下所示:
<p>
$R_0$ = <code>1111 0000 1010 1010 1111 0000 1010 1010</code> <br>
$E(R_0)$ = <code>011110 100001 010101 010101 011110 100001 010101 010101</code>
<p>
(注意, 每个由 4 个原始比特组成的比特块已经扩展为一个由 6 个输出比特组成的比特块).
<p>
接下来在 $f$ 计算中, 我们将输出的 $E(R_{n-1})$ 与密钥 $K_n$ 进 行XOR 运算:
$$K_n \oplus E(R_{n-1})$$
对于 $K_1, R(R_0)$, 我们有:
<p>
$K_1$ = <code>000110 110000 001011 101111 111111 000111 000001 110010</code> <br>
$E(R_0)$ = <code>011110 100001 010101 010101 011110 100001 010101 010101</code> <br>
$K_1 \oplus E(R_0)$ = <code>011000 010001 011110 111010 100001 100110 010100 100111</code>
<p>
我们尚未完成函数 $f$ 的计算. 到目前为止, 我们已经使用选择表将 $R_{n-1}$ 从 32-bits 扩展到 48-bits, 并将结果与密钥
$K_n$ 进行了 XOR. 现在我们有 48-bits (8 组 6-bits). 现在, 我们要对每组的 6-bits 做一些奇怪的事情:
把它们作为地址放入名为 "S 盒 (<b>S boxes</b>)" 的表中. 每组 6-bits 将为我们提供一个不同 S 盒中的位置.
位于该位置的将是一个 4-bits 数字. 这个 4-bits 数字将取代原来的 6-bits 数字.
最终结果是, 8 组 6-bits 数据转换成 8 组 4-bits (S 盒的 4 位输出) 共计 32 位数据.
<p>
将前面的 48-bits 结果写成如下形式:
$$K_n + E(R_{n-1}) = B_1B_2B_3B_4B_5B_6B_7B_8$$
其中每个 $B_i$ 是一组 6-bits. 我们现在计算:
$$S_1(B_1)S_2(B_2)S_3(B_3)S_4(B_4)S_5(B_5)S_6(B_6)S_7(B_7)S_8(B_8)$$
其中 $S_i(B_i)$ 指的是第 i 个 S 盒的输出.
重复一下, 每个函数 $S_1, S_2, ...,S_8$ 都采用 6-bits 块作为输入, 4-bits 块作为输出. $S_1$ 的表格如下所示并进行了解释:
<table>
<tr>
<th>Row <br> No.</th>
<th>0</th>
<th>1</th>
<th>2</th>
<th>3</th>
<th>4</th>
<th>5</th>
<th>6</th>
<th>7</th>
<th>8</th>
<th>9</th>
<th>10</th>
<th>11</th>
<th>12</th>
<th>13</th>
<th>14</th>
<th>15</th>
</tr>
<tr>
<th>0</th>
<td>14</td>
<td>4</td>
<td>13</td>
<td>1</td>
<td>2</td>
<td>15</td>
<td>11</td>
<td>8</td>
<td>3</td>
<td>10</td>
<td>6</td>
<td>12</td>
<td>5</td>
<td>9</td>
<td>0</td>
<td>7</td>
</tr>
<tr>
<th>1</th>
<td>0</td>
<td>15</td>
<td>7</td>
<td>4</td>
<td>14</td>
<td>2</td>
<td>13</td>
<td>1</td>
<td>10</td>
<td>6</td>
<td>12</td>
<td>11</td>
<td>9</td>
<td>5</td>
<td>3</td>
<td>8</td>
</tr>
<tr>
<th>2</th>
<td>4</td>
<td>1</td>
<td>14</td>
<td>8</td>
<td>13</td>
<td>6</td>
<td>2</td>
<td>11</td>
<td>15</td>
<td>12</td>
<td>9</td>
<td>7</td>
<td>3</td>
<td>10</td>
<td>5</td>
<td>0</td>
</tr>
<tr>
<th>3</th>
<td>15</td>
<td>12</td>
<td>8</td>
<td>2</td>
<td>4</td>
<td>9</td>
<td>1</td>
<td>7</td>
<td>5</td>
<td>11</td>
<td>3</td>
<td>14</td>
<td>10</td>
<td>0</td>
<td>6</td>
<td>13</td>
</tr>
</table>
<p>
设 $S_1$ 是此表中定义的函数, $B$ 是 6-bits 块, 那么 $S_1(B)$ 的确定方法如下: B 的第 1 位和最后一位用来表示二进制下的
在十进制 0 - 3 (二进制: 00 - 11) 范围中的一个数字, 令这个数字为 $i$; $B$ 中间的 4 位表示二进制下的
在十进制 0 - 15 (二进制: 0000 - 1111) 范围中的一个数字, 令这个数字为 $j$. 在表格中查找第 $i$ 行第 $j$ 列中的数字.
它是一个范围在 0 - 15 之间的数字, 唯一表示成一个 4-bits 的数据块. 例如: 对于输入块 $B = 011011$, 第 1 位是 "0",
最后一位是
"1", 因此选择第 01 行 (即第 1 行). 中间四位是 "1101". 这相当于十进制数 13 的二进制形式, 因此列号为 13. 第 1 行第
12 列是 5.
这决定了输出; 5 的二进制是 0101, 因此输出是 0101. 所以 $S_1(011011) = 0101$.
<p>
函数 $S_1, ..., S_8$ 定义如下表所示:
<table>
<caption align="top">$S_1$</caption>
<tbody>
<tr>
<td>14</td>
<td>4</td>
<td>13</td>
<td>1</td>
<td>2</td>
<td>15</td>
<td>11</td>
<td>8</td>
<td>3</td>
<td>10</td>
<td>6</td>
<td>12</td>
<td>5</td>
<td>9</td>
<td>0</td>
<td>7</td>
</tr>
<tr>
<td>0</td>
<td>15</td>
<td>7</td>
<td>4</td>
<td>14</td>
<td>2</td>
<td>13</td>
<td>1</td>
<td>10</td>
<td>6</td>
<td>12</td>
<td>11</td>
<td>9</td>
<td>5</td>
<td>3</td>
<td>8</td>
</tr>
<tr>
<td>4</td>
<td>1</td>
<td>14</td>
<td>8</td>
<td>13</td>
<td>6</td>
<td>2</td>
<td>11</td>
<td>15</td>
<td>12</td>
<td>9</td>
<td>7</td>
<td>3</td>
<td>10</td>
<td>5</td>
<td>0</td>
</tr>
<tr>
<td>15</td>
<td>12</td>
<td>8</td>
<td>2</td>
<td>4</td>
<td>9</td>
<td>1</td>
<td>7</td>
<td>5</td>
<td>11</td>
<td>3</td>
<td>14</td>
<td>10</td>
<td>0</td>
<td>6</td>
<td>13</td>
</tr>
</tbody>
</table>
<p>
<table>
<caption align="top">$S_2$</caption>
<tbody>
<tr>
<td>15</td>
<td>1</td>
<td>8</td>
<td>14</td>
<td>6</td>
<td>11</td>
<td>3</td>
<td>4</td>
<td>9</td>
<td>7</td>
<td>2</td>
<td>13</td>
<td>12</td>
<td>0</td>
<td>5</td>
<td>10</td>
</tr>
<tr>
<td>3</td>
<td>13</td>
<td>4</td>
<td>7</td>
<td>15</td>
<td>2</td>
<td>8</td>
<td>14</td>
<td>12</td>
<td>0</td>
<td>1</td>
<td>10</td>
<td>6</td>
<td>9</td>
<td>11</td>
<td>5</td>
</tr>
<tr>
<td>0</td>
<td>14</td>
<td>7</td>
<td>11</td>
<td>10</td>
<td>4</td>
<td>13</td>
<td>1</td>
<td>5</td>
<td>8</td>
<td>12</td>
<td>6</td>
<td>9</td>
<td>3</td>
<td>2</td>
<td>15</td>
</tr>
<tr>
<td>13</td>
<td>8</td>
<td>10</td>
<td>1</td>
<td>3</td>
<td>15</td>
<td>4</td>
<td>2</td>
<td>11</td>
<td>6</td>
<td>7</td>
<td>12</td>
<td>0</td>
<td>5</td>
<td>14</td>