Generátor smršťování - Shrinking generator

v kryptografie, zmenšující se generátor je forma generátor pseudonáhodných čísel určené k použití v a proudová šifra. To bylo vydáváno v Crypto 1993 autorem Don Coppersmith, Hugo Krawczyk, a Yishay Mansour.[1]

Generátor smršťování používá dva posuvné registry lineární zpětné vazby. Jeden s názvem A sekvence, generuje výstupní bity, zatímco druhá, nazývaná S sekvence, řídí jejich výstup. Oba A a S jsou taktované; pokud S bit je 1, pak A bit je výstup; pokud S bit je 0, A bit je zahozen, nic není na výstupu a my hodiny znovu registrujeme. To má tu nevýhodu, že výstupní rychlost generátoru se mění nepravidelně, a to způsobem naráží na stav S.; tento problém lze překonat vyrovnávací pamětí výstupu. Náhodná sekvence generovaná LFSR nemůže zaručit nepředvídatelnost v zabezpečeném systému a byly navrženy různé metody pro zlepšení jeho náhodnosti [2]

Navzdory této jednoduchosti v současné době neexistují žádné známé útoky lepší než vyčerpávající hledání, když jsou zpětnovazební polynomy tajné. Pokud jsou známy zpětnovazební polynomy, nejznámější útok vyžaduje méně než A • S bity výstupu.[3]

Zajímavou variantou je samořezný generátor.

Implementace v Pythonu

Tento příklad používá dva Galois LFRS k výrobě výstupního pseudonáhodného bitového toku. Kód Pythonu lze použít k šifrování a dešifrování souboru nebo jakéhokoli bytestreamu.

#! / usr / bin / env python3import sys# ----------------------------------------------------------------------------# Zde začínají funkce Crypto4o# ----------------------------------------------------------------------------třída GLFSR:    "" "Galoisův lineární zpětnovazební posuvný registr." ""    def __init__(já, polynom, počáteční hodnota):        tisk "Používám polynom 0x%X, počáteční hodnota: 0x%X." % (polynom, počáteční hodnota)        já.polynom = polynom | 1        já.data = počáteční hodnota        tmp = polynom        já.maska = 1        zatímco tmp != 0:            -li tmp & já.maska != 0:                tmp ^= já.maska            -li tmp == 0:                přestávka            já.maska <<= 1    def next_state(já):        já.data <<= 1        odplata = 0        -li já.data & já.maska != 0:            odplata = 1            já.data ^= já.polynom        vrátit se odplatatřída SPRNG:    def __init__(já, polynom_d, init_value_d, polynom_c, init_value_c):        tisk "GLFSR D0:",        já.glfsr_d = GLFSR(polynom_d, init_value_d)        tisk "GLFSR C0:",        já.glfsr_c = GLFSR(polynom_c, init_value_c)    def next_byte(já):        byte = 0        bitpos = 7        zatímco Skutečný:            bit_d = já.glfsr_d.next_state()            bit_c = já.glfsr_c.next_state()            -li bit_c != 0:                bit_r = bit_d                byte |= bit_r << bitpos                bitpos -= 1                -li bitpos < 0:                    přestávka        vrátit se byte# ----------------------------------------------------------------------------# Zde končí funkce Crypto4o# ----------------------------------------------------------------------------def hlavní():    prng = SPRNG(        int(sys.argv[3], 16),        int(sys.argv[4], 16),        int(sys.argv[5], 16),        int(sys.argv[6], 16),    )    s otevřeno(sys.argv[1], "rb") tak jako F, otevřeno(sys.argv[2], "wb") tak jako G:        zatímco Skutečný:            input_ch = F.číst(1)            -li input_ch == "":                přestávka            random_ch = prng.next_byte() & 0xFF            G.psát si(chr(ord(input_ch) ^ random_ch))-li __název__ == "__hlavní__":    hlavní()

Viz také

Reference

  1. ^ D. Coppersmith, H. Krawczyk a Y. Mansour, “Zmenšující se generátor, ”In CRYPTO ’93: Proceedings of the 13th international cryptology conference on Advances in cryptology, (New York, NY, USA), pp. 22–39, Springer-Verlag New York, Inc., 1994
  2. ^ Poorghanad, A. a kol. Generování vysoce kvalitního pseudonáhodného čísla pomocí evolučních metod IEEE, DOI: 10.1109 / CIS.2008.220.
  3. ^ Caballero-Gil, P. a kol. Nová strategie útoku pro zmenšující se generátor Journal of Research and Practice in Information Technology, Sv. 1, strany 331–335, prosinec 2008.