. : New eShop! - Mobilní verze - Pandatron.cz - Pandatron.sk - Diskuzní fórum - Zakázkový vývoj : .
 
Šifra XTEA a její spojení s KEELOQ
14. března 2016 - 00:03 | Pandatron | Šifra XTEA a její spojení s KEELOQ | Komentářů: 0  

Šifra XTEA a její spojení s KEELOQ

Představení blokové šifry TEA a XTEA autorů Davida Wheelera a Rogera Needhama včetně její implementace na 8 bitový mikrokontrolér řady PIC firmy Microchip.

XTEA (eXtended TEA) je bloková šifra, vycházející z TEA, určená k nápravě původních nedostatků. Přičemž samotný šifrovací algoritmus TEA (Tiny Encryption Algorithm) je unikátní vysokým stupněm odolnosti, doprovázený vysokým výkonem, který pochází z velice krátkého zdrojového kódu.

Následující zdrojový kód představuje kompletní referenční implementaci algoritmu TEA, který jako public domain uveřejnili autoři David Wheeler a Roger Needham z Cambridge Computer Laboratory.

 
#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

Obr. 1: Diagram funkce TEA

Oba zmínění autoři stojí i za rozšířením do podoby XTEA, uveřejněné v původně nepublikované technické zprávě již roku 1997. Algoritmus není předmětem žádného patentu a je tak volně k dispozici v podobě kompletní dokumentace i ukázkového zdrojového kódu.

Stejně jako TEA i XTEA je založena na 64 bitovém bloku Feistelovy sítě se 128 bitovým klíčem a doporučenými 64 použitími Feistelovy sítě, což odpovídá 32 průchodům. Narozdíl od předchozí implementace využívá XTEA složitější klíč, návrh i nové uspořádání funkcí XOR apod.

Feistelova síť představuje většinu dnes používaných blokových algoritmů a setkáme se s ní tak například v DES, Blowfish, FEAL, Lucifer, GOST či CAST. Její základní myšlenka (pocházející z počátku 70. let 20. st.) je taková, že vstupní blok o n bitech rozdělíme na 2 části délky n/2 bitů (n tedy musí být sudé), které označíme L a R. Následně je potřeba definovat interaktivní blokový algoritmus, kde vstup do i-té rundy je výstupem vždy rundy předcházející:

Li = Ri-1

Ri = Li-1 XOR f(Ri-1, Ki)

kde Ki je subklíč použitý v i-té rundě a f je libovolná funkce

Reverzibilnost tohoto algoritmu je dána reverzibilností funkce XOR, bez ohledu na to jak složitá je funkce f. Neboť platí:

Li-1 XOR f(Ri-1, Ki) XOR f(Ri-1, Ki) = Li-1

Následuje referenční zdrojový kód pro šifru XTEA a funkční diagram:

 
#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key in k[0] - k[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const k[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const k[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

Obr. 2: Diagram funkce XTEA

XTEA a KEELOQ®
Samotnou implementaci šifry XTEA na obvodech KEELOQ® firmy Microchip podrobně popisuje nyní uveřejněná aplikační poznámka AN1285 - KEELOQ® with XTEA Encryption Receiver/Decoder, doplněná o kompletní zdrojové kódy volně dostupné u firmy Microchip. Jako demonstrace možností je zde provedena implementace na mikrokontrolér střední třídy - PIC16F886 a díky využití možností XTEA je tak dosažen vysoký stupeň zabezpečení přenosu dat.


Obr. 3: Struktura implementace XTEA a KEELOQ

Základní vlastnosti modulů v AN1285:

  • Zdrojový kód plně kompatibilní s HI-TECH C
  • Hardware kompatibilní s KEELOQ 3 Development Kit
  • Přijímač je s využitím vnitřní paměti schopen naučit se až osm vysílačů
  • Radio Receive rutiny (PWM) obsluhované v přerušení
  • Kompatibilní s KEELOQ XTEA s TE = 200 µs
  • Šifrovaná data zahrnují 32 bitový čítač, 8 funkčních bitů a 24 uživatelsky definovaných bitů
  • Automatická synchronizace během příjmu pomocí 8MHz interního oscilátoru
  • Zařazeny I2C Slave rutiny pro větší kontrolu systému
  • LCD rutiny určeny pro zobrazení dešifrovaných dat a zpráv

