深入浅出IDEA
前言 这几天玩的挺Hi，是时候学习了。
原理简介 IDEA算法是在DES算法的基础上发展出来的，是一个分组长度为 64 比特的分组密码算法，密钥长度为 128 比特，由 8 轮迭代操作实现。 每个迭代都由三种函数：mod（216）加法、mod（216+1）乘法和逐位异或算法组成。整个算法包括子密钥产生、数据加密过程、数据解密过程三部分。 该算法规定明文和密文块均为 64 比特，密钥长度为 128比特，加解密相同，只是密钥各异。
加密过程 IDEA 总共进行 8 轮迭代操作，每轮需要 6 个子密钥，另外还需要 4 个额外子密钥输出变换，所以总共需要 52 个子密钥，这 52 个子密钥都是从 128 比特密钥中扩展出来的。
代码一览 输入的明文为 8 个字符（即 64 比特），首先需要将 64 比特数据块分成 X1,X2,X3,X4 四个子块，每一子块 16 比特。
for(i = 0; i < 4; i++)
X = (plaintext >> (48-i*16)) & 0xffff; 然后根据种子密钥产生52个16bits的子密钥
/* sub keys generation */
status_t subkey_generation(uint16_t key, uint16_t sub_key)
{
int i, j;
uint16_t tmp_key;
for(i = 0; i < 8; i++)
tmp_key = key;
for(i = 0; i < 6; i++)
{
for(j = 0; j < 8; j++)
sub_key = tmp_key;
left_shift(tmp_key, 25);
}
for(i = 0; i < 4; i++)
sub_key = tmp_key;
return IDEA_SUCCESS;
} 这 4 个子块将作为第一轮迭代的输入，全部共 8 轮迭代。
for(i = 0; i < 8; i++)
{
idea_round(X, &(sub_key), out);
for(j = 0; j < 4; j++)
X = out;
} 在每一轮中，这 4 个子块相互异或、相加和相乘，且与 6 个 16 比特子密钥相异或、相加和相乘。
status_t idea_round(uint16_t X, uint16_t Z, uint16_t out)
{
status_t st;
uint16_t tmp, ma_in, ma_out;
tmp = mp_mod(X, Z); //step 1. multiply X1 by 1st sub key
tmp = add_mod(X, Z); //step 2. add X2 to 2nd sub key
tmp = add_mod(X, Z); //step 3. add X3 to 3rd sub key
tmp = mp_mod(X, Z); //step 4. multiply X4 by 4th sub key
ma_in = XOR(tmp, tmp); //step 5. XOR results in step 1 and step 3
ma_in = XOR(tmp, tmp); //step 6. XOR results in step 2 and step 4
st = MA(ma_in, &Z, ma_out);//step 7. MA diffusion
/* step 8. generate the output*/
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
swap(&(out), &(out));
return st;
} 最后在输出变换中 4 个子块与 4 个子密钥进行运算。
swap(&(out), &(out));
out = mp_mod(out, sub_key);
out = add_mod(out, sub_key);
out = add_mod(out, sub_key);
out = mp_mod(out, sub_key);
*ciphertext = out; 最后将4个16bits的密文拼接为64bits的密文
for(i = 1; i <= 3; i++)
*ciphertext = ((*ciphertext)<<16)|out;IDA数据流跟踪 IDA载入程序
首先第一步，将明文拆分为4块
来看下拆分之后的结果
第一块
所有4块
所以我们呢得到4块数据
0x1234
0x5678
0x9876
0x5432 然后经过子密钥生成函数，产生52个子密钥
这个生成的过程没有细看，大概就是前48个来自同一种方法，后4个是种子密钥的前64位
这样便产生了52个子密钥，先放在一边。
接下来就需要处理明文，进入轮函数部分。总共有8轮，每一轮的输出作为下一轮的输入。
在轮函数中做了许多操作。
不过我们没必要深究为什么要这么运算，只要了解轮函数的大致特征就行了。
第一轮输出
这并不是用语言可以简单描述的变化，所以直接看下一步。
接着经过轮函数加密后，密文又跟4个子密钥进行运算
接着将拆分的密文合并成64bit的密文。
解密过程 和加密密钥一样，解密密钥也需要拓展，不同的是解密密钥是由加密密钥加法逆或乘法逆构成的，且两者一一对应。
IDEA算法的解密过程和加密过程一样，只是加密用加密密钥EK，解密用解密密钥DK。输入的密文同样为8个字符（即64比特），将64比特数据块分成Y1，Y2，Y3，Y4四个子块，每一个子块16比特。这4个子块将作为第一轮迭代的输入，全部共8轮迭代。
IDA跟进 IDA载入解密函数
整个流程是一模一样的，除了最后的swap函数的顺序。
这里唯一需要关注的地方就是子密钥生成函数是不同的。
而且解密函数的子密钥生成函数是和加密函数的子密钥生成有关联的，也就是说解密密钥是根据加密密钥生成的，这也就是EK和DK的关系，不过这里并不会去研究这两者之间究竟有怎么样的数学联系。
后面都是一样，也就不多讲了。
总结 IDEA算法的特征还是比较明显的，相加相乘以及异或运算 >.-:
示例代码//main.c
#include <stdio.h>
#include <string.h>
#include "IDEA.h"
int main(void){
uint16_t key = {0x1234,0x5678,0x90ab,0x3456,0x5678,0x2345,0x1908,0x1235};
uint64_t plaintext[] = {0x1234567898765432};
int block_cnt = 0, i = 0, len;
uint64_t ciphertext={0};
idea_encrypt(plaintext, key, ciphertext);
printf("0x%016llx\n", ciphertext);
idea_decrypt(ciphertext, key, &(plaintext));
printf("0x%016llx\n", plaintext);
}//IDEA.c
/* IDEA(International Data Encryption Algorithm), refer to http://www.quadibloc.com/crypto/co040302.htm
* IDEA.c, an IDEA encryption and decryption program.
* Author shenyang
* Mar. 4th, 2011
* TODO: Fault analysis on IDEA, defence of fault analysis on IDEA.
*/
#ifndef IDEA_H
#include "IDEA.h"
#endif
#include <string.h>
#include <stdio.h>
/* define operation */
static uint16_t add_mod(uint16_t a, uint16_t b);
static uint16_t mp_mod(uint16_t a,uint16_t b);
static uint16_t XOR(uint16_t a, uint16_t b);
static status_t left_shift(uint16_t key, int num);
static void swap(uint16_t *a, uint16_t *b);
/* addition and mod 65536 */
static uint16_t add_mod(uint16_t a, uint16_t b)
{
uint32_t tmp = a+b;
uint16_t ret = tmp % IDEA_ADD_MODULAR;
return ret;
}
/* multiply and mod 65537 */
static uint16_t mp_mod(uint16_t a,uint16_t b)
{
/* Note: In IDEA, for purposes of multiplication, a 16 bit word containing all zeroes is considered to represent the number 65,536;
* other numbers are represented in conventional unsigned notation, and multiplication is modulo the prime number 65,537
*/
uint64_t tmp, tmp_a, tmp_b; //if both a and b are 2^16, the result will be 2^32 which will exceed a 32-bit int
tmp_a = a==0 ? (1<<16) : a;
tmp_b = b==0 ? (1<<16) : b;
tmp = (tmp_a * tmp_b) % IDEA_MP_MODULAR;
return (uint16_t)(tmp);
}
/* XOR */
static uint16_t XOR(uint16_t a, uint16_t b)
{
return a^b;
}
static void swap(uint16_t *a, uint16_t *b)
{
uint16_t c = 0;
c = *a;
*a = *b;
*b = c;
}
/* IDEA encryption */
status_t idea_encrypt(uint64_t plaintext, uint16_t key, uint64_t *ciphertext)
{
uint16_t X, sub_key, out;
status_t st;
int i, j;
/* cut 64-bit plaintext into 4 16-bit sub blocks */
for(i = 0; i < 4; i++)
X = (plaintext >> (48-i*16)) & 0xffff;
/* generate sub keys */
st = subkey_generation(key, sub_key);
for(i = 0; i < 8; i++)
{
idea_round(X, &(sub_key), out);
for(j = 0; j < 4; j++)
X = out;
}
/* round 9, do output transform */
//Note that the swap of B and C is not performed after round 8. So we swap them again.
swap(&(out), &(out));
out = mp_mod(out, sub_key);
out = add_mod(out, sub_key);
out = add_mod(out, sub_key);
out = mp_mod(out, sub_key);
*ciphertext = out;
for(i = 1; i <= 3; i++)
*ciphertext = ((*ciphertext)<<16)|out;
return st;
}
/* IDEA decryption */
status_t idea_decrypt(uint64_t ciphertext, uint16_t key, uint64_t *plaintext)
{
status_t st;
uint16_t X, sub_dkey, out;
int i, j;
for(i = 0; i < 4; i++)
X = (ciphertext >> (48-i*16)) & 0xffff;
/* generate sub keys for decryption*/
st = subdkey_generation(key, sub_dkey);
if(st != IDEA_SUCCESS)
return st;
for(i = 0; i < 8; i++)
{
idea_round(X, &(sub_dkey), out);
for(j = 0; j < 4; j++)
X = out;
}
out = mp_mod(out, sub_dkey);
out = add_mod(out, sub_dkey);
out = add_mod(out, sub_dkey);
out = mp_mod(out, sub_dkey);
swap(&(out), &(out)); //Note that the unswap in decryption is called after transform, that is different from the encryption.
*plaintext = out;
for(i = 1; i <= 3; i++)
*plaintext = ((*plaintext)<<16) | out;
return st;
}
status_t idea_round(uint16_t X, uint16_t Z, uint16_t out)
{
status_t st;
uint16_t tmp, ma_in, ma_out;
tmp = mp_mod(X, Z); //step 1. multiply X1 by 1st sub key
tmp = add_mod(X, Z); //step 2. add X2 to 2nd sub key
tmp = add_mod(X, Z); //step 3. add X3 to 3rd sub key
tmp = mp_mod(X, Z); //step 4. multiply X4 by 4th sub key
ma_in = XOR(tmp, tmp); //step 5. XOR results in step 1 and step 3
ma_in = XOR(tmp, tmp); //step 6. XOR results in step 2 and step 4
st = MA(ma_in, &Z, ma_out);//step 7. MA diffusion
/* step 8. generate the output*/
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
out = XOR(tmp, ma_out);
swap(&(out), &(out));
return st;
}
/* MA diffusion */
status_t MA(uint16_t ma_in, uint16_t sub_key,uint16_t ma_out)
{
uint16_t tmp;
tmp = mp_mod(ma_in, sub_key);
tmp = add_mod(ma_in, tmp);
ma_out = mp_mod(tmp, sub_key);
ma_out = add_mod(tmp, ma_out);
return IDEA_SUCCESS;
}
/* sub keys generation */
status_t subkey_generation(uint16_t key, uint16_t sub_key)
{
int i, j;
uint16_t tmp_key;
for(i = 0; i < 8; i++)
tmp_key = key;
for(i = 0; i < 6; i++)
{
for(j = 0; j < 8; j++)
sub_key = tmp_key;
left_shift(tmp_key, 25);
}
for(i = 0; i < 4; i++)
sub_key = tmp_key;
return IDEA_SUCCESS;
}
/* sub dkeys generation
*
*The decryption key schedule is:
*
*The first four subkeys for decryption are:
*
*KD(1) = 1/K(49)
*KD(2) =-K(50)
*KD(3) =-K(51)
*KD(4) = 1/K(52)
*
*and they do not quite follow the same pattern as the remaining subkeys which follow.
*
*The following is repeated eight times, adding 6 to every decryption key's index and subtracting 6 from every encryption key's index:
*
*KD(5)= K(47)
*KD(6)= K(48)
*
*KD(7)= 1/K(43)
*KD(8)=-K(45)
*KD(9)=-K(44)
*KD(10) = 1/K(46)
*
*/
status_t subdkey_generation(uint16_t key, uint16_t sub_dkey)
{
status_t st;
int i;
uint16_t sub_key;
uint32_t tmp;
st = subkey_generation(key, sub_key);
st = extended_eucild(sub_key, IDEA_MP_MODULAR, &tmp);
if(st != IDEA_SUCCESS)
{
printf("subdkey_generation error!/n");
return st;
}
sub_dkey = tmp == 65536 ? 0 : (uint16_t)tmp;
sub_dkey = (IDEA_ADD_MODULAR - sub_key) % IDEA_ADD_MODULAR;
sub_dkey = (IDEA_ADD_MODULAR - sub_key) % IDEA_ADD_MODULAR;
st = extended_eucild(sub_key, IDEA_MP_MODULAR, &tmp);
if(st != IDEA_SUCCESS)
{
printf("subdkey_generation error!/n");
return st;
}
sub_dkey = tmp == 65536 ? 0 : (uint16_t)tmp;
for(i = 0; i < 8; i++)//This is awful?!...May be I should make a table.
{
sub_dkey = sub_key;
sub_dkey = sub_key;
st = extended_eucild(sub_key, IDEA_MP_MODULAR, &tmp);
if(st != IDEA_SUCCESS)
{
printf("subdkey_generation error!/n");
return st;
}
sub_dkey = tmp == 65536 ? 0 : (uint16_t)tmp;
sub_dkey = (IDEA_ADD_MODULAR - sub_key) % IDEA_ADD_MODULAR;
sub_dkey = (IDEA_ADD_MODULAR - sub_key) % IDEA_ADD_MODULAR;
st = extended_eucild(sub_key, IDEA_MP_MODULAR, &tmp);
if(st != IDEA_SUCCESS)
{
printf("subdkey_generation error!/n");
return st;
}
sub_dkey = tmp == 65536 ? 0 : (uint16_t)tmp;
}
return IDEA_SUCCESS;
}
/* left shift */
static status_t left_shift(uint16_t key, int num)
{
uint16_t copy_key;
int i;
for(i = 0; i < 8; i++)
copy_key = key;
for(i = 0; i < 8; i++)
key = (copy_key[(i+num/16)%8]<<(num%16)) | (copy_key[(i+num/16+1)%8]>>(16-num%16));
return IDEA_SUCCESS;
}
/* Extended Eucild Algorithm to caculate d^-1 mod k*/
status_t extended_eucild(uint16_t d, uint32_t k, uint32_t *result)
{
int x, y, t, q;
int i;
x = x = 0;
x = k;
y = 0, y = 1;
y = d == 0 ? (1<<16) : d;
while(y > 1)
{
q = x / y;
for(i = 1; i <= 3; i++)
t = x - q*y;
for(i = 1; i <= 3; i++)
x = y;
for(i = 1; i <= 3; i++)
y = t;
}
if(y == 1)
{
if(y < 0)
y += k;
*result = y;
return IDEA_SUCCESS;
}
else
return IDEA_ERROR;
}//IDEA.h
/* IDEA.h */
#ifndef IDEA_H
#define IDEA_H
/* define return status */
#define IDEA_SUCCESS 0
#define IDEA_ERROR 1
/* define data length */
#define IDEA_KEY_LEN 128
#define IDEA_BLOCK_SIZE 64
#define IDEA_SUB_BLOCK_SIZE 16
/* define global variable */
#define IDEA_ADD_MODULAR 65536
#define IDEA_MP_MODULAR 65537
/* define operation mode */
#define ECB 0
#define CBC 1
#define CFB 2
#define OFB 3
/* define data type */
//typedef bool bit_t, status_t;
typedef unsigned char byte_t, uint8_t;
typedef unsigned shortword_t, uint16_t;
typedef unsigned int dword_t, uint32_t, status_t;
typedef unsigned long long uint64_t;
/* declare fuction */
status_t idea_encrypt(uint64_t plaintext, uint16_t key, uint64_t *ciphertext);
status_t idea_decrypt(uint64_t ciphertext, uint16_t key, uint64_t *plaintext);
status_t idea_round(uint16_t X, uint16_t Z, uint16_t out);
status_t MA(uint16_t ma_in, uint16_t sub_key,uint16_t ma_out);
status_t subkey_generation(uint16_t key, uint16_t sub_key);
status_t subdkey_generation(uint16_t key, uint16_t sub_dkey);
status_t extended_eucild(uint16_t d, uint32_t k, uint32_t *result);
#endif
页:
[1]