مولد کوچک‌کننده

در رمزنگاری، مولد کوچک کننده نوعی تولیدکننده عدد شبه تصادفی است که در رمزنگاری جریانی مورد استفاده قرارمی گیرد. این مولد برای اولین باردر کریپتو ۱۹۹۳ توسط دون کوپرزمیت، هوگو کراچزیک و ییشی منصور منتشر شده‌است.

مولد کوچک کننده از دو ثبات تغییر بازخورد خطی استفاده می‌کند. یکی با نام دنباله A، بیت‌های خروجی تولید می‌کند، و دیگری با نام دنباله S، خروجی آنها را کنترل می‌کند. هر دو A و S کلاک می‌خورند، اگر بیت S برابر ۱ باشد، بیت A خروجی است. S برابر ۱ باشد، A دور ریخته می‌شود، خروجی نخواهیم داشت، و رجیسترها دوباره کلاک می‌خورند. این کار اشکالاتی دارد که نرخ خروجی مولد به‌طور نامنظم متفاوت است و به گونه ای که به وضعیت S اشاره دارد. این مشکل را می‌توان با بافر کردن خروجی برطرف کرد. دنبالهٔ تصادفی تولید شده توسط LFSR نمی‌تواند عدم پیش‌بینی شدن سیستم ایمن را تضمین کند و روشهای مختلفی برای بهبود تصادفی بودن آن پیشنهاد شده‌است

با وجود این سادگی، در حال حاضر هیچ حملهٔ شناخته شده‌ای بهتر از Brute-force وقتی که چندجمله ای‌های بازخورد مخفی هستند وجود ندارد. اگر چندجمله‌های بازخورد شناخته شده باشند، بهترین حمله شناخته شده به خروجی باطول کمتر از A*S نیاز دارد.

یک نوع جالب مولد خود کوچک کننده است.

پیاده‌سازی در پایتون

در این مثال از دو ثبات تغییر بازخورد خطی گالیوس برای تولید جریان خروجی شبه تصادفی استفاده شده‌است. از این کد پایتون می‌توان برای رمزگذاری و رمزگشایی یک فایل یا هر نوع bytestream استفاده کرد.

#!/usr/bin/env python

import sys
# ----------------------------------------------------------------------------
# Crypto4o functions start here
# ----------------------------------------------------------------------------

class GLFSR(object):
    """Galois linear-feedback shift register."""

    def __init__(self, polynom, initial_value):
        print "Using polynom 0x%X, initial value: 0x%X." % (polynom, initial_value)

        self.polynom = polynom | 1
        self.data = initial_value
        tmp = polynom
        self.mask = 1

        while tmp != 0:
            if tmp & self.mask != 0:
                tmp ^= self.mask

            if tmp == 0:
                break

            self.mask <<= 1

    def next_state(self):
        self.data <<= 1

        retval = 0

        if self.data & self.mask != 0:
            retval = 1
            self.data ^= self.polynom

        return retval

class SPRNG(object):
    def __init__(self, polynom_d, init_value_d, polynom_c, init_value_c):
        print "GLFSR D0: ",
        self.glfsr_d = GLFSR(polynom_d, init_value_d)
        print "GLFSR C0: ",
        self.glfsr_c = GLFSR(polynom_c, init_value_c)

    def next_byte(self):
        byte = 0
        bitpos = 7

        while True:
            bit_d = self.glfsr_d.next_state()
            bit_c = self.glfsr_c.next_state()

            if bit_c != 0:
                bit_r = bit_d
                byte |= bit_r << bitpos

                bitpos -= 1

                if bitpos < 0:
                    break

        return byte

# ----------------------------------------------------------------------------
# Crypto4o functions end here
# ----------------------------------------------------------------------------

def main():
    prng = SPRNG(int(sys.argv[3], 16), int(sys.argv[4], 16),
                 int(sys.argv[5], 16), int(sys.argv[6], 16))

    with open(sys.argv[1], "rb") as f, open(sys.argv[2], "wb") as g:
        while True:
            input_ch = f.read(1)

            if input_ch == "":
                break

            random_ch = prng.next_byte() & 0xff
            g.write(chr(ord(input_ch) ^ random_ch))

if __name__ == '__main__':
    main()

جستارهای وابسته

• FISH، رمزنگاری جریانی (ناامن) براساس اصل مولد کوچک کننده
• مولد گام متناوب، مشابه رمزنگاری جریانی.