آر سی ۴

تاریخچه

RC4 یک رمز دنباله‌ای است که توسط Ron Rivest از اعضای کمپانی RSA Security در سال ۱۹۸۷طراحی شد. RC4 از نظر تجاری مدت‌ها از سوی کمپانی RSA Security پنهان نگه داشته شده بود و در نهایت این الگوریتم در سمپامبر ۱۹۹۴ لو رفت.
مهمترین فاکتورهای موفقیت RC4 در رنج وسیع کاربردهای آن، سادگی و سرعت آن می‌باشد و اینکه پیاده‌سازی آن هم در سخت‌افزار و هم در نرم‌افزار کارآمد است و همچنین توسعه آن بسیار ساده‌است.

الگوریتم زمانبندی کلید[KSA) [The Key-Scheduling Algorithm)

KSA برای مقداردهی اولیه جایگشت در آرایه S استفاده می‌شود. keylength به عنوان تعداد بایت‌های کلید تعریف می‌شود که می‌تواند بین ۱تا ۲۵۶ باشد ولی معمولاً بین ۵ و۱۶ می‌باشد و به تبع آن، طول کلید نیز معمولاً بین۴۰ و ۱۲۸ بیت خواهد بود. ابتدا آرایه S برای ایجاد جایگشت مقداردهی اولیه شده و سپس S برای ۲۵۶ تکرار در PRGA پردازش می‌شود و هم‌زمان نیز بایت‌های مربوط به کلید را تولید می‌کند.
for i from 0 to 255
    S[i]:= i
endfor
j:= ۰
for i from 0 to 255
 j:= (j + S[i] + key[i mod keylength]) mod 256
    [swap values of S[i] and S[j
endfor

الگوریتم تولید شبه تصادفی[PRGA) [The pseudo-random generation algorithm)

به خاطر تکرارهای زیاد، PRGA حالت و خروجی‌های دنباله کلید را بهبود می‌دهد. در هر بار تکرار،PRGA مقدار i را افزایش می‌دهد و سپس مقدار [S[i را با j جمع می‌کند، مقادیر [S[i و [S[j را با هم جابجا کرده و سپس مقدار S[i]+S[j] mod 256 را محاسبه کرده و به عنوان شاخصی برای واکشی S که در واقع خروجی الگوریتم می‌باشد، استفاده می‌کند. هر عنصر S با یک عنصر دیگر حداقل یک بار در هر ۲۵۶ تکرار جابجا خواهد شد.

 i:= ۰
j:= ۰
while GeneratingOutput:
 i:= (i + 1) mod 256
 j:= (j + S[i]) mod 256
 [swap values of S[i] and S[j
 [K:= S[(S[i] + S[j]) mod 256
 output K
endwhile

پیاده‌سازی

خیلی از جریان‌های رمزشده بر مبنای شیفت رجیسترهای بازخورد خطی (Linear feedback shift registers) می‌باشند، این در حالی است که پیاده‌سازی این سیستم‌ها در سخت‌افزار کارآمد هستند ولی در نرم‌افزار اینچنین نیستند. در طراحی RC4 از استفاده از LFSRها پرهیز می‌شود و بنابراین برای پیاده‌سازی نرم‌افزاری ایده‌آل است چرا که فقط نیازمند دستکاری بایت‌ها ست. RC4 از ۲۵۶ بایت حافظه برای آرایه حالت، [S[0 تا S[255]، k بایت حافظه برای کلید، [key[0 تا [key[k-1، و متغیرهای عددی i, j و y استفاده می‌کند.

بردار تست

بردارهای تست زیر رسمی نیستند ولی برای تست کردن برنامه‌های RC4 راحت مناسب و راحت می‌باشند. کلیدها و متن‌های اصلی همگی در مد اسکی هستند و دنباله کلید و متون رمز شده در مد هگزادسیمال می‌باشند

انواع RC4

همان‌طور که در بالا اشاره شد مهم‌ترین نقطه ضعف RC4از ناکارآمدی زمان کلید ناشی می‌شود به این صورت که اولین بایت خروجی کلید را آشکار می‌کند، که این امر را می‌توان با در نظرنگرفتن بخش ابتدایی جریان خروجی تصحیح کرد. این روش بهRC4-dropN معروف است که N معمولاً بر ۲۵۶ بخش پذیر است (مثل ۷۶۸ یا ۱۰۲۴). تعدای از تلاش‌های انجام شده برای تقویت RC4 عبارت اند: RC4A, VMPC و RC+.

VMPC

متغیر اصلاح ترکیب جایگشت (VMPC) یکی دیگر از انواع RC4 است. از زمان‌بندی کلید همانند RC4 استفاده می‌کنند، اما تعداد تکرارهای آن به جای ۲۵۶ بار ۷۶۸ تکرار می‌باشد.
All arithmetic is performed modulo 256
i:= ۰
while GeneratingOutput:
 a:= S[i]
 j:= S[j + a]
 b:= S[j]
 output S[S[b] + 1]
 S[i]:= b
 S[j]:= a
 i:= i + 1
endwhile

RC4+

RC4+ نسخه اصلاح شده از RC4 است با یک پیچدگی بیشتر در زمانبندی کلید سه-مرحله‌ای و همچنین تابع خروجی پیچیدگی بیشتری دارد به این صورت که چهار جستجوی بیشتر در آرایه S برای هر بایت خروجی انجام می‌دهد.
All arithmetic is performed modulo 256while GeneratingOutput:
 i:= i + 1
 a:= S[i]
 j:= j + a
 b:= S[j]
 S[i]:= b
 S[j]:= a
 c:= S[i<<5 ⊕ j>>3] + S[<5 ⊕ i>>۳]
 output (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]
endwhile
این الگوریتم هنوز به صورت قابل توجهی موشکافی نشده‌است.