Samořezný generátor - Self-shrinking generator
A samořezný generátor je generátor pseudonáhod to je založeno na zmenšující se generátor pojem. Varianty samo zmenšovacího generátoru založené na a posuvný registr lineární zpětné vazby (LFSR) jsou studovány pro použití v kryptografie.
Algoritmus
Na rozdíl od zmenšující se generátor, který používá druhý zpětnovazební posuvný registr k řízení výstupu prvního, samo zmenšující se generátor používá střídavé výstupní bity jednoho registru k ovládání jeho konečného výstupu. Postup taktování tohoto druhu generátoru je následující:
- Taktujte LFSR dvakrát, abyste získali pár bitů jako výstup LFSR.
- Pokud je pár 10, výstup nula.
- Pokud je pár 11 výstup jeden.
- Jinak nic nevydá.
- Vraťte se k prvnímu kroku.
Příklad
V tomto příkladu bude použit polynom připojení X8 + x4 + x3 + x2 + 1a počáteční vyplnění registru 1 0 1 1 0 1 1 0.
Níže uvedená tabulka uvádí seznam pro každou iteraci LFSR, jeho mezivýstup před vlastním smrštěním, stejně jako konečný výstup generátoru. Polohy odboček definované polynomem připojení jsou označeny modrými záhlavími. Stav nulové iterace představuje počáteční vstup.
| Iterace # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | Mezilehlý výstup | Výstup generátoru |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N / A | N / A |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | N / A |
| 2 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 3 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 4 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
Na konci čtyř iterací se vytvoří následující sekvence mezilehlých bitů: 0110.
První pár bitů 01, je zahozeno, protože se také neshoduje 10 nebo 11. Druhý pár bitů 10, odpovídá druhému kroku algoritmu, takže je na výstupu nula.
Další bity se vytvářejí pokračováním v taktování LFSR a zmenšením jeho výstupu, jak je popsáno výše.
Kryptoanalýza
Ve svém příspěvku[1] Meier a Steffelbach dokazují, že samo zmenšující se generátor založený na LFSR s připojovacím polynomem délky L má za následek období výstupní sekvence alespoň 2L / 2a lineární složitost alespoň 2L / 2-1.
Dále ukazují, že každý smršťovací generátor může být reprezentován jako smršťovací generátor. Platí také inverze: Jakýkoli zmenšující se generátor lze implementovat jako samo zmenšující se generátor, i když výsledný generátor nemusí mít maximální délku.
Útok představený autory vyžaduje přibližně 20,7 l kroky, za předpokladu známého polynomu připojení.
Pokročilejší útok,[2] objeven Mihaljevićem, je schopen rozbít registr o délce sto bitů asi za 257 kroky, s použitím výstupní sekvence pouze 4,9 x 108 bity.
Další útok [3]
Reference
- ^ „Self-shrrating generator“, Advances in Cryptology-Eurocrypt 1994 (LNCS 950), 205-214, 1995.
- ^ „Bezpečnostní zkouška samořezného generátoru“, Circencester, Velká Británie, prosinec 1995.
- ^ Zenner, Erik; Krause, Matthias; Štěstí, Stefane. „Vylepšená kryptoanalýza samořezného generátoru“. Informační bezpečnost a soukromí 13. Australasian Conference ACISP 2008: 30. Citováno 12. dubna 2016.