查看: 92|回复: 0

[Reverse] 深入浅出IDEA

[复制链接]

22

主题

23

帖子

0

精华

VIP

Rank: 16

学币
10
荣耀
0
rank
0
违规
0

VIP

    发表于 2020-6-15 01:02:50 | 显示全部楼层 |阅读模式

    前言
      这几天玩的挺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[i] = (plaintext >> (48-i*16)) & 0xffff;
      然后根据种子密钥产生52个16bits的子密钥
    /* sub keys generation */
    
    status_t subkey_generation(uint16_t key[8], uint16_t sub_key[52])
    
    {
    
    int i, j;
    
    uint16_t tmp_key[8];
    
    for(i = 0; i < 8; i++)
    
    tmp_key[i] = key[i];
    
    for(i = 0; i < 6; i++)
    
    {
    
    for(j = 0; j < 8; j++)
    
    sub_key[i*8+j] = tmp_key[j];
    
    left_shift(tmp_key, 25);
    
    }
    
    for(i = 0; i < 4; i++)
    
    sub_key[48+i] = tmp_key[i];
    
    return IDEA_SUCCESS;
    
    }
      这 4 个子块将作为第一轮迭代的输入,全部共 8 轮迭代。
    for(i = 0; i < 8; i++)
    
    {
    
    idea_round(X, &(sub_key[i*6]), out);
    
    for(j = 0; j < 4; j++)
    
    X[j] = out[j];
    
    }
      在每一轮中,这 4 个子块相互异或、相加和相乘,且与 6 个 16 比特子密钥相异或、相加和相乘。
    status_t idea_round(uint16_t X[4], uint16_t Z[6], uint16_t out[4])
    
    {
    
    status_t st;
    
    uint16_t tmp[4], ma_in[2], ma_out[2];
    
    tmp[0] = mp_mod(X[0], Z[0]);    //step 1. multiply X1 by 1st sub key
    
    tmp[1] = add_mod(X[1], Z[1]);   //step 2. add X2 to 2nd sub key
    
    tmp[2] = add_mod(X[2], Z[2]);   //step 3. add X3 to 3rd sub key
    
    tmp[3] = mp_mod(X[3], Z[3]);    //step 4. multiply X4 by 4th sub key
    
    
    
    ma_in[0] = XOR(tmp[0], tmp[2]); //step 5. XOR results in step 1 and step 3
    
    ma_in[1] = XOR(tmp[1], tmp[3]); //step 6. XOR results in step 2 and step 4
    
    
    
    st = MA(ma_in, &Z[4], ma_out);  //step 7. MA diffusion
    
    
    
    /* step 8. generate the output*/
    
    out[0] = XOR(tmp[0], ma_out[1]);
    
    out[1] = XOR(tmp[1], ma_out[0]);
    
    out[2] = XOR(tmp[2], ma_out[1]);
    
    out[3] = XOR(tmp[3], ma_out[0]);
    
    swap(&(out[1]), &(out[2]));
    
    
    
    return st;
    
    }
      最后在输出变换中 4 个子块与 4 个子密钥进行运算。
    swap(&(out[1]), &(out[2]));
    
    out[0] = mp_mod(out[0], sub_key[48]);
    
    out[1] = add_mod(out[1], sub_key[49]);
    
    out[2] = add_mod(out[2], sub_key[50]);
    
    out[3] = mp_mod(out[3], sub_key[51]);
    
    *ciphertext = out[0];
      最后将4个16bits的密文拼接为64bits的密文
    for(i = 1; i <= 3; i++)
    
    *ciphertext = ((*ciphertext)<<16)|out[i];
    IDA数据流跟踪  IDA载入程序

    深入浅出IDEA

    深入浅出IDEA
      首先第一步,将明文拆分为4块

    深入浅出IDEA

    深入浅出IDEA
      来看下拆分之后的结果
      第一块

    深入浅出IDEA

    深入浅出IDEA
      所有4块

    深入浅出IDEA

    深入浅出IDEA
      所以我们呢得到4块数据
    0x1234
    0x5678
    0x9876
    0x5432
      然后经过子密钥生成函数,产生52个子密钥
      这个生成的过程没有细看,大概就是前48个来自同一种方法,后4个是种子密钥的前64位

    深入浅出IDEA

    深入浅出IDEA
      这样便产生了52个子密钥,先放在一边。

    深入浅出IDEA

    深入浅出IDEA
      接下来就需要处理明文,进入轮函数部分。总共有8轮,每一轮的输出作为下一轮的输入。

    深入浅出IDEA

    深入浅出IDEA
      在轮函数中做了许多操作。

    深入浅出IDEA

    深入浅出IDEA
      不过我们没必要深究为什么要这么运算,只要了解轮函数的大致特征就行了。
      第一轮输出

    深入浅出IDEA

    深入浅出IDEA
      这并不是用语言可以简单描述的变化,所以直接看下一步。
      接着经过轮函数加密后,密文又跟4个子密钥进行运算

    深入浅出IDEA

    深入浅出IDEA
      接着将拆分的密文合并成64bit的密文。

    深入浅出IDEA

    深入浅出IDEA
    解密过程  和加密密钥一样,解密密钥也需要拓展,不同的是解密密钥是由加密密钥加法逆或乘法逆构成的,且两者一一对应。
    IDEA算法的解密过程和加密过程一样,只是加密用加密密钥EK,解密用解密密钥DK。输入的密文同样为8个字符(即64比特),将64比特数据块分成Y1,Y2,Y3,Y4四个子块,每一个子块16比特。这4个子块将作为第一轮迭代的输入,全部共8轮迭代。
    IDA跟进  IDA载入解密函数

    深入浅出IDEA

    深入浅出IDEA
      整个流程是一模一样的,除了最后的swap函数的顺序。
      这里唯一需要关注的地方就是子密钥生成函数是不同的。

    深入浅出IDEA

    深入浅出IDEA

    深入浅出IDEA

    深入浅出IDEA
      而且解密函数的子密钥生成函数是和加密函数的子密钥生成有关联的,也就是说解密密钥是根据加密密钥生成的,这也就是EK和DK的关系,不过这里并不会去研究这两者之间究竟有怎么样的数学联系。
      后面都是一样,也就不多讲了。
    总结  IDEA算法的特征还是比较明显的,相加相乘以及异或运算 >.-:
    示例代码
    //main.c
    
    #include <stdio.h>
    #include <string.h>
    #include "IDEA.h"
    
    int main(void){
    uint16_t key[8] = {0x1234,0x5678,0x90ab,0x3456,0x5678,0x2345,0x1908,0x1235};
    uint64_t plaintext[] = {0x1234567898765432};
    int block_cnt = 0, i = 0, len;
    uint64_t ciphertext[1024]={0};
    
    idea_encrypt(plaintext[i], key, ciphertext);
    printf("0x%016llx\n", ciphertext[0]);
    
    idea_decrypt(ciphertext[0], key, &(plaintext[i]));
    printf("0x%016llx\n", plaintext[0]);
    
    }
    //IDEA.c
    
    /* IDEA(International Data Encryption Algorithm), refer to [url]http://www.quadibloc.com/crypto/co040302.htm[/url]
    
    * 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[8], 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[8], uint64_t *ciphertext)
    
    {
    
    uint16_t X[4], sub_key[52], out[4];
    
    status_t st;
    
    int i, j;
    
    
    
    /* cut 64-bit plaintext into 4 16-bit sub blocks */
    
    for(i = 0; i < 4; i++)
    
    X[i] = (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[i*6]), out);
    
    for(j = 0; j < 4; j++)
    
    X[j] = out[j];
    
    }
    
    
    
    /* 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[1]), &(out[2]));
    
    out[0] = mp_mod(out[0], sub_key[48]);
    
    out[1] = add_mod(out[1], sub_key[49]);
    
    out[2] = add_mod(out[2], sub_key[50]);
    
    out[3] = mp_mod(out[3], sub_key[51]);
    
    *ciphertext = out[0];
    
    for(i = 1; i <= 3; i++)
    
    *ciphertext = ((*ciphertext)<<16)|out[i];
    
    
    
    return st;
    
    }
    
    
    
    /* IDEA decryption */
    
    status_t idea_decrypt(uint64_t ciphertext, uint16_t key[8], uint64_t *plaintext)
    
    {
    
    status_t st;
    
    uint16_t X[4], sub_dkey[52], out[4];
    
    int i, j;
    
    
    
    for(i = 0; i < 4; i++)
    
    X[i] = (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[i*6]), out);
    
    for(j = 0; j < 4; j++)
    
    X[j] = out[j];
    
    }
    
    
    
    out[0] = mp_mod(out[0], sub_dkey[48]);
    
    out[1] = add_mod(out[1], sub_dkey[49]);
    
    out[2] = add_mod(out[2], sub_dkey[50]);
    
    out[3] = mp_mod(out[3], sub_dkey[51]);
    
    swap(&(out[1]), &(out[2]));     //Note that the unswap in decryption is called after transform, that is different from the encryption.
    
    
    
    *plaintext = out[0];
    
    for(i = 1; i <= 3; i++)
    
    *plaintext = ((*plaintext)<<16) | out[i];
    
    
    
    return st;
    
    }
    
    
    
    status_t idea_round(uint16_t X[4], uint16_t Z[6], uint16_t out[4])
    
    {
    
    status_t st;
    
    uint16_t tmp[4], ma_in[2], ma_out[2];
    
    tmp[0] = mp_mod(X[0], Z[0]);    //step 1. multiply X1 by 1st sub key
    
    tmp[1] = add_mod(X[1], Z[1]);   //step 2. add X2 to 2nd sub key
    
    tmp[2] = add_mod(X[2], Z[2]);   //step 3. add X3 to 3rd sub key
    
    tmp[3] = mp_mod(X[3], Z[3]);    //step 4. multiply X4 by 4th sub key
    
    
    
    ma_in[0] = XOR(tmp[0], tmp[2]); //step 5. XOR results in step 1 and step 3
    
    ma_in[1] = XOR(tmp[1], tmp[3]); //step 6. XOR results in step 2 and step 4
    
    
    
    st = MA(ma_in, &Z[4], ma_out);  //step 7. MA diffusion
    
    
    
    /* step 8. generate the output*/
    
    out[0] = XOR(tmp[0], ma_out[1]);
    
    out[1] = XOR(tmp[1], ma_out[0]);
    
    out[2] = XOR(tmp[2], ma_out[1]);
    
    out[3] = XOR(tmp[3], ma_out[0]);
    
    swap(&(out[1]), &(out[2]));
    
    
    
    return st;
    
    }
    
    
    
    /* MA diffusion */
    
    status_t MA(uint16_t ma_in[2], uint16_t sub_key[2],uint16_t ma_out[2])
    
    {
    
    uint16_t tmp[2];
    
    
    
    tmp[0] = mp_mod(ma_in[0], sub_key[0]);
    
    tmp[1] = add_mod(ma_in[1], tmp[0]);
    
    ma_out[1] = mp_mod(tmp[1], sub_key[1]);
    
    ma_out[0] = add_mod(tmp[0], ma_out[1]);
    
    
    
    return IDEA_SUCCESS;
    
    }
    
    
    
    /* sub keys generation */
    
    status_t subkey_generation(uint16_t key[8], uint16_t sub_key[52])
    
    {
    
    int i, j;
    
    uint16_t tmp_key[8];
    
    for(i = 0; i < 8; i++)
    
    tmp_key[i] = key[i];
    
    for(i = 0; i < 6; i++)
    
    {
    
    for(j = 0; j < 8; j++)
    
    sub_key[i*8+j] = tmp_key[j];
    
    left_shift(tmp_key, 25);
    
    }
    
    for(i = 0; i < 4; i++)
    
    sub_key[48+i] = tmp_key[i];
    
    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[8], uint16_t sub_dkey[52])
    
    {
    
    status_t st;
    
    int i;
    
    uint16_t sub_key[52];
    
    uint32_t tmp;
    
    
    
    st = subkey_generation(key, sub_key);
    
    
    
    st = extended_eucild(sub_key[48], IDEA_MP_MODULAR, &tmp);
    
    if(st != IDEA_SUCCESS)
    
    {
    
    printf("subdkey_generation error!/n");
    
    return st;
    
    }
    
    sub_dkey[0] = tmp == 65536 ? 0 : (uint16_t)tmp;
    
    sub_dkey[1] = (IDEA_ADD_MODULAR - sub_key[49]) % IDEA_ADD_MODULAR;
    
    sub_dkey[2] = (IDEA_ADD_MODULAR - sub_key[50]) % IDEA_ADD_MODULAR;
    
    st = extended_eucild(sub_key[51], IDEA_MP_MODULAR, &tmp);
    
    if(st != IDEA_SUCCESS)
    
    {
    
    printf("subdkey_generation error!/n");
    
    return st;
    
    }
    
    sub_dkey[3] = tmp == 65536 ? 0 : (uint16_t)tmp;
    
    
    
    for(i = 0; i < 8; i++)  //This is awful?!...May be I should make a table.
    
    {
    
    sub_dkey[4+i*6] = sub_key[52-(i+1)*6];
    
    sub_dkey[4+i*6+1] = sub_key[52-(i+1)*6+1];
    
    st = extended_eucild(sub_key[52-(i+1)*6-4], IDEA_MP_MODULAR, &tmp);
    
    if(st != IDEA_SUCCESS)
    
    {
    
    printf("subdkey_generation error!/n");
    
    return st;
    
    }
    
    sub_dkey[4+i*6+2] = tmp == 65536 ? 0 : (uint16_t)tmp;
    
    sub_dkey[4+i*6+3] = (IDEA_ADD_MODULAR - sub_key[52-(i+1)*6-2]) % IDEA_ADD_MODULAR;
    
    sub_dkey[4+i*6+4] = (IDEA_ADD_MODULAR - sub_key[52-(i+1)*6-3]) % IDEA_ADD_MODULAR;
    
    st = extended_eucild(sub_key[52-(i+1)*6-1], IDEA_MP_MODULAR, &tmp);
    
    if(st != IDEA_SUCCESS)
    
    {
    
    printf("subdkey_generation error!/n");
    
    return st;
    
    }
    
    sub_dkey[4+i*6+5] = tmp == 65536 ? 0 : (uint16_t)tmp;
    
    }
    
    return IDEA_SUCCESS;
    
    }
    
    
    
    /* left shift */
    
    static status_t left_shift(uint16_t key[8], int num)
    
    {
    
    uint16_t copy_key[8];
    
    int i;
    
    for(i = 0; i < 8; i++)
    
    copy_key[i] = key[i];
    
    for(i = 0; i < 8; i++)
    
    key[i] = (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[4], y[4], t[4], q;
    
    int i;
    
    x[1] = x[2] = 0;
    
    x[3] = k;
    
    y[1] = 0, y[2] = 1;
    
    y[3] = d == 0 ? (1<<16) : d;
    
    
    
    while(y[3] > 1)
    
    {
    
    q = x[3] / y[3];
    
    for(i = 1; i <= 3; i++)
    
    t[i] = x[i] - q*y[i];
    
    for(i = 1; i <= 3; i++)
    
    x[i] = y[i];
    
    for(i = 1; i <= 3; i++)
    
    y[i] = t[i];
    
    }
    
    if(y[3] == 1)
    
    {
    
    if(y[2] < 0)
    
    y[2] += k;
    
    *result = y[2];
    
    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 short  word_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[8], uint64_t *ciphertext);
    
    status_t idea_decrypt(uint64_t ciphertext, uint16_t key[8], uint64_t *plaintext);
    
    status_t idea_round(uint16_t X[4], uint16_t Z[6], uint16_t out[4]);
    
    status_t MA(uint16_t ma_in[2], uint16_t sub_key[2],uint16_t ma_out[2]);
    
    status_t subkey_generation(uint16_t key[8], uint16_t sub_key[52]);
    
    status_t subdkey_generation(uint16_t key[8], uint16_t sub_dkey[52]);
    
    status_t extended_eucild(uint16_t d, uint32_t k, uint32_t *result);
    
    
    
    #endif



    温馨提示:
    1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
    2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
    3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
    学逆向论坛-免费的逆向学习论坛
    微信公众号
    快速回复 返回顶部 返回列表