مولد کوچککننده
در رمزنگاری، مولد کوچک کننده نوعی تولیدکننده عدد شبه تصادفی است که در رمزنگاری جریانی مورد استفاده قرارمی گیرد. این مولد برای اولین باردر کریپتو ۱۹۹۳ توسط دون کوپرزمیت، هوگو کراچزیک و ییشی منصور منتشر شدهاست.
مولد کوچک کننده از دو ثبات تغییر بازخورد خطی استفاده میکند. یکی با نام دنباله 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، رمزنگاری جریانی (ناامن) براساس اصل مولد کوچک کننده
- مولد گام متناوب، مشابه رمزنگاری جریانی.
منابع ویرایش
- ↑ Poorghanad, A. et al. Generating High Quality Pseudo Random Number Using Evolutionary methods IEEE, DOI: 10.1109/CIS.2008.220.
- ↑ Caballero-Gil, P. et al. New Attack Strategy for the Shrinking Generator Journal of Research and Practice in Information Technology, Vol. 1, pages 331–335, Dec 2008.