/*
A related key attack for RTEA.

23 02 2009
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define F(X) (((X<<6)^(X>>8))+X)

void rtea(uint32_t block[2], uint32_t key[8])
{
    // from ru.wikipedia.org
    int r;
    uint32_t a=block[0], b=block[1];
    for (r=0;r<64;r++)
    {
        b+=a+((a<<6)^(a>>8))+ (key[r%8]+r);
        r++;
        a+=b+((b<<6)^(b>>8))+ (key[r%8]+r);
    }
    block[0]=a; block[1]=b;
}

void req(uint32_t block[2], uint32_t key_relation[8])
{
    uint32_t key[8]={0x12345678,1,2,3,4,5,6,7};
    int i;
    for(i=0;i<8;i++)
        key[i]^=key_relation[i];
    rtea(block, key);
}

uint32_t rand32()
{
    return rand()^(rand()<<13)^(rand()<<24);
}

int main()
{
    uint32_t m1[2], m2[2];
    uint32_t r1[8], r2[8];
    int i;
    uint32_t A, B, k=0;

    srand(12345);

    while(1)
    {
        k++;
        do
        {
            A=rand32();
            B=A+0x80000000;
        } while(F(B)-F(A) != 0x80800000);
        m1[0]=A; m2[0]=B;
        m1[1]=m2[1]=rand32();

        r1[0]=r2[0]=(k&0xFF)<<23;
        for(i=1;i<8;i++)
            r1[i]=r2[i]=rand32();
        r2[0]^=0x7F800000;
        r2[1]^=0x80000000;
        r2[7]^=0x80000000;

        req(m1, r1);
        req(m2, r2);

        if(m1[0]+0x80000000==m2[0] && m1[1]==m2[1])
        {
            printf("key[0] & 0x7F800000 == 0x%08X\n", (k&0xFF)<<23);
            printf("%u related key queries.\n", k);
            return 0;
        }
    }
}