توابع شبه‌تصادفی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علم رمزنگاری، یک خانواده از توابع شبه‌تصادفی (به انگلیسی: Pseudorandom function family) که مختصرا با PRF نمایش می‌دهیم، مجموعه‌ای از توابع محاسبه پذیر کارا است، به طوری که هیچ الگوریتم کارایی (که به صورت اراکلی به توابع دسترسی دارد) نتواند با مزیت قابل توجهی، یک تابع ازاین خانواده را، از یک تابع تصادفی دلخواه تمایز دهد.

توابع شبه‌تصادفی نباید با مولدهای شبه‌تصادفی اشتباه گرفته شوند. یک مولد شبه‌تصادفی تابعی است که اگر ورودی آن تصادفی باشد، انتظار
داریم خروجی اش تصادفی به نظر برسد؛ اما توابع شبه‌تصادفی خانواده‌ای از توابع است که اگر یک تابع از این خانواده انتخاب کنیم، باید یک
تابع تصادفی به نظر برسد؛ یعنی تشخیص اینکه این تابع از همین خانواده انتخاب شده است، برای یک شخص ثالث سخت باشد.

کاربردها[ویرایش]

توابع شبه‌تصادفی ابزارهای اساسی در ساختن اولیه‌های (primitive) رمزنگاری هستند.

توابع شبه‌تصادفی ابزاری سودمند برای رسیدن به امنیت متن اصلی انتخابی اند و می‌توان از آنها در احراز هویت و اصالت سنجی پیام استفاده نمود.

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

از توابع شبه‌تصادفی می‌توان در ساختن مولدهای شبه تصادفی استفاده کرد؛ البته عکس این کار نیز امکان‌پذیر است.

استفاده از توابع شبه تصادفی در شبکه فایستل دو دوری

یک کاربرد دیگر توابع شبه‌تصادفی، تولید جایگشت‌های شبه تصادفی است، که نمونه بارز آن شبکه فایستل است. ثابت شده است که اگر تعداد دورهای شبکه فایستل بیشتر از ۲ باشد و توابع استفاده شده شبه تصادفی باشند، شبکه فایستل یک جایگشت شبه تصادفی است.

منابع[ویرایش]

  • مشارکت‌کنندگان ویکی‌پدیا، «Pseudorandom function family»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۱ مه ۲۰۱۴).
  • کتاب Introduction to modren cryptography/katz and lindell