مساله ی لگاریتم گسسته چیست؟ و چه کاربردی در رمزنگاری دارد؟

4 90

فهرست

در این مقاله قصد داریم در مورد یکی از مسائل مهم در جبر، که در رمزنگاری کلید عمومی یا Public Key Encryption کاربردهای وسیعی دارد صحبت کنیم. مساله ی لگاریتم گسسته یا Discrete Logarithm Problem (DLP) یکی از پیش نیازها برای درک سیستم های وسیعی از رمزنگاری کلید عمومی مثل الجمال یا El-Gamal و پروتکل های تبادل کلید مثل شمای تبادل کلید دیفی-هلمن یا  Diffie-Hellman Key Exchange می باشد. بنابراین قبل از صحبت کردن در مورد سیستم های رمزنگاری کلید عمومی بهتر است با مسائل سخت مورد استفاده در آن ها آشنا شویم.

مفاهیمی در جبر

برای معرفی مساله ی لگاریتم گسسته ابتدا نیاز داریم مفاهیمی در جبر را معرفی کنیم. باید توجه شود سختی بسیاری از مسائلی که در رمزنگاری معرفی می شوند وابسته به ساختمان جبری مورد استفاده در آن ها است برای مثال فرض کنید شما یک به عنوان یک برنامه نویس، برنامه ای توسعه می دهید که کمترین توجهی به موارد امنیتی آن نکرده اید. در این صورت اگر هم آن برنامه درست کار کند، استفاده ی موثری نمی توان از آن کرد. در رمزنگاری نیز پیکربندی و انتخاب مولفه های مختلف، مخصوصا مولفه های جبری و اطلاعاتی بسیار حائز اهمیت است و برای همین بزرگان این زمینه همچون پروفسور دن بونه (Dan Boneh) قویا تاکید می کنند که توسعه ی کتابخانه ها و APIهای رمزنگاری نمی تواند بر عهده ی هر شخصی که صرفا برنامه نویس است و دانش سطحی در زمرنگاری و جبر دارد باشد. در ادامه به معرفی مفاهیمی در جبر می کنیم.

گروه یا Group در جبر

در ریاضیات و خاصا در جبر و نظریه ی گروه ها، یک گروه، یک مجموعه مثل G به همراه یک عمل دوتایی در G (در اینجا این عمل را با * نمایش می دهیم) است که دارای شرایط زیر است:

  • بسته بودن: نتیجه ی ترکیب هر دو عضو مثل a و b در G، یک عضو در G است. یا به زبان ریاضی:

    \[ \forall \alpha,\beta\inG: \alpha*\beta\in G \]

  • خاصیت انجمنی: این خاصیت بیان می کند جابجایی پرانتزها و الویت در محاسبات نباید تاثیری بر نتیجه ی نهایی داشته باشد. یا به زبان ریاضی:

    \[ \forall \alpha,\beta,\gamma\in G: \alpha*(\beta*\gamma) = (\alpha*\beta)*\gamma \]

  • وجود عضو همانی: یک عضو یکتا مثل e در G وجود دارد که عمل آن با هر عضو دیگر، همان عضو را نتیجه می دهد. یا به زبان ریاضی:

    \[ \exists! e\in G : \forall \alpha\in G: \alpha*e = \alpha , e*\alpha=\alpha \]

  • وجود عضو معکوس: برای هر عضو در G یک عضو یکتا وجود دارد که عمل آن دو باهم، عضو همانی را نتیجه می دهد. یا به زبان ریاضی:

    \[ \forall \alpha\in G \exists! \beta \in G: \alpha*\beta = e , \beta*\alpha = e \]

برای مثال مجموعه اعداد گویا با عمل ضرب یک گروه است. در شکل زیر مکعب روبیک را مشاهده می کنیم که بر اساس یک گروه خاص می باشد.

گروه جبری مکعب روبیک

گروه چرخشی (سیکلیک، دوری) یا Cyclic Group

گروه چرخشی یک گروه است که دارای مولد یا Generator باشد. به بیان دیگر بتوان کلیه ی عضوهای آن را با یک عضو تولید کرد. برای مثال کلیه (Z/pZ) با p اول، چرخشی است. مثلا Z/۳Z چرخشی است. گروه چرخشی متناهی، یک گروه چرخشی است که دارای اعضای متناهی باشد.

گروه چرخشی

مساله ی لگاریتم گسسته

اگر G یک گروه چرخشی ضربی باشد و g مولد یا Generator آن باشد، با توجه به چرخشی بودن G می توان گفت کلیه ی اعضای G را می توان برای یک یا تعدادی عدد صحیح h به صورت gنوشت. حال فرض کنید برای a عضو G داریم:

    \[ g^{h} = a \]

یافتن صحیح h که در رابطه ی بالا صدق کند معرف مساله ی لگاریتم گسسته است و به h لگاریتم گسسته ی a می گویند.

آیا لگاریتم گسسته یک مساله ی سخت است؟

