دعوت به رمزگذاری
مشکلات
در ادبیات مدرن رمزنگاری - برای نشان دادن مشکلات و روشهای اساسی - دو شخصیت ساختگی به نامهای آلیس و باب معرفی شدهاند که اکنون بهطور سنتی به قهرمانهای کنش تبدیل شدهاند. منشأ آنها به وضوح به دلیل شخصیت سازی حروف A و B است که در زبان رسمی محققان استفاده می شود. این واقعیت که دو نماد به شخصیتهایی تبدیل شدهاند که اکنون متون چهرهای به آنها اختصاص میدهند - و با مقداری بیشرمانه، حتی یک شخصیت، هرچند جنینی، شاید فراتر از بازی، به این معنی باشد که این ماده خود را به یک کاربرد فوری وامی دارد. و زمینهای را میطلبد که در آن مدعیان یا گهگاهی متحدان یک مسابقه را بتوان مستقیماً و نه به طور انتزاعی شناخت.
به عنوان مثال: آلیس و باب یک بحث دارند و تمام دارایی های مشترک را تقسیم می کنند. برای برخی از اشیا انتخاب آسان است، در حالی که برای برخی دیگر یک قرعه کشی لازم است تا تصمیم بگیرد که آن را به چه کسی اختصاص دهد. اما این دو قصد ملاقات ندارند (یا اکنون کیلومترها از هم فاصله دارند) و می خواهند قرعه کشی را از طریق تلفن انجام دهند. کدام یک از این دو به اندازه کافی سخاوتمند - و قابل اعتماد - خواهد بود که به دیگری اجازه دهد سکه کلاسیک را برگرداند و نتیجه قرعه کشی را به او بگوید؟
وضعیت حساس است، خطر برافروختن مجدد اختلافات و بدتر شدن روابط را در پی دارد، اما... نگران نباشید: هر دو می توانند روی روشی توافق کنند که احتمال پنجاه درصدی (یعنی یک تساوی منصفانه) را برای هر یک از آنها تضمین کند، بدون نیاز به اعتماد به دیگری، فقط داشتن حداقل دانش از پیچیدگی محاسباتی برخی از عملیات های حسابی روی اعداد صحیح. آلیس و باب خوشبختانه روی این موضوع آماده شده اند و مشکل حل شده است.
مشکل دیگر در عوض این است که آلیس و باب مشتاق تبادل پیام هستند - مهم نیست چه ماهیتی دارد، حتی اگر همه موافق باشند که آنها مهربان هستند. اما سرنوشت آنها، افسوس، در این مورد نیز این است که در فاصله زیادی قرار داشته باشند و به همین دلیل می خواهند روی کلیدی به توافق برسند که محتوای واقعی پیام ها را رمزگذاری کند : فرض کنید چارلی، خواستگاری که آلیس آن را رد کرده است. ، در غیر این صورت می توانند از آن برای ایجاد مشکل در روابط خود استفاده کنند. در اینجا نیز جای نگرانی نیست: باب در یک دوره رمزنگاری کلید عمومی شرکت کرده است و به طور واضح به آلیس توضیح می دهد که چگونه می توانند ادامه دهند. چارلی پیام را قطع می کند و متوجه می شود که نمی تواند برنامه پارازیت خود را اجرا کند. او نیز همین دوره را در زمینه رمزنگاری دنبال کرده است و برای او واضح است که حتی اگر ارتباطات آنها را رهگیری کند، نمی تواند کلید رمزگذاری را که آلیس و باب قصد دارند برای تبادل پیام به توافق برسند، یاد بگیرد.
قبل از اینکه یک رشته علمی باشد، رمزنگاری یک عمل، مجموعه ای از قوانین، روش ها و ابزارها بود. تقریباً به یک هنر تبدیل شده بود: هنر تبادل پیام بدون درک محتوای واقعی، حتی اگر رهگیری شود. رشته ای با جایگاهی مبهم، مرزی با جادو و باطنی. در این زمینه، آلیس و باب هنوز متولد نشده اند. ما با مشکلات جاسوسی سر و کار داریم، دشمنانی که مشتاقند اطلاعاتی را که با متحدانمان رد و بدل می کنیم به دست آورند تا از آن به ضرر خود استفاده کنند.
واضح است که منشأ باستانی است و نه تنها به نیازهای تجاری، بلکه بیش از هر چیز دیپلماتیک و نظامی مرتبط است. مشخص است که در بسیاری از موارد سرنوشت درگیری ها با این توانایی برای شناخت از قبل حرکات حریف تعیین شده است. سپس ظهور شبکه های ارتباطی دیجیتال که به طور منظم در زندگی روزمره مورد استفاده قرار می گیرد، نیازهای جدیدی را برای امنیت و حفاظت از حریم خصوصی می طلبد . و ریاضیات - به ویژه نظریه اعداد - ماهیت رمزنگاری را تغییر داد، آن را از هاله رمز و راز آن رها کرد و آن را از یک هنر به یک علم تبدیل کرد.
اما دو مشکل قبلی مربوط به آلیس و باب چه وجه اشتراکی با این موضوع قدیمی دارند: قرعهکشی که از طریق تلفن انجام میشود یا تعویض یک کلید رمزگذاری زیر بینی شخصی که آن را رهگیری میکند، اما کسی که هرگز قادر به انجام آن نیست. از آن استفاده کنم؟ واقعیت این است که وقتی ریاضیات با رسمی شدن آن در بخشی درگیر می شود، یک سری مسائل ظاهراً متفاوت و غیر مرتبط را نیز آشکار می کند که در عوض یک وحدت تعریف شده و اغلب عمیق را نشان می دهد.
و این همان چیزی است که اخیراً اتفاق افتاده است: مشکل فقط در (1) رمزگذاری یا رمزگشایی یک پیام نیست ، بلکه در "تأیید کردن" آن است، یعنی: (2) شناسایی فرستنده پیام و (3) درک آیا پیام دست نخورده است یا در حین انتقال دستکاری شده است . اما همچنین: (4) توافق با کسی در مورد یک قطعه داده که مخفی نگه داشته شود ، حتی اگر از یک کانال انتقال ناامن استفاده کنید. (5) به طور تصادفی تصمیم بگیرید، با شانس موفقیت برابر در مقایسه با یک همکار غیرقابل اعتماد . (6) بدون اینکه منبع یا راز آن را فاش کنید، آگاه سازید که علم خاصی دارید .
اولین مشکل ذکر شده، امنیت انتقال است که فیلم های جنگی و جاسوسی متعددی ما را به آن عادت کرده اند. دوم این است که از صحت فرستنده ; در این مورد، علاوه بر بازی دوگانه جاسوسی، لازم است مشکلات مدرن تراکنش های اقتصادی از راه دور را به خاطر بسپاریم: دستگاه خودپرداز یا به اصطلاح امضای دیجیتال که به ما امکان می دهد حتی از طریق ایمیل نیز شناسایی شویم. سومین مشکل ذکر شده مربوط به یکپارچگی پیام است . این تله ای است که پیشینه های معروفی دارد: رومئو به مانتوا پناه می برد و از پرستار مورد اعتماد خود (به اصطلاح!) خبر دروغ مرگ ژولیت را دریافت می کند. مشکلات (4) قرعه کشی از راه دور و (5) تعویض کلید مواردی هستند که قبلاً آلیس و باب را در حال کار در آنها دیده ایم و راه حل آنها بعداً آشکار خواهد شد. آخرین مشکل لیست شده به اصطلاح به دانش صفر می پردازد: چگونه می توانیم تضمین کنیم که اطلاعاتی داریم بدون اینکه جنبه های اساسی آن آشکار شود؟ به عنوان مثال، چگونه نیکولو فونتانا، تارتالیای معروف، در قرن شانزدهم اعلام کرد که فرمول حل رادیکال های معادلات درجه سوم را بدون اینکه مجبور باشد آن را برای جامعه ریاضی آشکار کند (حداقل تا زمانی که موفق به انجام این کار شود) کشف کرده است. )؟ در این مورد، مشکل دشوار نیست: فقط باید نشان دهید که می دانید چگونه ریشه برخی از معادلات پیشنهاد شده توسط دیگران را محاسبه کنید. هر کسی به راحتی می تواند درستی پاسخ را تأیید کند و پس از چند اجرا از این دست خود را متقاعد کند که هرکسی که ریشه معادلات را پیدا کرده است، لزوماً باید یک روش مطمئن داشته باشد، یک فرمول دقیقاً: تأیید اینکه آیا یک عدد معین یک ریشه است یا خیر، یک عملیات است. بسیار ساده تر از یافتن آن، حداقل برای کسانی که فرمول آن را نمی دانند. اما در عوض به این فکر کنید که اختراعی ساخته اید که برای ثبت اختراع آن درخواست بودجه می کنید: یک نگاه به پروژه برای درک ایده کافی است و می فهمید که ایده همه چیز است. در همان زمان، شما می خواهید وام دهنده شما مطمئن باشد که مکانیسم کار می کند. اعتماد کنیم یا نه؟ کدام مسیر را دنبال کنیم؟
واضح است که در این مسیر مشکلات چند برابر می شود. برای اکثر آنها، عمل راه حل های تجربی، خاص و متفاوت از مورد به مورد پیدا کرده است. ریاضیات سعی می کند همه این مسائل را به عنوان موارد خاصی از یک مسئله واحد و اساسی ببیند.
انسانها ابتدا کلماتی را خلق کردند تا یکدیگر را درک کنند و سپس - شاید توبه کنند - رمزنگاری را اختراع کردند تا فقط برای برخی خود را بفهمند. اما در این راه، علاوه بر جلب کنجکاوی غالباً علاقه مند طردشدگان، مجبور بودند به دنیایی از اسرار پناه ببرند تا با چند نفر در میان بگذارند. نسخه جدید و مدرن رمزنگاری، چیزی که رمزنگاری کلید عمومی نامیده میشود ، به نظر میرسد از میل جهانی ریاضیدانان به رفتار یکسان با همه، کنجکاو و با اعتماد به نفس، و حذف حتی کوچکترین اشتراکگذاری راز از ارتباطات خصوصی ما، زاده شده است. با چه موفقیتی خواهیم دید.
با این حال، قبل از پرداختن به ایدهها و روشهای اساسی، خوب است که یک مشاهده اصلی داشته باشیم: در مسئله کلاسیک انتقال پیام ، از آلیس تا باب، با تلاش شخصی مانند چارلی برای رمزگشایی محتوای واقعی - مشکلی که به آن کمک میکند. خود را برای گنجاندن همه چیزهای دیگر که تبدیل به جنبه ها یا تخصص های خاصی می شوند در خود گنجانده است - معمولاً رفتار مشروع به کسانی که سعی در برقراری ارتباط دارند اختصاص می دهد، در حالی که استراق سمع به مثابه فردی که بی جهت به "کسب و کار خود" نمی پردازد، با دیدی منفی تلقی می شود. ". هیچ چیز در مورد این فعالیت نمی تواند دور از واقعیت باشد: برای مثال، مشخص است که یکی از معروف ترین موارد استفاده از تکنیک های رمزنگاری در طول جنگ جهانی دوم رخ داد، زمانی که سرویس مخفی انگلیس با کمک ضروری آلن تورینگ ( 1912-1954)، در اوایل سال 1942 موفق به رمزگشایی ماشین رمز انیگما شد که توسط فرماندهی آلمانی استفاده می شد. و این واقعیت برای سرنوشت جنگ تعیین کننده بود (حتی اگر ماشین دیگری به نام T-52 در تمام طول جنگ فعال بماند).
با این روحیه عینی است که رمزنگاران و حتی بیشتر از آن ریاضیدانان خود را به در نظر گرفتن روش های خود وامی دارند: تاریخ رمزنگاری مملو از حرکات و حرکات متقابل است، نوعی رقابت بین کسانی که همیشه روش های رمزگذاری جدید را ابداع می کنند و کسانی که بی وقفه روش های رمزگذاری را پیدا می کنند. روشی برای رمزگشایی سیستم جدید نیز.
کسانی که رمزگذاری می کنند و کسانی که رمزگشایی می کنند باید در یک سطح در نظر گرفته شوند. اینها دو روش متفاوت از یک پدیده هستند، مانند دو بخش که اندازه گیری آنها علائم متفاوتی دارد، فقط به این دلیل که جهت مثبت خط مستقیم در یک جهت انتخاب شده است تا جهت دیگر. ملاحظات اخلاقی رفتار به زمینه دیگری تعلق دارد.
اطلاعات مختصر و جذاب در مورد رویدادهای تاریخی و ایده های مدرن فعالیت رمزنگاری از نقطه نظر فنی در Sgarro [1] و Berardi, Beutelspacher [2] موجود است. درمان گستردهتر، اما همچنان به شیوهای قانعکننده روایت میشود، برخورد سینگ [3] است. هرکسی که بخواهد مشکل را از نقطه نظر تأثیر آن بر توسعه سیستم های ارتباطی دیجیتال - و در نتیجه عمدتاً با توجه به مشکلات اجتماعی و حقوقی - طرح ریزی کند، می تواند با Giustozzi، Monti و Zimuel [4] مشورت کند.
کلید رمزگذاری
اگرچه ممکن است متناقض به نظر برسد، همه موافق هستند که برای تجهیز خود به روشی برای انتقال پیام های محرمانه در طول یک کانال قابل رهگیری، لازم است قبلاً یک کانال امن در دسترس باشد که از طریق آن A و B بتوانند کلیدی را مبادله کنند. یکی برای رمزگذاری پیام ها و دیگری برای رمزگشایی خدمت می کند.
واقعیت این است که این کانال امن نمی تواند برای انتقال عادی استفاده شود، اما شاید در شرایط استثنایی ایجاد شود که تکرار آن دشوار است. به عنوان مثال، در استعاره جاسوسی که به خوبی برای این موقعیت ها مناسب است، A و B با یکدیگر ملاقات می کنند و مستقیماً در مورد کلیدی که بعداً استفاده خواهند کرد توافق می کنند. بسه کانال امنی که با نزدیکی آنها و امکان برقراری ارتباط صوتی ارائه می شود هرگز تکرار نخواهد شد، اما کلید تضمین محرمانه بودن ارتباطات آینده آنها در امتداد کانال دیگری و معمول تر است که - آنها به خوبی می دانند - به طور سیستماتیک توسط رقیب C رهگیری می شود. .
نقش اساسی کلید رمزگذاری حتی در دوره ای مدون شد که در آن فعالیت رمزنگاری که همیشه در زمینه نظامی به طور گسترده مورد استفاده قرار می گرفت به نوعی حداکثر استفاده رسید. فیلولوژیست هلندی ژان گیوم کرکخوف (1835-1903)، در کار خود La cryptographie militaire در سال 1883، مشاهده می کند که امنیت یک سیستم رمزنگاری تنها به محرمانه بودن کلید بستگی دارد.
به عبارت دیگر، بدون بحث پذیرفته می شود که یک رهگیر احتمالی از پیام های رمزگذاری شده و همچنین از سیستم رمزگذاری استفاده شده آگاه می شود: چیزی که او نباید بداند کلید است. امنیت انتقال به محرمانه بودن آن بستگی دارد و بالعکس: رهگیر فقط باید کلید را بداند تا بتواند همه پیام ها را رمزگشایی کند.
پس مشکل از دید کسانی که می خواهند پیام های محرمانه رد و بدل کنند چیست؟ واضح است که قبل از هر چیز کلید سیستم رمزنگاری باید برای چند نفر شناخته شود، کسانی که ارسال می کنند و کسانی که دریافت می کنند و احتمالاً هیچ کس دیگری، زیرا - همانطور که می دانیم - رهگیرها ظلم های کمی دارند. و سپس لازمه سادگی را با هم ترکیب کنید - بتوانید آن را به خاطر بسپارید بدون اینکه اسنادی را در اطراف آن بنویسید که امکان یافتن آن وجود دارد و برای سهولت استفاده - همراه با نوعی پیچیدگی که اجازه نمی دهد به راحتی آن را ردیابی کنید. با بررسی تعداد معینی از پیام های رمزگذاری شده. بیایید بگوییم که مشکلات کلید رمزنگاری به اشتراک گذاری آن بین چندین موضوع و رابطه متعادل بین سادگی و پیچیدگی استفاده است.
کمی تاریخچه
به گفته سوتونیوس ویتا سزاروم ، یکی از قدیمیترین سیستمهای رمزی به ژولیوس سزار برمیگردد و در جنگ او علیه گولها مورد استفاده قرار میگرفت. مشخص است که قبلاً از سیستمهای دیگر، اغلب بسیار اصلی نیز استفاده شده بود، اما این یکی از Cesare شاید اولین موردی باشد که گاه به گاه نیست: یک روش، یک سیستم را پیشنهاد میکند، با کلیدهای مختلف قابل تکرار است.
این ایده در حقیقت آنقدر ساده است که زیرکی گول ها را ارج نمی نهد، اما ما آن را برای راحتی توضیح فرض می کنیم: پس از مرتب کردن حروف به ترتیب الفبایی کلاسیک، دایره ای در نظر گرفته شده - بنابراین، با حرف a به دنبال z - هر حرف به همان میزان به سمت راست منتقل می شود. بنابراین، اگر ترجمه از دو حرف باشد، a تبدیل به c، b تبدیل به d ... و به همین ترتیب، تا زمانی که z تبدیل به b شود مانند طرح زیر که در آن هر حرف متن ساده بالای حرف رمزگذاری شده مربوطه قرار میگیرد :
abcdefghilmnopqrstuvz
cdefghilmnopqrstuvzab
سپس تمام حروف موجود در پیام به طور منظم به حروف رمز مربوطه تغییر می کنند. این رمز سزار (یا ترجمه) است و اطلاعات اساسی کلید در این مورد فقط با کمیتی که ارزش ترجمه را مشخص می کند داده می شود: آشکارا در مجموع 21 کلید رمزگذاری مجزا وجود دارد - یکی از آنها بی اهمیت است. هویت
معیار سادگی مطمئناً برآورده می شود. شاید خیلی زیاد. و فکر کردن به حرکت از یک ترجمه به یک قرابت، برای افزایش کمی تعداد رمزها بدون اینکه سیستم را غیر عملی کند، دشوار نیست. این بدان معنی است که به جای فرمولی مانند:
n'=n+k
جایی که n نشان دهنده موقعیت حرفی است که باید رمزگذاری شود، n' موقعیت حرف رمزگذاری شده مربوطه (n, n' =1, 2, ... , 21) و k کلید است، یک عبارت از نوع خواهد بود. استفاده می شود:
n'=an+b
در این مورد ، کلید توسط جفت اعداد صحیح مرتب شده (a, b) داده می شود که هر دو از 21 تجاوز نمی کنند . لازم است که اجازه دهید GCD(a,21)=1 باشد ، یعنی عدد صحیح a هیچ مقسوم علیه مشترکی با 21 نداشته باشد (همانطور که می گویند: a و 21 باید برای یکدیگر اول باشند ). محاسبه (تمرین!) تعداد رمزهای مشابه که متمایز هستند آسان است: 252 است که یکی از آنها هنوز هویت است.
تعداد رمزها بیشتر از قبل است، اما هنوز خیلی کم است که نمیتوان با حمله رمزگشاهای ماهر روبرو شد. یک استراتژی می تواند این باشد که به جای استفاده از یک فرمول ساده مانند ترجمه یا قرابت، هر گونه جایگشتی را برای تعیین حروف رمزگذاری شده فرض کنیم. 21 جایگشت احتمالی وجود دارد! و این عددی است که دارای 20 رقم اعشاری است و هر رمزی را از خطر شکسته شدن در اثر تلاش محافظت می کند. اما خوب نیست. زیرا هر کسی که ارسال میکند و دریافت میکند باید جایگشت حروفی را که انتخاب کردهاند، به زیان پنهان کاری، در جایی ثبت کند: کلید رمزنگاری با اطلاعاتی که به خاطر سپردن و استفاده ساده باشد داده نمیشود، بلکه خود کل جایگشت است.
بنابراین مشکلی که پیش میآید این است: چگونه با استفاده از یک مکانیسم ساده برای به خاطر سپردن، یک جایگشت از حروف الفبا ایجاد کنیم؟ در عمل این مشکل باعث ایجاد ایده کلمات کلیدی شده است . در این مرحله، از زمان سزار، ما قبلاً به رنسانس رسیدهایم، زمانی که تکنیکهای رمزنگاری - مرتبط با رشد تجارت و تماسهای دیپلماتیک بین دولتها - از یک دوره تاریک احیا شدند.
پس از برداشتن یک کلمه بدون تکرار، حروف آن به عنوان اولین جایگشت مورد استفاده قرار می گیرد و از یک مکان خاص شروع می شود. حروف دیگر رمز در ادامه فهرست شدهاند و از حروفی که قبلاً استفاده شدهاند صرفنظر میکنند. به عنوان مثال، با استفاده از کلمه کلیدی hello که از حرف d شروع می شود، یعنی از جایگاه چهارم، جایگشت زیر به دست می آید:
abcdefghilmnopqrstuvz
tuzsalvebcdfghimnopqr
در این مورد، کلید رمزنگاری به جفت کاهش می یابد (سلام، 4). اما داستان به اینجا ختم نمی شود: یک رمزگشا با دانش خوبی از آمار، برخی جداول و تعداد کافی پیام رمزگذاری شده که A و B رد و بدل کرده اند، می تواند به سرعت کلید را ردیابی کند. طبیعتاً، او میداند که حروف مختلف الفبا با چه فراوانی در متون همسانی که میخواهد رمزگشایی کند - چه حروف عاشقانه یا پیامهای نظامی - ظاهر میشوند و به زودی، برای مثال، حروف صدادار و صامتهای خاص را بیشتر تشخیص خواهد داد. از حروف دیگر استفاده می شود. همه با ابهام زیاد، اما فقط برای لحظه. او آزمایشها، حدسها، تلاشهای کم و بیش انگیزهای را انجام میدهد تا زمانی که کلمهای با معنای کامل پیدا کند یا دورهای را که رمزگذاری انجام میشود تشخیص دهد: اساساً طول کلمه کلیدی.
در این مرحله انجام شده است. از اینجا یک گام کوتاه برای شکستن کل رمز است.
چگونه می توان فرکانس های آماری را لغو کرد و از تکرارهای دوره ای اجتناب کرد؟ به راحتی می توان تشخیص داد که تجزیه و تحلیل فرکانس با این واقعیت امکان پذیر است که رمز جایگزین تک الفبایی است ، یعنی هر حرف همیشه با همان حرف در طول انتقال کل پیام رمزگذاری می شود. این اشکال را می توان با جابجایی به رمزهای جایگزین چند الفبایی حل کرد ، برای مثال با استفاده از صد علامت مختلف، از هر ماهیت، برای رمزگذاری 21 حرف متن ساده. برای مثال، اگر بدانیم که در پیامهایی که به آن علاقه داریم، حرف a به طور متوسط ده بار از صد مورد اتفاق میافتد، کافی است از ده علامت مختلف برای رمزگذاری آن استفاده کنیم. نگران نباشید: لازم نیست بین متن ساده و الفبای رمزگذاری شده تناظر یک به یک وجود داشته باشد، بلکه فقط باید یکسان باشد: عبور از متن رمزگذاری شده به متن ساده. به این ترتیب، حرف a یک بار به یک صورت و یک بار به روش دیگر به ده روش مختلف رمزگذاری می شود و بسامد آن عملاً لغو می شود: اما هرکس پیام را دریافت کند و سیستم رمزگذاری را بشناسد، در هر صورت قادر است تا ده مورد را تشخیص دهد. نمادهای مختلف باید به عنوان a تفسیر شوند.

