Skip to content

IDEA

Warning

The current page still doesn't have a translation for this language.

You can read it through Google Translate.

Besides, you can also help to translate it: Contributing.

概述

国际数据加密算法(International Data Encryption Algorithm,IDEA),最早称为改良建议加密标准(Improved Proposed Encryption Standard,IPES),是密码学上一种对称密钥分组密码,由 James Massey 与来学嘉设计,在1991年首次提出。这个算法的提出,是为了取代旧有的数据加密标准 DES。(来自维基百科)

基本流程

密钥生成

IDEA 在加密的每轮中使用 6个密钥,然后最后输出轮使用4个密钥。所以一共有52个。

  1. 前8个密钥来自与该算法最初的密钥,K1 取自密钥的高16比特,K8 取自密钥的低16比特。
  2. 将密钥循环左移 25 位获取下一轮密钥,然后再次分为8组。

加密流程

IDEA 加密的数据块的大小为 64 比特,其使用的密钥长度为128 比特。该算法会对输入的数据块进行8次相同的变换,只是每次使用的密钥不同,最后会进行一次输出变换。每一轮的操作

可以输入和输出都是 16 比特位一组。每一轮的主要执行的运算有

  • 按位异或,⊕
  • 模加,模数为 2^{16} ,⊞
  • 模乘,模数为 2^{16}+1 ,⊙。但是需要注意的是 0x0000 的输入会被修改为 2^{16}2^{16} 的输出结果会被修改为0x0000。

这里我们称由 K5,K6 构成的中间那个方格的加密方式为MA。这也是 IDEA 算法中重要的一部分,此外,我们称 MA_L 为该部分加密后的左侧结果,其最后会和最左边的 16 比特操作;MA_R 为该部分加密后的右半部分的结果,其最后会和第三个 16 比特操作。

在最后输出轮的操作如下

解密流程

解密流程与加密流程相似,主要在于其密钥的选取

  • 第 i(1-9) 轮的解密的密钥的前 4 个子密钥由加密过程中第10-i 轮的前 4 个子密钥得出
  • 其中第 1 个和第 4 个解密子密钥为相应的子密钥关于 2^{16}+1 的乘法逆元。
  • 第 2 个和第 3 个子密钥的取法为
    • 当轮数为2,...,8时,取相应的第3个和第2个的子密钥的2^{16} 的加密逆元。
    • 当轮数为 1 或 9 时,取相应的第 2 个和第 3 个子密钥对应的2^{16} 的加密逆元。
  • 第 5 和第 6 个密钥不变。

总体流程

我们来证明一下算法的正确性,这里我们关注于解密算法的第一轮,首先我们先看一下Y_i 是如何得到的

Y_1 = W_{81} \odot Z_{49}

Y_2=W_{83}\boxplus Z_{50}

Y_3=W_{82}\boxplus Z_{51}

Y_4=W_{83}\odot Z_{52}

解密时,第一轮直接进行的变换为

J_{11}=Y_1 \odot U_1=Y_1 \odot Z_{49}^{-1}=W_{81}

J_{12}=Y_2 \boxplus U2=Y_2\boxplus Z_{50}^{-1}=W_{83}

J_{13}=Y_3 \boxplus U3=Y_3\boxplus Z_{51}^{-1}=W_{82}

J_{14}=Y_4 \odot U_4=Y_4 \odot Z_{52}^{-1}=W_{84}

可以看出得到的结果只有中间的两个16位加密结果恰好相反。我们进一步看一下W_{8i} 是如何得到的。

W_{81}=I_{81} \oplus MA_R(I_{81}\oplus I_{83},I_{82}\oplus I_{84})

W_{82}=I_{83} \oplus MA_R(I_{81}\oplus I_{83},I_{82}\oplus I_{84})

W_{83}=I_{82} \oplus MA_L(I_{81}\oplus I_{83},I_{82}\oplus I_{84})

W_{84}=I_{84} \oplus MA_L(I_{81}\oplus I_{83},I_{82}\oplus I_{84})

那么对于V11来说

V_{11}=J_{11} \oplus MA_R(J_{11}\oplus J_{13},J_{12}\oplus J_{14})

通过简单带入已有的值,显然

V_{11}=W_{81} \oplus MA_R(I_{81}\oplus I_{83},I_{82} \oplus I_{84})=I_{81}

对于其他的元素也类似,那么其实我们会发现第一轮解密后的结果恰好是I_{81},I_{83},I_{82},I_{84}

类似地,这个关系可以一直满足直到

V_{81}=I_{11},V_{82}=I_{13},V_{83}=I_{12},V_{84}=I_{14}

那么最后再经过一次简单的输出变换,恰好得到最初加密的数值。

题目

  • 2017 HITCON seccomp