در حالت عمومی خیر! سختی مساله ی لگاریتم گسسته بستگی به گروه انتخابی برای مساله دارد. برای مثال گروه معروف *Zکه p اول و این گروه یک گروه محبوب در رمزنگاری است تحت شرایطی ناامن است و مساله ی لگاریتم گسسته روی آن بسیار بهینه قابل حل است. برای مثال اگر p-1 حاصل ضرب دو عدد صحیح کوچک باشد الگوریتم پولیگ-هلمن به صورت بهینه قادر به حل آن است. برای همین موضوع است همیشه در رمزنگاری از بخواهیم از به عنوان *Zp گروه استفاده کنیم باید یک عدد اول امن را در نظر بگیریم. یک عدد امن اول می تواند به صورت ۲q+1 باشد که q یک عدد اول بزرگ است و تضمین می کند که p-1 که برابر ۲q است دارای فاکتور اول بزرگ می باشد و در نتیجه الگوریتم پولیگ-هلمن قادر به حل آن در زمان منطقی نیست.
اما حتی اگر p امن هم باشد، الگوریتمی شبه نمایی تحت عنوان Index Calculus یا محسابات شاخص وجود دارد که می تواند مساله را با پیچیدگی نزدیک به نمایی حل کند. برای همین عدد p‌ واقعا باید بزرگ باشد (حداقل ۱۰۲۴ بیت) که بتوانیم سیستم رمزنگاری امنی داشته باشیم. این آموزش را برای اثبات این موضوع مشاهده کنید.

مثال هایی از سیستم های رمزنگاری و پروتکل ها بر پایه ی لگاریتم گسسته

بسیاری از سیستم های رمزنگاری در رمزنگاری کلید عمومی بر پایه ی لگاریتم گسسته می باشند. اصلا بهتر است بگوییم شروع رمز نگاری کلید عمومی با پروژه ی دانشجویی Whitfield Diffie و Martin Hellman در دانشگاه استنفورد بر مبنای مساله ی لگاریتم گسسته بود. در ادامه تعدادی از سیستم های رمزنگاری و پروتکل هایی که بر مبنای لگاریتم گسسته هستند را معرفی می کنیم.

  • پروتکل تبادل کلید دیفی-هلمن
ویتفیلد دیفی و مارتین هلمن
  • سیستم رمزنگاری الجمال یا El-Gamal
  • سیستم امضا دیجیتال الجمال یا El-Gamal
  • RSA در مراحل ابتدایی (بطور کلی RSA مبتنی بر Factorization است)
  • امضاء دیجیتال DSA یا Digital Signature Algorithm

طاهر الجمال

سخن پایانی

در این مقاله در مورد یکی از مسائل مهم در جبر که در رمزنگاری و امنیت اطلاعات کاربرد وسیع دارد صحبت کردیم. رمزنگاری یکی از پایه های اساسی امنیت اطلاعات و امنیت شبکه است به طوری که ارزیابی امنیتی شبکه ها و حتی نرم افزارها بسگی مستقیمی با موتورهای رمزنگاری آن ها دارد. درک مساله ها و پایه های ریاضی مورد استفاده در رمزنگاری، مهم ترین قدم برای ورود به دنیای رمزنگاری است. در آینده در مورد مسائل دیگر در رمزنگاری و امنیت اطلاعات صحبت خواهیم کرد.

درباره ما

ترجنس | thregence.ir
آکادمی ترجنس | edu.thregence.ir
دوره‌های آکادمی ترجنس | courses.thregence.ir
اینستاگرام | instagram.com/thregence
تلگرام | t.me/thregence
یوتوب | https://bit.ly/30mGowo
آپارات | aparat.com/thregence

4 نظرات
  1. hanie.asadi
    hanie.asadi می گوید

    خارق العاده بود. وب سایتتون خیلی خوبه اما انتظار چنین پست فوق العاده ای دیگه نداشتم! وب سایت هایی که داخلش افرادی باشن که علم واقعی امنیت اطلاعات داشته باشن بسیار کم دیده میشه. کاملا مشخصه خودتون در زمینه ی امنیت اطلاعات یک شخص حرفه ای هستید و البته من دورادور شما رو میشناسم و یک بار هم افتخار داشتم در جلسه ی ABE شما حضور داشتم و نظرم صرفا بخاطر این مطلب نیستش. شخصی که با این سواد به این صورت پنهان فعالیت میکنن خیلی قابل احترامن و به نظرم اگر خودتونو معرفی کنید میتونید به سرعت این کارتون رو توی اوج قرار بدید. اگر امکانش هست در مورد RSA و باقی مانده چینی هم صحبت کنید.
    ممنون استاد عزیزم.

    1. C983RC0113C70R
      C983RC0113C70R می گوید

      ممنون. متاسفانه شما رو به خاطر ندارم. حتما در مورد مواردی که گفتید مطالبی خواهم نوشت.
      برای شما آروزی توفیق دارم.

  2. Samaneh_Zemni_M
    Samaneh_Zemni_M می گوید

    سلام و با تشکر از پست های ارزنده شما. “سواد یک نفر در امنیت ارتباط مستقیم و محکم با سواد اون شخص در امنیت اطلاعات و رمزنگاری داره”. این جمله ای بود که در یکی از جلسات، خودتون روش تاکید کردید و از زبان بزرگان دیگر در این زمینه و در زمینه نفوذ و APT بیان کردید. من یادداشت کردم و همیشه گوشه ی ذهنم دارم این صحبت ارزشمند رو. خدا قوت استاد. امیدوارم سلامت و پیروز و جاودانه باشید.

    1. C983RC0113C70R
      C983RC0113C70R می گوید

      سلام، از لطفی که دارید سپاسگزارم.
      برای شما آرزوی توفیق دارم.

ارسال یک پاسخ