رمز دیسک
با این حال، واضح است که مشکل فقط تا حدی حل شده است زیرا در تناوب مداوم بین جستجوی سادگی سیستم و امنیت آن، این روش فرستنده و گیرنده را ملزم می کند تا خود را به یک جدول چشمگیر برای مشورت با هر یک مجهز کنند. زمان و این واقعیت ضمن ارائه اطلاعات مفید در برخی موارد، با نیاز به محرمانه بودن کلید منافات دارد.
با این حال، گام بعدی که در قرن پانزدهم توسط برخی از محققان رنسانس شناسایی شد و به صراحت توسط هنرمند و ریاضیدان بزرگ لئون باتیستا آلبرتی (1406-1472) پیشنهاد شد، تعیین کننده است: او در اثر خود Modus scribendi in ziferas در سال 1466، چند الفبایی را معرفی می کند. جایگزینی که انجام آن آسان است و چرخههایی را که در رمزگذاری رخ میدهد و بنابراین درک دورههای رمز را بسیار دشوارتر میکند. این ایده تا دوران مدرن به طور قابل ملاحظه ای بدون تغییر باقی خواهد ماند.
برای این منظور باید خود را به رمز پویا مجهز کرد : هر حرف از متن ساده بسته به موقعیت آن در خود متن، هر از گاهی به طور متفاوت رمزگذاری می شود. آلبرتی، به عنوان سازنده ماهری که بود، مکانیزم عملی را نیز ابداع کرده بود، مجهز به دو نسخه الفبا بر روی دو دیسک که میتوانستند نسبت به یکدیگر بچرخند و بنابراین از طرق مختلف با یکدیگر مکاتبه کنند. : پس از رمزگذاری یک حرف از پیام، یک چرخش ساده از یک یا چند بریدگی به شما امکان می دهد مکاتبات را برای حرف بعدی که باید رمزگذاری شود تغییر دهید. برای استفاده از آن توسط شخص دریافت کننده پیام، دانستن نقطه تطابق اولیه دیسک ها و تعداد بریدگی هایی که باید بعد از هر عملیات رمزگذاری بچرخند، کافی است. این کلید سیستم رمزگذاری ایجاد شده توسط لئون باتیستا آلبرتی است. این ایده مربوط به تناظر پویا بین حروف الفبا که در طول پیام متغیر بود، توسط دیپلمات فرانسوی بلز دو ویژنر (1523-1596) در قرن بعد محقق شد و مورد استفاده قرار گرفت و در اثر او Traité des chiffres ou گسترده شد. secrètes maniéres d'escrire of 1586: رمزهای به دست آمده، که عملاً تا دهه 1900 فعال بودند، همگی نام او را گرفتند: رمزهای ویژنر.
در این رمزها، تناظر پویا با استفاده از یک کلمه متعارف ترکیب می شود تا به عنوان کلیدی استفاده شود که دیگر نیازی به انتخاب بدون تکرار ندارد، که به نظر می رسد اولین رسمی سازی آن در رساله De furtivis literarum notos، vulgo وجود دارد. de ziferis ، نوشته شده در سال 1563 توسط دانشمند و فیلسوف Giovan Battista della Porta.
ایده این است که از حروف کلمه کلیدی استفاده شود که تا زمانی که لازم است در متن ساده به طور مداوم تکرار شود تا رمزی (از نوع سزار ) مورد استفاده در آن لحظه را نشان دهد. در اصل، حرفی که باید رمزگذاری شود و حرف متناظر کلمه کلیدی بهعنوان نوعی مختصات مسطح استفاده میشود که با آن حرف رمزگذاری شده را در چارچوبی شناسایی میکنیم - یک تابلو ، همانطور که امروز در ریاضیات میگوییم - که شامل تمام سزار ممکن است. رمزها
به عنوان مثال، کلمه hello را دوباره به عنوان کلید انتخاب کنید و فرض کنید می خواهید پیام را منتقل کنید:
ریاضیات بخون و همیشه خوشحال خواهی بود.
عملیات به شرح زیر است:
1. هر حرف از پیام ساده مطابق با یک حرف کلید قرار می گیرد که در صورت لزوم مطابق با حروف آن تکرار می شود:
ریاضی بخون
سلام سلام
سلام علیکم همیشه
شاد سلام سلام سلام سلام سلام
2. حرف کلید نشان می دهد که از کدام رمز برای حرف متن ساده مربوطه استفاده شود، با مراجعه به جدول زیر، که شامل تمام رمزهای سزار به شیوه ای منظم است :

