Generátor střídavého kroku - Alternating step generator

v kryptografie, an generátor střídavého kroku (ASG) je kryptografický generátor pseudonáhodných čísel použito v proudové šifry, na základě tří lineární zpětnovazební posuvné registry. Jeho výstup je kombinací dvou LFSR, které jsou střídavé (taktované) střídavě, v závislosti na výstupu třetí LFSR.

Návrh byl publikován v roce 1987 a patentován v roce 1989 C. G. Güntherem.[1][2]

Přehled

Posuvné registry s lineární zpětnou vazbou (LFSR) jsou, statisticky vzato, vynikající generátory pseudonáhod, s dobrou distribucí a jednoduchou implementací. Nelze je však použít tak, jak jsou, protože jejich výstup lze snadno předvídat.

ASG zahrnuje tři lineární zpětnovazební posuvné registry, které budeme pro pohodlí nazývat LFSR0, LFSR1 a LFSR2. Výstup jednoho z registrů rozhodne, který z ostatních dvou se má použít; například pokud výstup LFSR2 a 0, je taktován LFSR0, a pokud je výstup 1, je taktován LFSR1. Výstupem je exkluzivní NEBO posledního bitu produkovaného LFSR0 a LFSR1. Počáteční stav tří LFSR je klíč.

Obvykle používají LFSR primitivní polynomy zřetelného, ​​ale blízkého stupně, přednastaveného na nenulový stav, takže každý LFSR generuje a sekvence maximální délky. Za těchto předpokladů má výstup ASG prokazatelně dlouhé období, vysokou lineární složitost a rovnoměrné rozložení krátkých subsekvencí.

Příklad kódu v C:

/ * 16bitová hračka ASG (příliš malá pro praktické použití); návrat 0 nebo 1. * /nepodepsaný Hračka ASG16(prázdnota){  statický nepodepsaný / * nepodepsaný typ s minimálně 16 bity * /    lfsr2  = 0x8102, / * počáteční stav, 16 bitů, nesmí být 0 * /    lfsr1  = 0x4210, / * počáteční stav, 15 bitů, nesmí být 0 * /    lfsr0  = 0x2492; / * počáteční stav, 14 bitů, nesmí být 0 * /  / * LFSR2 použít x ^^ 16 + x ^^ 14 + x ^^ 13 + x ^^ 11 + 1 * /  lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;  -li (lfsr2&1)    / * LFSR1 použít x ^^ 15 + x ^^ 14 + 1 * /    lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;  jiný    / * LFSR0 použít x ^^ 14 + x ^^ 13 + x ^^ 3 + x ^^ 2 + 1 * /    lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;  vrátit se (lfsr0 ^ lfsr1)&1;}

ASG je velmi jednoduché implementovat do hardwaru. Zejména na rozdíl od zmenšující se generátor a samořezný generátor, při každém taktu se vytváří výstupní bit, který zajišťuje konzistentní výkon a odolnost vůči načasování útoků.

Bezpečnostní

Shahram Khazaei, Simon Fischer a Willi Meier[3] dát dešifrování ASG umožňující různé kompromisy mezi časovou složitostí a objemem výstupu potřebným k provedení útoku, např. s asymptotickou složitostí a bity, kde je velikost nejkratší ze tří LFSR.

Reference

  1. ^ Günther, C. G. (1988). „Střídavé krokové generátory řízené sekvencemi De Bruijn“. Pokroky v kryptologii - EUROCRYPT '87. Přednášky z informatiky. Berlín, Heidelberg: Springer. 304: 5–14. doi:10.1007/3-540-39118-5_2. ISBN  978-3-540-39118-0 - přes SpringerLink.
  2. ^ Gunther, Christoph-Georg (1989-03-28). "US4817145A - Generátor pro generování binárních šifrovacích sekvencí". Patenty Google.
  3. ^ Khazaei, Shahram; Fischer, Simon; Meier, Willi (2007). „Snížená složitost útoků na generátor střídavého kroku“. Vybrané oblasti v kryptografii. Přednášky z informatiky. Berlín, Heidelberg: Springer. 4876: 1–16. doi:10.1007/978-3-540-77360-3_1. ISBN  978-3-540-77360-3 - přes SpringerLink.
  • Schneier, Bruce. Aplikovaná kryptografie (p383-384), druhé vydání, John Wiley & Sons, 1996. ISBN  0-471-11709-9