مولد گام متناوب

در رمزنگاری، مولد گام متناوب (ASG) یک مولد عدد شبه تصادفی رمزنگاری است که در رمزنگاری جریانی مورد استفاده قرار می‌گیرد. این طرح در سال ۱۹۸۷ توسط CG گونتر منتشر شد. همچنین به عنوان مولد توقف و حرکت متناوب شناخته می‌شود.

بررسی اجمالی

رجیسترهای تغییر بازخورد خطی (LFSR) از نظر آماری مولدهای شبه تصادفی عالی، با توزیع خوب و پیاده‌سازی ساده هستند. با این حال، از آنها نمی‌توان به تنهایی به این منظور مورد استفاده قرار گیرند زیرا خروجی آنها به راحتی قابل پیش‌بینی است.

ASG شامل سه رجیستر تغییر فیدبک خطی است که ما برای راحتی آنها را LFSR0، LFSR1 و LFSR2 می‌نامیم. خروجی یکی از این رجیسترها تصمیم می‌گیرد که از کدام دو رجیستر دیگر استفاده شود. به عنوان مثال اگر LFSR2 خروجی ۰ را تولید کند، LFSR0 کلاک می‌خورد، و اگر ۱ را خروجی دهد، به جای آن، LFSR1 کلاک می‌خورد. خروجی Xor آخرین بیت تولید شده توسط LFSR0 و LFSR1 است. وضعیت اولیه سه LFSR کلید(k)است.

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

کد مثال در C :

/* 16-bit toy ASG (much too small for practical usage); return 0 or 1. */
unsigned ASG16toy(void)
{
  static unsigned /* unsigned type with at least 16 bits */
    lfsr2  = 0x8102, /* initial state, 16 bits, must not be 0 */
    lfsr1  = 0x4210, /* initial state, 15 bits, must not be 0 */
    lfsr0  = 0x2492; /* initial state, 14 bits, must not be 0 */

  /* LFSR2 use  x^^16 + x^^14 + x^^13 + x^^11 + 1 */
  lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;

  if (lfsr2&1)
    /* LFSR1 use  x^^15 + x^^14 + 1 */
    lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;
  else
    /* LFSR0 use  x^^14 + x^^13 + x^^3 + x^^2 + 1 */
    lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;

  return (lfsr0 ^ lfsr1)&1;
}

پیاده‌سازی ASGدر سخت‌افزار بسیار ساده است. برخلاف مولد کوچک کننده و مولد خود کوچک شونده، یک بیت خروجی در هر کلاک تولید می‌شود و عملکرد و مقاومت مداوم در برابر حملات زمان‌بندی را تضمین می‌کند.

امنیت

در حملات با پیچیدگی کاهش یافته بر روی مولدگام متناوب، شهرام خزایی، سیمون فیشر و ویلی مایر یک رمزنگاری از ASG را ارائه می‌دهند که اجازه می‌دهد تا مبادلات مختلفی بین پیچیدگی زمانی و میزان خروجی مورد نیاز برای سوار کردن حمله انجام شود، به عنوان مثال با پیچیدگی مجانبی. $O(L^{2}.2^{2L/3})$ و $O(2^{2L/3})$ بیت، که$L$ اندازه کوتاهترین سه LFSR است.

منابع

• C. G. Günther مولد گام متناوب کنترل شده توسط دنبالههای de Bruijn، پیشرفت‌ها در رمزنگاری - EuroCrypt '87 (صفحات ۵–۱۴)، LNCS 304، Springer Verlag، شابک ‎۳−۵۴۰−۱۹۱۰۲-X . [۱] یا [۲].
• Schneier, Bruce. رمزنگاری کاربردی (p383-384)، چاپ دوم، John Wiley & Sons، ۱۹۹۶. شابک ‎۰−۴۷۱−۱۱۷۰۹−۹ شابک 0-471-11709-9