3. برای رمزگذاری پیام، از حروف کلمه کلیدی برای شناسایی رمز استفاده می شود: بنابراین، برای حرف اول s ، خطی که با s همان hello شروع می شود استفاده می شود و n مشخص می شود . برای حرف t ساده بعدی، رمز رمزی است که با a در hello شروع می شود و بنابراین حتی پس از رمزگذاری t باقی می ماند. اکنون از l کلمه کلیدی برای رمزگذاری u و تبدیل آن به g و غیره استفاده می کنیم . پیام رمزگذاری شده شکل می گیرد...

تو ادامه بده برای درک بهتر استفاده از رمز پویا، مشاهده کنید که چگونه از این قطعه کوچک به نظر می رسد که حرف e بار اول با p و دفعه بعد با c رمزگذاری شده است . برعکس، حرف f مخفف m و t به دلیل این واقعیت است که این حروف موقعیتهای مختلفی را در پیام متنی معمولی اشغال میکنند.
بدیهی است که با تغییر کلمه کلیدی، تعداد نامحدودی از رمزها از این طریق به دست می آید. و اگر کلید به اندازه کافی طولانی باشد - و محدودیتی که در آن حروف تکراری وجود ندارد دیگر مورد نیاز نیست - دوره سیستم رمزگذاری به نسبت طولانی است. با این حال، ما نباید روش های آمار و یا توانایی و سرسختی رمزگشاها را دست کم بگیریم: برای دانستن تعداد کافی از پیام های رمزگذاری شده، در طول زمان روش هایی برای یافتن دوره سیستم رمزگذاری و از اینجا به صورت تجربی ایجاد شده است. راه، کلید را ردیابی کنید.
این نتایج، ناگفته نماند که در زمینه نظامی به دست آمده است. معماران اصلی افسر پروس فریدریش ویلهلم کاسیکی (1805-1881) و بعدها ژنرال آمریکایی ویلیام فردریک فریدمن (1891-1969) بودند. ایده اتخاذ شده توسط کاسیسکی مبتنی بر تجزیه و تحلیل تکرار گروههایی از حروف است که در رابطه مستقیم با طول کلمه کلیدی قرار میگیرند: این امکان را فراهم میکند که رمز به اجزای تک الفبایی خود تقسیم شود، که رمزگشایی آنها سادهتر است. کار فریدمن در عوض بر این احتمال تمرکز دارد که هر دو حرف در یک متن رمزی در واقع با یک حرف متن ساده مطابقت دارند. شرح مختصری از این روش ها، بدون پیچیدگی های فنی بیش از حد، را می توان در متن چابک Berardi و Beutelspacher [2] یافت. بنابراین ما به سپیده دم دهه 1900 رسیدیم، زمانی که دستگاه های الکترومکانیکی برای پردازش مقادیر روزافزون داده هایی که به عملیات رمزگشایی متصل بودند و در نتیجه برای عملیات دوگانه تنظیم دقیق سیستم رمزگذاری آماده بودند. .
ماشین های رمزگذاری
دوره ابزارهای رمزگذاری و رمزگشایی ابتدا سیستم های مکانیکی و سپس الکتریکی و الکترونیکی را به عنوان پیامد تکامل خود مفهوم ارتباطات دید. مقاله شانون در سال 1949 [5] نشانه ورود قطعی رمزنگاری به حوزه نظریه اطلاعات است. عصر رمزگذاری خودکار است . ما قبلاً به ماشین رمز انیگما
اشاره کردهایم ، مجموعهای که قبلاً در دهه 1920 برای اهداف تجاری طراحی شده بود و سپس به عنوان استانداردی برای ارتباطات محرمانه توسط فرماندهی آلمان در طول جنگ جهانی دوم اقتباس شد. این دستگاه از تعداد معینی دیسک دوار (سه عدد در پیچیده ترین نسخه ها) تشکیل شده بود که هر کدام از آنها الفبا را با استفاده از مدارهای الکتریکی پیچیده رمزگذاری می کردند. علاوه بر این، برای پیچیدگی بیشتر، این روتورها با توجه به کلیدی که به صورت رمزگذاری شده نیز ارسال می شد، روز به روز به روشی متفاوت به یکدیگر متصل می شدند. پس از هر حرف ارسال شده، آنها تحت یک چرخش قرار گرفتند.
مجموعه ای از روش ها برای رمزگشایی مفید بودند، از جمله روش هایی که از طریق به دست آوردن اطلاعات از طریق جاسوسی سنتی و همچنین آمار، مطالعه ساختارهای جبری و ترکیبی، بررسی عادات فرستنده های آلمانی و عبارات عامیانه، تجزیه و تحلیل مقادیر زیادی از داده ها با استفاده از دیگر ماشینهای الکترومکانیکی مخصوص ساخته شده ( بمبهای معروف ، بهاصطلاح تیک تاک کلاسیکشان). برای سهولت بیشتر در کار و صرفه جویی آشکار در ابزار، انیگما از یک بازتابنده استفاده کرد که به لطف آن از کلیدهای یکسان و عملیات های مشابه هم برای رمزگذاری و هم برای رمزگشایی استفاده می شد: متن ساده روی صفحه کلید تایپ می شود و دستگاه به طور مناسب مرتب می شود. با توجه به کلید، متن کدگذاری شده روی صفحه نمایش خوانده می شود. برعکس، اگر متن کد شده را تایپ کنید، متن ساده را مستقیماً می خوانید. سیستم رمزنگاری برگشت پذیر است و این ویژگی ساختاری عناصر اساسی را برای رمزگشایی فراهم می کند.
داستان جذاب این ماشین، اصول ساخت آن و اینکه چگونه گروهی از ریاضیدانان، فیلسوفان و معمدانان که توسط فرماندهی انگلیسی در پارک بلتی جمع شده بودند، توانستند آن را حداقل در برخی از جنبه های آن، به ویژه برای جنگ در دریا رمزگشایی کنند. آنها به خوبی در زندگینامه آلن تورینگ نوشته اندرو هاجز t6 و در تاریخ رمزنگاری سینگ [3] آمده است.
سایر ماشینها و سیستمهای دیگر بخشی از تاریخ رمزنگاری قرن بیستم هستند. بهترین سیستم شناخته شده که برای طولانی ترین مدت در برابر حملات رمزگشایی مقاومت کرده است، سیستمی است که به طور رسمی در سال 1977 توسط دولت ایالات متحده تأسیس شد، DES ( استاندارد رمزگذاری داده ها )، یک رمز تک الفبایی که امنیت آن بر روی کلید 56 بیتی (که 8 بیت کنترل هستند)، در سال 1998 شکسته شد. این اولین سیستم رمزگذاری تجاری است که به عنوان یک استاندارد توسط یک نهاد نظارتی ایجاد شد تا از گسترش سیستم های رمزگذاری ناسازگار با یکدیگر جلوگیری شود.
DES یک سری تبدیلات ابتدایی را انجام می دهد که چندین بار بر روی بسته های ساختاری مناسب متن تکرار می شود تا بیت هایی را که آن را تشکیل می دهند تحت یک تغییر کلی قرار دهد که اساساً به کلید انتخاب شده وابسته است: الگوریتم ها عمومی می شوند. کلید - با رعایت دقیقترین اصل کرکهوف - تنها دادهای است که کاربر تنظیم میکند.
جنبه مهم این است که رمزگذاری می تواند در زمان واقعی با یک کامپیوتر با قدرت متوسط انجام شود. علاوه بر این، سیستم متقارن است به این معنا که، مانند همه سیستمهایی که تا این لحظه مثال زده شده، از کلید مستقیماً برای رمزگشایی استفاده میشود. یک
عدد 56 بیتی حاوی مقدار زیادی اطلاعات است: شما 7، 2 x 10 16 کلید مختلف دارید. با این حال، از اولین ظهور، به نظر محققان برای مقابله با منابعی که به طور قابل پیش بینی در آینده توسعه خواهند یافت، کوتاه تر از آن به نظر می رسید. و همانطور که انتظار می رفت، این دلیل اصلی رمزگشایی آن بود، اگرچه این امر نیازمند قدرت هزاران رایانه بود که به طور همزمان کار می کردند، هماهنگ شده از طریق اینترنت .
در واقع، در زمینه ماشینهای محاسباتی بزرگی است که به مسائل رمزنگاری اختصاص داده شده است که در دهه 1900 این آگاهی به وجود آمد که برای داشتن یک رمز کامل ، یعنی رمزی که نمیتوان آن را شکست، کلید باید به این صورت باشد. اطلاعات زیادی به عنوان کلید پیام های ممکن. یک پارادوکس ظاهری، که با این حال، تنها مفهوم کلید رمزنگاری را به جلو می برد. به عنوان مثال رمز Vernam است که به نام مهندس ارتباطات راه دور گیلبرت ورنام (1890-1960) نامگذاری شده است که در آن کلید یک مولد اعداد تصادفی است. تعجب آور نیست که هر کلید را می توان به صورت عددی کدگذاری کرد: واضح است که با این سطح از پیشرفت و شروع روش های دیجیتال، می توان به خوبی فکر کرد که پیام نیز چیزی جز یک عدد نیست که در تعداد معینی کدگذاری شده است. از بیت ها . مشکل واقعی که باقی می ماند مشکل کلید است: تولید، حفاظت و انتقال آن.
به این ترتیب، با هر استفاده جدید، کلید همیشه جدید است. هرگز از انتقالی به انتقال دیگر تکرار نمیشود و در واقع، پس از استفاده حذف میشود (آمریکاییها از پد یکبار مصرف صحبت میکنند تا تاکید بر استفاده غیرقابل تکرار از کلید داشته باشند) اما راز واقعی اکنون در راه متمرکز شده است. که تولید می شود.
| اولین رمزی که توسط Vernam در سال 1917 طراحی شد شامل دستگاهی است که قادر به اجرای انحصاری یا V، مدت به ترم، سیگنال های دوتایی بر روی دو نوار است. در یک نوار متنی وجود دارد که باید رمزگذاری شود، در دیگری کلید: در نتیجه، در هر موقعیت خروجی ، 1 به دست می آید اگر و فقط اگر دو موقعیت متناظر روی نوارها متفاوت باشند: 0 و 1 یا 1. و 0. ابتکار روش در این واقعیت نهفته است که ناتوانی عملیات "a V -"، که در آن a یک متغیر باینری است: |
aV(aVb)=b
برگشت پذیری سیستم را تضمین می کند.
اما برای نشان دادن معنای استفاده از کلید یکبار مصرف لزوماً یک محیط تکنولوژیکی بسیار پیچیده ضروری نیست: برای مثال، به این فکر کنید که با همکار خود ثابت کنید که کلید انتقال پیام های رمزگذاری شده توسط نسخه خاصی از کمدی الهی داده شده است. . شما رمزگذاری à la Vigenère را با استفاده از تمام حروف متوالی کار دانته به عنوان کلید انجام می دهید: " nelmezzodelcammindinostravita...... " با این قرارداد که برای پیام بعدی کلید از جایی شروع می شود که در پیام قبلی متوقف شده است. بدیهی است که سیستم هیچ دوره ای ندارد: رمزگذاری هرگز به همان شکل تکرار نمی شود. اما ماشینی که با آزمون و خطا پیش می رفت، مطمئناً دیر یا زود می تواند پیام های شما را رمزگشایی کند و شاید همه آیات کمدی الهی را بازنویسی کند !
در این مرحله از توسعه، ما به ایدهای نیاز داریم که مفهوم کلید رمزنگاری را با امکانات بسیار زیادی ارائه کند و در عین حال آن را از نیاز به اشتراک گذاری بین چندین طرف، حتی بین فرستنده و گیرنده، رها کند. مدیریت کلیدها، که اغلب دست و پا گیر هستند، تولید آنها، ارسال آنها به گیرندگان، نیازهای امنیتی... این نقطه حیاتی واقعی سیستم های رمزگذاری است. و این همان چیزی است که از ایده کلید عمومی ، در مقابل استفاده خصوصی، شخصی و مخفیانه از کلید، پیشرفت زیادی دریافت کرد. کلیدی که میتوانید با هر کسی که میخواهد پیامی را رمزگذاری کند و برای شما ارسال کند، ارتباط برقرار کنید، اما برای رمزگشایی که فقط شما میدانید چگونه آن را انجام دهید مفید نیست.
تبادل کلید
آلیس و باب را از سر می گیریم که با مشکل مبادله کلیدی برای استفاده برای ارتباطات شخصی خود دست و پنجه نرم می کنند، اما از کنجکاوی چارلی در امان هستند. آنها امکان ملاقات ندارند اما ماشین هایی با ظرفیت محاسباتی و ارتباطی خوب دارند، علیرغم اینکه می دانند ایمیل هایشان مرتباً رهگیری می شود. آنها به این ترتیب پیش خواهند رفت: با تلفن - که توسط چارلی حسود نیز شنود می شود - یک عدد صحیح مثبت n را ثابت می کنند . سپس هر یک از آنها به تنهایی، بدون اینکه آن را برای کسی فاش کند، دیگری را انتخاب میکند: آلیس a را درست میکند و باب b را درست میکند ، آلیس به باب مقدار n a را میگوید و باب ارزش n b را به او میگوید (و چارلی به همه چیز گوش میدهد). اکنون آلیس n ab را صرفاً با بالا بردن مقداری که باب به او ابلاغ کرده است را به توان مخفی خود a محاسبه می کند و به طور مشابه باب همان مقدار را با افزایش na به توان b که فقط او می داند محاسبه می کند. این همه (در ویژگی جابجایی محصول):
(n a ) b = (n b ) a = n ab
و هر دوی آنها این شماره را می دانند که به عنوان کلید رمزنگاری آنها عمل می کند. چارلی ناامید n a و n b را جداگانه می داند اما a و b را نمی داند که باید دو لگاریتم پایه n محاسبه کند . این مشکل اوست، زیرا آلیس و باب اعداد ( n، a و b ) را به اندازه کافی بالا انتخاب کردند تا سیستمهای محاسباتی چارلی را خارج از این امکان قرار دهند، در اصل ساده اما در عمل بسیار وقتگیر.
میدانیم که موضوع کجاست: محاسبه نمایی، حتی با یک سیستم کم یا قدرتمند، میتواند به راحتی انجام شود در حالی که معکوس آن، لگاریتم، میتواند به منابع محاسباتی نیاز داشته باشد که از نظر زمان غیرقابل تحمل هستند.
این ایده ای است که در دهه 70 بوجود آمد و سپس در Diffie and Hellman [7] منتشر شد: ارائه یک تابع - معکوس بله، در غیر این صورت رمزگشایی ممکن نیست، اما به یک معنا به راحتی محاسبه می شود و بسیار دشوار است. محاسبه معکوس طولانی یا عملاً غیرممکن است - تابعی که در اصطلاحات آنگلوساکسون در حال حاضر مرسوم است، به آن trapdoor می گویند .
سقوط آسان است، در حالی که صعود به عقب عملاً غیرممکن است (مگر اینکه یک مسیر مخفی بدانید).
یکی از این توابع، در واقع توابعی که در گستردهترین پیادهسازیهای سیستمهای رمزنگاری مورد استفاده قرار میگیرد، با حاصل ضرب اعداد صحیح به دست میآید: در حالی که این یک عملیات آسان برای انجام حتی بین اعداد با ارقام زیاد است (به شرطی که محاسبه در دسترس داشته باشید. ابزارهای بسیار قدرتمند)، عملیات معکوس که تجزیه به عوامل است می تواند به طور غیرقابل تحمل طولانی باشد. تخمین های مربوط به فاکتورسازی تعدادی از چند صد رقم اعشار، علیرغم داشتن مدرن ترین سیستم های محاسبه سریع موجود، هنوز بر حسب میلیون ها سال اندازه گیری می شوند. این یک مسئله تئوری اعداد است که از نظر محاسباتی غیرقابل حل به نظر می رسد.
کلید عمومی
اولین کاربرد برای مشکل انتقال رمزگذاری شده پیام ها، یعنی مشکل اصلی رمزنگاری، بر اساس مشاهده - پیش پا افتاده اما تعیین کننده - است که کلید رمزگذاری کانال ارتباطی را متقارن می کند. از A به B منتقل میشود، اما این فرآیند همچنین میتواند بدون تغییر رمز یا کلید معکوس شود: احتمالاً، اگر رمز برگشتپذیر نباشد، همه عملیاتها باید معکوس شوند.
تقارن کانال - این جزء ساختاری فرآیند ارتباط - در عمل با یک تابع رمز ترفند تغییر میکند: کانال نامتقارن میشود. رمزگذاری فقط در یک جهت امکان پذیر است و خود فرستنده - که دستورالعمل های رمزگذاری را دارد - قادر به رمزگشایی پیام ها نیست.
اکنون دو کلید متمایز وجود دارد: یکی برای رمزگذاری، که برای همه کسانی که می خواهند پیام رمزگذاری شده ارسال کنند، به طور عمومی شناخته شده است، و دیگری برای رمزگشایی که توسط گیرنده پیام ها کاملاً مخفی نگه داشته می شود. بدیهی است که کلیدها به یکدیگر وابسته هستند - در غیر این صورت پیام ها هرگز نمی توانند رمزگشایی شوند - اما دانش یکی برای ردیابی دیگری کافی نیست... مگر اینکه شما رازی را بدانید: یک تابع ترفند.
مشکل اشتراک گذاری کلید رمزنگاری کاملاً حل شده است و سادگی رمزگذاری به دشواری شدید رمزگشایی مرتبط است. این همه به عملکرد ترفند بستگی دارد!
سیستم RSA
این سیستم، چند سال پس از ایده توابع ترفند ، در Rivest، Shamir و Adleman [8] ظاهر میشود و دقیقاً بر اساس دشواری یافتن منابع محاسباتی کافی برای تجزیه به عوامل اول اعداد صحیح است که دارای ارقام متعدد هستند.
الگوریتمی که برای اجرای عملی پیشنهاد شده است، از پیچیدگی محاسباتی برخی از فرآیندهای تئوری اعداد، مربوط به محاسبات مدولار (که در کادر مقابل بحث شده است، که نتایجی را که به الگوریتم اجازه عملکرد میدهد، نیز توضیح میدهد) بهرهبرداری میکند.
شایان توجه است که این نتایج، که همه خلاصه شده و به طور کامل در Disquisitiones Arithmeticae گاوس (1801) بیان شدهاند، اساساً برای اویلر و در برخی موارد برای فرما در قرن هفدهم شناخته شده بود. به نظر می رسد به کارگیری این نتایج، که در دوره ای یافت می شود که چشم انداز محاسبه سریع حتی از دور قابل تصور نبود، نمونه خارق العاده ای از ثمربخشی تفکر ریاضی و عقلانیتی است که در تحقیق این بزرگان ذاتی است. ارقام ریاضی
بیایید با توضیح ایده پشت سیستم رمزنگاری کلید عمومی شروع کنیم و مشاهده کنیم که برخی از عملیات که ممکن است در نگاه اول در مقایسه با زمان محاسبه بسیار گران به نظر برسند، در عوض به راحتی قابل محاسبه هستند: این مورد، برای مثال، نمایی و بزرگترین مقسومکننده مشترک است. از دو عدد - حتی بسیار بزرگ - و همچنین محاسبه مدول باقیمانده n. جالب است بدانید که این سادگی، علیرغم انواعی که در طول زمان ایجاد شده اند، اساساً توسط یک نتیجه کلاسیک دیگر با اهمیت بسیار ارائه شده است: الگوریتم تقسیمات متوالی یا الگوریتم اقلیدسی که ریشه و منطق آن در عناصر اقلیدس است. و در مسائل مورد بحث در قرن 3 قبل از میلاد (برای مشکلات پیچیدگی محاسباتی در مورد عملیات مختلف می توان به عنوان مثال Salomaa [9] یا Ferragine و Luccio [10] مراجعه کرد).
همه چیز برای راه اندازی سیستم آماده است: هر کسی که قصد دارد گیرنده پیام های محرمانه شود - فرض کنید باب است - کلید خود را تعمیر کرده و عمومی می کند، به طوری که هر کسی که می خواهد یک پیام رمزگذاری شده برای او ارسال کند (نه تنها آلیس، بلکه همچنین دیگران) می داند چگونه رفتار کند. برای این منظور، باب باید برخی از انتخاب ها و برخی عملیات مقدماتی را انجام دهد: توجه به این نکته که امنیت رمز به کیفیت این انتخاب ها بستگی دارد، اضافی است.
با این حال، در اینجا ارزش پرداختن به این جزئیات را ندارد، بلکه تلاش برای روشن کردن روش در اصول آن است (کسانی که برای دانستن این جزئیات بی تاب هستند باید با Koeblitz [11]، Salomaa [9] یا Ferragine و Luccio [10] مشورت کنند. ).
باب یک جفت از اعداد ( e, n ) را با این شرط انتخاب می کند که e و φ(n) ضریب اول مشترک نداشته باشند:
GCD(e, φ(n)) = 1
گفتیم که این انتخاب حتی در محاسبه مشکل ایجاد نمی کند. اگر دو عدد e و n کاملاً بزرگ باشند و همانطور که مشاهده شد بهترین کار این است که معیارهای مناسب برای افزایش استحکام سیستم رعایت شود. این جفت ( e, n ) کلید عمومی باب است که او آن را در دسترس همه قرار می دهد، اما مراقب باشید... باب هیچ اشاره ای به مقدار φ( n ) - حتی به آلیس - نخواهد کرد، زیرا این راز اوست. ، کلید شخصی او که به او امکان رمزگشایی پیام ها را می دهد.
در واقع، باب با استفاده از φ( n )، عدد d را محاسبه می کند که همخوانی درجه اول را حل می کند:
e*x≡1 (mod φ(n))
این عدد d (mod φ( n )) است که مستقیماً برای رمزگشایی پیام ها استفاده می کند. شرط اول بودن e و φ( n ) برای یکدیگر تضمین می کند که همخوانی قبلی یک راه حل منحصر به فرد را تا مدول همخوانی φ( n ) می پذیرد.
اکنون هر کسی توانایی ارسال یک پیام محرمانه را برای باب دارد و او آماده است تا آن را رمزگشایی کند. این روش به این صورت انجام می شود: برای مثال آلیس می خواهد پیام m را (که قبلاً به طور مناسب با یک عدد کدگذاری شده است) ارسال کند. برای این کار، m را به توان e ببرید و مدول باقیمانده n عدد به دست آمده را محاسبه کنید. او دقیقاً از اطلاعاتی که باب به همه اطلاع داده بود - کلید عمومی خود ( e, n ) - برای دریافت پیام رمزگذاری شده c استفاده کرد :
c≡m e (mod n)
چگونه باب می تواند پیام را بازسازی کند، یعنی از c به m برگردد ، و چرا هیچ کس دیگری که c را رهگیری می کند و کلید عمومی باب را می داند قادر به انجام همین کار نیست؟ برای باب آسان است، زیرا او φ(n) را می داند و d را محاسبه کرده است . او فقط باید پیام رمزگذاری شده c را به توان مخفی d برساند . در واقع، همانطور که پیدا شد، ed = kφ(n)+1 مربوط به مقداری عدد صحیح k است و بنابراین داریم:
c d ≡(m e ) d ≡m ed ≡m kφ(n)+1 ≡(m φ(n) ) k *m ≡m(mod n)
که در آن از ویژگی پایداری رابطه همخوانی با توجه به حاصلضرب و قضیه اویلر-فرمات استفاده کردیم: m φ(n) ≡1 (mod n).
رازی که فقط به باب اجازه می دهد پیام را رمزگشایی کند چیست؟ واضح است که در توان d قرار دارد که از کلید رمزگذاری e استفاده می کند و آن را معکوس می کند (مدول φ(n)) . و d با دانستن φ(n) به دست می آید: همانطور که گفتیم این راز واقعی است زیرا محاسبه φ(n) به اندازه تجزیه n به عوامل پیچیده است. وقتی باب کلید عمومی خود را انتخاب کرد، آینده نگری داشت که n را به عنوان حاصلضرب اعداد اول خاص انتخاب کند و بنابراین، به لطف خاصیت ضربی φ اویلر، محاسبه φ(n) برای او بسیار آسان است. در این فرآیند، ویژگیهای اساسی حساب مدولار و φ اویلر شناسایی خواهند شد.
استراتژی بهینه باب دقیقاً این است که n را به عنوان حاصل ضرب تنها دو عدد اول، به اندازه کافی بزرگ و نه خیلی نزدیک به یکدیگر انتخاب کند. به این ترتیب n = p*q با p و q اول است و داریم:
φ(n)=(p - 1)*(q - 1)
بنابراین، همه چیز بر اساس فاکتورسازی اول است. این واقعیت همچنین نشاندهنده «نقطه ضعف» سیستم رمزنگاری است: امنیت مبتنی بر «ناآگاهی» ما از بسیاری از پدیدههای مربوط به اعداد اول است. اگر و زمانی که تحقیقات ریاضی موفق به حل مسائل توزیع اعداد اول شود و روشی کارآمد برای فاکتورگیری بیابد، روش فوراً کارایی خود را از دست خواهد داد... و ما باید به توابع ترفند جدیدی روی بیاوریم.
بار دیگر، همانطور که اغلب اتفاق می افتد، پیشرفت فنی مستقیماً تابع دانش نظری است.
امضای دیجیتال
مشکل اصالت فرستنده اهمیت فزاینده ای پیدا می کند زیرا عملیات های بیشتر و بیشتری با ماهیت و اهمیت مختلف به صورت الکترونیکی انجام می شود. امضای دیجیتال در حال تبدیل شدن به یک ابزار قانونی در بسیاری از کشورها است.
اصل آن چیست؟ در واقع، با «معکوس کردن» اصل انتقال رمزگذاری شده با یک کلید عمومی به دست می آید. بنابراین، بیایید فرض کنیم که باب - همیشه او - می خواهد پیام را منتقل کند، اما این بار، جنبه مهم در رازداری m نهفته است - که همه باید بدانند - بلکه در این است که خود را با قطعیت توسط گیرنده شناسایی کند . این در نهایت عملکردی است که توسط امضای ما انجام میشود: فقط ما میتوانیم آن را انجام دهیم و در نتیجه همه میتوانند تشخیص دهند که یک سند از طرف ما آمده است.
به عنوان مثال، باب از طریق ایمیل از خارج به بانک خود می نویسد تا مقداری اعتبار را دریافت کند: شناسایی باید ایمن باشد. البته باب کلید عمومی خود را دارد ( e, n ) که همه میدانند و به تنهایی توان d را نیز محاسبه کرده است که به او امکان رمزگشایی پیامها را میدهد. با مسلح شدن به این داده ها، باب جفت ( m, m d ) را به عنوان پیامی به بانک خود می فرستد و با اطمینان شناسایی می شود زیرا با محاسبه ای مشابه آنچه که انجام شده است، بلافاصله این اتفاق می افتد:
m≡(m d ) e (mod n)
به عبارت دیگر، شخصی که پیام رمزگذاری شده md را ارسال کرده و اعلام می کند که پیام m به صورت متن واضح است ، فقط می تواند باب باشد. به دو واقعیت توجه کنید: اول اینکه باب صرفاً با اعلام نمایش d
امضا نمیکند ، که مجبور نیست فاش کند و برای تشخیص آن کافی نیست. و سپس، در نتیجه این واقعیت اول، هیچ "امضایی" جدا از اسناد وجود ندارد، که در جایی سپرده شده و در صورت لزوم برای مقایسه شناخته می شود: هر امضایی متناظر با یک سند است، با آن و فقط با آن زندگی می کند. حتی اگر باب کلید عمومی خود را انتخاب نکرده باشد، کسی می تواند آن را برای او انجام دهد. به عنوان مثال، فرض کنید که او مشتری یک موسسه اعتباری است که هنگام برداشت پول از یک دستگاه خودکار باید او را بشناسد. واضح است که مؤسسه باید به باب و سایر مشتریان کارتی با داده های مغناطیسی آنها ارائه دهد و کد شخصی را در اختیار آنها بگذارد که امکان شناسایی آسان را فراهم می کند. اما، از سوی دیگر، به همان اندازه روشن است که نگهداری اطلاعات مربوط به مشتریان و کدهای شخصی آنها در جایی، به عنوان مثال در یک پایگاه داده که امنیت آن باید دائماً نظارت شود، چقدر خطرناک است. سیستم امضای دیجیتال به مؤسسه اجازه میدهد تا برای هر مشتری کلید عمومی خود ( e, n ) را محاسبه کند، ضریب ویژه d را محاسبه کند ، آن را به طرف علاقهمند ارسال کند - مهم نیست که کلید را به آنها اطلاع دهد ( e, n ) - و سپس .. d را از فایل های خود حذف کنید. همچنین میتوان تشخیص را تنها با استفاده از ( e, n ) انجام داد، که میتوان آن را نیز در نمایش گذاشت و در دسترس همه قرار داد. محرمانه بودن سیستم مصادف با محرمانه بودن d است ، که فقط طرف ذینفع می داند: به نظر می رسد این آینده کدهای مخفی، کلیدهای عمومی و محاسبات در انتظار همه ما است.
قرعه کشی آلیس و باب
آنچه باید مورد بررسی قرار گیرد روشی است که در آن دو مدعی می توانند قرعه کشی را انجام دهند، بدون اینکه امکان ملاقات برای بررسی درستی انجام تمام عملیات ها وجود داشته باشد. این مشکل مستقیماً به رویههای رمزنگاری - انتقال و اعتبارسنجی پیامهای محرمانه - مربوط نمیشود، بلکه بر اساس همان اصل کلید عمومی است ، یعنی امکان انجام عملیاتی که معکوس آن برای محاسبه فوری قابل دسترسی نیست، مگر اینکه مقداری وجود داشته باشد. اطلاعات اضافی
در این حالت، آلیس و باب متقابلاً یک تابع ترفند f را انتخاب می کنند. بنابراین، آلیس، برای مثال، مقدار x آرگومان را ثابت میکند، f (x) را محاسبه میکند و به باب پیشنهاد میکند که به طور تصادفی خاصیتی از x را انتخاب کند که احتمال درستی آن 50٪ است: برای مثال، وقتی x یک عدد کامل است، از او می خواهد بگوید زوج است یا فرد. واضح است که برای باب ردیابی از f (x) تا x غیرممکن است: اگر او درست حدس بزند، پیروزی در تساوی متعلق به اوست، در غیر این صورت از آن آلیس است و خود باب می تواند به راحتی خود را در این مورد متقاعد کند. انتخاب تصادفی و منصفانه بود، همانطور که در قرعه کشی لازم بود.
معمولاً حتی برای رویه ای از این نوع جالب ترین توابع از نظریه اعداد گرفته می شود. در اینجا یکی است که از یک ویژگی غیر پیش پا افتاده استفاده می کند: مانند انتخاب کلید عمومی، آلیس دو عدد اول بسیار بزرگ p و q را ثابت می کند و حاصلضرب آنها n=p*q را محاسبه می کند . او ارزش n را به باب می گوید، اما نه فاکتورگیری را که طبق معمول راز اوست. به نوبه خود، باب نیز یک عدد صحیح u را بین 1 و n/2 انتخاب می کند ، u 2 (mod n) را محاسبه می کند و این عدد را به آلیس می رساند. آلیس به راحتی می تواند دو ریشه مربع u 2 را که در بازه (1,n/2) قرار گرفته اند پیدا کند زیرا او فاکتورگیری n را می داند و اگر مقدار u انتخاب شده توسط باب را حدس بزند، برنده قرعه کشی خواهد شد: زیرا این دقیقاً 50٪ شانس برنده شدن دارد. بنابراین آلیس انتخاب خود را به باب اعلام می کند، که تنها در صورتی می تواند موافقت کند که آلیس به درستی حدس زده باشد، زیرا در غیر این صورت از او خواسته می شود که بگوید جذر دیگر u 2 چیست ... اما او قادر به محاسبه آن نیست.
نتیجه گیری
اکنون واضح است که رمزنگاری - که به لطف نیازهای تجاری، دیپلماتیک و نظامی تکامل یافته است، اخیراً دنیای جاسوسان و ژنرال ها را رها کرده است (یا بهتر بگوییم دامنه عمل خود را گسترش داده است) و شامل عملیات هایی می شود که هر روز توسط همه انجام می شود. حوزه خصوصی و شخصی از این طریق بر مشکلاتی با ارزش اجتماعی و سیاسی تأثیر گذاشته است، دارای اهمیت اقتصادی و قانونی است، حریم خصوصی ما، آزادی بیان و محرمانه بودن ارتباطات ما را شامل می شود. این دیگر فقط یک واقعیت "فنی" نیست که در یک دنیای مهم کاربرد پیدا می کند، بلکه محدود و به علاوه برای آگاهی ما بیگانه است. نیاز به گرهگشایی این شبکه از برنامهها، تمایز پشتیبانی فنی از عملکرد، بهرهبرداری از کاربرد عملی و ارزش ایدهآل آن، یک کار بسیار پیچیده است زیرا موضوع به سرعت تکامل مییابد، دائماً همگام با انتشار روشهای محاسبه سریع و ارتباطات دیجیتال: در این رابطه شایسته است به کتاب گیوستوزی، مونتی و زیموئل [4] برای خواننده ایتالیایی اشاره شود. از سوی دیگر، پیچیدگی شدید مسائل مربوط به این واقعیت منعکس می شود که امروزه رمزنگاری خود را در تقاطع عملی و مفهومی رشته های علمی متعدد می بیند: حتی مشکل صرف پرداختن به واقعیت فنی ناب، صرف نظر از کاربردهای انجام شده. از آن، ما را وادار می کند تا با گشت و گذار در زمینه ماشین های محاسبه و نظریه اطلاعات، به روشی غیر پیش پا افتاده به نظریه الگوریتم ها و پیچیدگی محاسباتی روی آوریم : مجموعه ای از موضوعات بسیار مدرن، که در برخی موارد هنوز به دنبال رسمی بودن خود هستند. ساختار، با تأثیرات عمیق و متنوع بر یکدیگر، که از طریق آن وسعت مهارت های لازم تقویت می شود.
در مورد ریاضیات، امروزه به نظر می رسد نظریه اعداد موضوعی است که برای یافتن توابع ترفند و یافتن استراتژی های پیچیده الگوریتمی مناسب است. اما رمزنگاری همچنین به طور گسترده به تکنیکهای آماری و روشهای حساب احتمالات، ساختارهای جبری و اخیراً هندسه جبری نیز میپردازد.
همانطور که مشاهده می شود، در پوشش مدرن رمزنگاری کلید عمومی، یک زمینه تحقیقاتی با علاقه نظری بزرگ است که مستقیماً با ارزش برنامه ها مرتبط است، در واقع اغلب بلافاصله توسط نیازهای آنها دیکته می شود.
اما شایان ذکر است که منطقه زمانی سیستم های رمزنگاری کاملاً آزاد نیست. به دلایل امنیتی، برنامههای رمزگذاری در نظر گرفته شده برای برنامههای غیرنظامی تحت کنترل هستند و با برخی پیچشهای خندهدار، با «سلاحهای جنگی» با هدف ممنوعیت صادرات آنها برابر میشوند: این داستان واقعی است که فیل زیمرمن، نویسنده کتاب به آن پرداخته است. نرم افزار PGP ( Pretty Good Privacy ) و مدافع متقاعد شده حق شخصی برای حفظ حریم خصوصی است که برنامه آن را دیگر نمی توان آزادانه از اینترنت دانلود کرد.
و بنابراین، به نوعی، رمزنگاری به اجبار به حوزه مشکلات نظامی، تحت پوشش محرمانه، "پس زده می شود".
https://matematica.unibocconi.eu/articoli/invito-alla-crittografia