Příjem dat:
Přijímací programový modul byl vyvinut s využitím rychlého přerušení ISR (Interrupt Service Routine). Celá funkce je realizována jako jednoduchý autonomní kód, pracující na dané časové základně s intervalem 60 µs. Práce kódu modulu je pro hlavní program zcela transparentní a výsledek příjmu 104 bitů kódované zprávy je uložen ve 13 bytech přijímacího bufferu. Hlavnímu programu je oznámen ukončený příjem nastavením bitu RF_FULL a tím je veškerá funkce přijímacího modulu ukončena. Hlavní program je následně zodpovědný za vyzvednutí přijatých dat a smazání stavového bitu.

Pro snížení nároků na zdroj hodinového signálu a možnost použití interního RC oscilátoru je přijímač automaticky aktivován každých 60 µs, kdy se snaží detekovat pokus o synchronizaci.



Obr. 4: Formát a struktura přenášených dat

Generování klíče:
Za generování šifrovacího klíče je zodpovědná funkce XTEAKeyGen() ze souboru xtea_keygen.c. Vstupními daty funkce může být výrobní nebo sériové 32 bitové číslo.

Generování 128 bitového klíče probíhá ve dvou fázích, neboť funkce poskytuje pouze 64 bitový výsledek. Pro prvních (LSB) 64 bitů generovaného klíče je tak možné funkci předat například 32 bitový klíč vynásobený hodnotou 0x55555555 a pro druhý klíč (MSB) naopak vynásobený hodnotou 0xAAAAAAAA. Tím je zajištěna dostatečná míra bezpečnosti i unikátnost výsledného 128 bitového klíče.

XTEA funkce:
Samotné šifrování i dešifrování zpráv probíhá prostřednictvím jediné společné funkce Xtea_Decrypt(), pracující podle výše popsaných algoritmů. Funkce vyžaduje dodání 104 bitů dat a 128 bitového klíče. Následně jsou výsledná data uložena v bufferu, kde jsou opět k dispozici hlavnímu programu.

Více informací o samotné implementaci je možné nalézt v již zmíněné aplikační poznámce AN1286 či dostupných zdrojových kódech. Další informace o principech šifrování dat je poté možné nalézt i v aplikační poznámce AN953 - Data Encryption Routines for the PIC18.

Odkazy & Download:
Domovská stránka firmy Microchip

Tiny Encryption Algorithm
XTEA
AN1285 - KeeLoq with XTEA Encryption Receiver/Decoder
AN953 - Data Encryption Routines for the PIC18
Více o teorii blokových šifer







GooglePlus1 FaceBook Twitter del.icio.us DiGG Google StumbleUpon Google Buzz Email RSS PDF Tisk

Komentáře:
Název příspěvku: Vaše jméno: host
                 
  Zakázat formátování [Zakáže kódování a nahrazování smajlíky.]
Připojit soubory
reklama:
Bluetooth modul BTM-112
BTM-112 je snadno dostupný Bluetooth modul výrobce Rayson.
Skladem od 208 Kč

Informace uvedené v článcích jsou platné v době jejich vydání a samotné články jsou určeny pouze jako zdroj informací. Autor článku ani správce webu nenesou žádnou zodpovědnost za případné újmy na majetku a zdraví. Názvy společností a výrobků, loga a další multimediální materiál mohou být ochrannými známkami příslušných společností.
RSS kanály: | |
+420 723 846 377
info@pandatron.cz
Všechna práva vyhrazena | mobilní verze | © Copyright 2000 - 2016 ISSN 1803-6007