الفصل الرابع

التشفير: الحياة السرية للأعداد الأوَّلية

في هذا الفصل سوف يدرك القارئ أن مجموعة أعداد العدِّ عُرفتْ منذ العصور القديمة بأنها مخزن للألغاز والأسرار، والكثير منها لم يُحلَّ حتى الآن. هذا كافٍ بالنسبة لكثيرٍ منا من أجل تبرير الدراسة الجادة المستمرة للأعداد، ولكن ربما يكون للآخرين رأي مختلف. ولما كانت هذه الألغاز مثيرة للاهتمام وصعبة الحل، فربما يُعتقد أن لها صلة ضعيفة ببقية المعارف البشرية، ولكنَّ ذلك اعتقاد خاطئ.

تَبيَّن على مدى العقود القليلة الماضية أن الأسرار العادية؛ الأسرار التي ننغمس جميعًا فيها من وقت لآخر، يمكن أن تكون مشفَّرة في صورة عددية. هذا هو ما يحدث الآن بالفعل، ويمكن أن تكون أثمنُ أسرارنا — سواء كانت تجارية أو عسكرية، شخصية أو مالية، سياسية أو شائنة بكل ما في الكلمة من معنى — محميةً على شبكة الإنترنت عن طريق إخفائها في صورة أعداد العد العادية.

تحوُّل الأسرار إلى أعداد

كيف يكون كل هذا ممكنًا؟ يمكن أن يُعبَّر عن أي معلومات بالكلمات، سواء كانت قصيدة أو كشف حساب مصرفي أو مخطط تصميم لسلاح أو برنامج كمبيوتر. مع ذلك، ربما نحتاج لزيادة حروفنا الأبجدية المستخدمة في تكوين كلماتنا لِما هو أكثر من الحروف الأبجدية العادية. ربما نزيد رموزًا رقمية وعلامات ترقيم، بما في ذلك رموز خاصة للمسافة بين الكلمات العادية، مع ذلك، هذه هي الحالة التي يمكن فيها التعبير عن كل المعلومات التي نرغب في نقلها — بما في ذلك تعليمات إنتاج الصور والرسوم البيانية — باستخدام كلمات من أبجدية لا تزيد، على سبيل المثال، عن ألف رمز. يمْكننا عد هذه الرموز؛ ومن ثم نمثِّل كل رمز بعدد على نحو فريد. ونظرًا لأن الأعداد لا تكلِّف شيئًا ولا تنضب، ربما يكون من الملائم استخدامُ الأعداد كلها بعدد الخانات نفسه لهذا الغرض (لذا على سبيل المثال، يُمثل كل رمز على نحو فريد باستخدام رقم التعريف الشخصي PIN الخاص به والمكون من أربعة خانات). ويمكننا أن ننظم الرموز معًا في سلسلة بالصورة اللازمة لإنتاج عدد طويل ضخم يقدم المعلومات كلها. ويمكننا حتى العمل بالنظام الثنائي إذا أردنا؛ ومن ثم نبتكر طريقة لترجمة أية معلومات إلى سلسلة طويلة مكونة من الأصفار والآحاد. ويمكن حينها تشفير كل رسالة قد نرغب في إرسالها في صورة سلسلة ثنائية، ثم يُفك تشفيرها في الطرف الآخر عن طريق كمبيوتر مبرمج على نحو مناسب، لكي تُجمَع وتُترجَم بلغة عادية يمكننا جميعًا فهمها. هذا هو أول ما يجب إدراكه. من أجل إرسال رسالة بين شخص وآخر، يكفي — نظريًّا وعمليًّا — أن تتوافر القدرة على إرسال أعداد من شخص إلى شخص آخر.

ومع ذلك، فإن تحويل الرسائل إلى أعداد ليس في حد ذاته الفكرةَ المذهلة؛ إذ من المؤكد أن العملية نفسها التي تُحوَّل فيها كلُّ المعلومات إلى صيغة عددية ربما تكون مَخْفِيَّة عن العامة، ولكنها مع ذلك ليست مصدر الحماية ضد المتلصصين. في الواقع، من وجهة نظر علم التشفير، ربما نحدد أي رسالة — أو «نص عادي» كما يُطلق عليها — من خلال العدد الذي يمثلها؛ ومن ثم ننظر للعدد على أنه النص العادي نفسه؛ حيث من المفترض أن يستطيع أي شخصٍ الوصولَ للوسيلة التي ستسمح بتحول إحدى صور النص إلى صورة أخرى. ولا تُعتبر السرِّيةُ بالفعل سرِّيةً إلا عندما نُخفي أعداد النص العادي باستخدام أعداد أخرى.

اسمح لي أن أعرفك على الرموز الزائفة الموجودة في السيناريوهات المختلفة للتشفير، التي تعبر عن دراسة الشفرات (الأكواد السرية). سنتخيل أن أليس وبوب يرغبان في التواصل معًا دون أن تَسْتَرِقَ إيف — المتنصتة — السمع إليهما. ربما نتعاطف مع أليس وبوب على نحو غريزي ونرى أفعال إيف سيئة، ولكن بالطبع قد يكون العكس هو الصحيح؛ إذ قد تمثل إيف سلطة شُرطِيَّة شريفة تكافح من أجل حمايتنا من مؤامرات بوب وألِيس الشريرة.

أيًّا كانت المواقف الأخلاقية للأشخاص الثلاثة، توجد طريقة عتيقة يمكن أن يستخدمها بوب وأليس من أجل إخراج إيف خارج المحادثة بينهما، حتى لو اعترضت إيف الرسائلَ المتبادلة بينهما؛ فيمكنهما تشفير البيانات باستخدام مفتاح تشفير لا يعرفه إلا أليس وبوب. ما يمكنهما فعله هو التقابل في بيئة آمنة يتبادلان فيها عددًا سريًّا ( مثلًا) ثم يعودان كلٌّ إلى منزله. وعندما يحين الوقت، سترغب أليس في إرسال رسالة إلى بوب، ولنفترضْ أن الرسالة يمكن تمثيلها — لمجرد توضيح الفكرة — بعدد من خانة واحدة بين و . وفي اليوم الموعود، ترغب أليس في إرسال رسالة إلى بوب. فتأخذ الرسالة وتضيف إليها المكون السري؛ أيْ تخفي قيمتها الحقيقية بإضافة ثم ترسل الرسالة إلى بوب عن طريق قناة تواصل غير آمنة. فيتسلم بوب هذه الرسالة ويطرح منها العدد السري للحصول على النص العادي لرسالة أليس .
مع ذلك، تدرك إيف الشريرة ما ينوي هذان الاثنان فعله، وبالفعل تنجح في اعتراض الرسالة المشفرة . ولكن ماذا يمكن أن تفعل بها؟ ربما تعلم — كما نعلم نحن أيضًا — أن أليس أرسلت رسالة من بين تسع رسائل محتملة ، ، ، …، إلى بوب، وتعلم أيضًا أنها شفَّرَتها بإضافة عدد للرسالة، لا بد أنه يقع بين ، و . مع ذلك، نظرًا لأنها لا تستطيع معرفة أيٍّ من هذه الأعداد المخفية تم استخدامه (فهي ليست على علم بالسر)، فإنها لا تعلم النص العادي الفعلي للرسالة التي أرسلَتْها أليس إلى بوب، الذي لا يزال على الأرجح أحد الاحتمالات التسعة. وكل ما تعرفه هو أن أليس أرسلت رسالة إلى بوب، ولكنها لا تعرف محتواها.
قد يبدو أنَّ أليس وبوب محصَّنان الآن من شر إيف ويمكنهما التراسل على نحو آمن باستخدام العدد السحري من أجل إخفاء كل ما يريدان قوله. لكن الأمر ليس كذلك. فالأجدر بهما تغيير ذلك العدد، بل الأفضل استخدام عدد سري جديد كل مرة؛ لأنهما إن لم يفعلا ذلك فسوف يبدأ النظام في تسريب معلومات لإيف. على سبيل المثال، لِنَقُلْ إنه بعد أسبوع ترغب أليس في إرسال نفس رسالة العدد إلى بوب. فحينها، سيسير كل شيء كما حدث من قبل، وسوف تعترض إيف مرة أخرى العدد الغامض من موجات البث، ولكن هذه المرة سوف يخبرها شيئًا. سوف تعلم إيف أنه أيًّا كانت الرسالة، فهي الرسالة نفسها التي أرسلتها أليس إلى بوب في الأسبوع الأول؛ وهذا شيء لا يرغب أليس وبوب في أن تعرفه إيف.

غير أن ذلك لا يمثل مشكلة كبيرة لأليس وبوب. فعندما تقابلا في المرة الأولى لتبادُل مفتاح الشفرة، كان يمكن لأليس أن تقدم لبوب قائمة طويلة مرتبة من آلاف الأعداد السرية — بدلًا من الاتفاق على عدد واحد سريٍّ فحسب — حيث يُستخدم واحد تلو الآخر؛ ومن ثم يتجنبان أية احتمالية لوقوع مصادفات ذات معنًى في عمليات التواصل المتاحة على نحو علني.

وهذا بالفعل ما يحدث في الواقع. ويُطلق على هذا النوع من نظم التشفير «دفتر المرة الواحدة»؛ إذ يُخفي المرسل والمتلقي النص العادي بعدد من الدفتر يُستخدم لمرة واحدة، ثم يتخلى المرسل والمتلقي عن هذه الورقة (العدد) من الدفتر بعد إرسال الرسالة وفك تشفيرها. وتمثِّل طريقة دفتر المرة الواحدة نظامًا آمنًا تمامًا؛ إذ إن الرسائل غير المؤمَّنة التي تنتقل في العلن لا تحتوي على أية معلومات حول محتوى النص العادي. ولفك تشفيرها يحتاج الشخص المعترِض للرسالة إلى الحصول على هذا الدفتر من أجل التوصُّل إلى مفتاح التشفير وفك التشفير.

المفاتيح وتبادل المفاتيح

يبدو أن مشكلة التواصل الآمن حُلتْ بالكامل بواسطة دفتر المرة الواحدة، وهذا حقيقي نوعًا ما. مع ذلك، تتمثل مشكلة الشفرات التي على شاكلة دفتر المرة الواحدة في أنها تتطلب من الطرفين تبادُل المفتاح من أجل استخدامها. ويتطلب ذلك في الواقع الكثيرَ من الجهد. وبالنسبة للاتصالات عالية المستوى — على غرار الاتصالات بين البيت الأبيض والكرملين — لا يمثِّل المالُ مشكلة، ويَحْدث التبادل اللازم تحت ظروف أَمنيَّة عالية المستوى. على الجانب الآخر، يحتاج الأشخاص والمؤسسات كافةً في المعاملات اليومية للتواصل بعضُهم مع بعض على نحو سري. ولا يستطيع الطرفان تحمُّل الوقت والطاقة اللازمَين لتأمين تبادُل المفتاح، وحتى إذا تم تأمين هذا عن طريق طرف ثالث موثوق فيه، يمكن أن تكون العملية مكلِّفة للغاية.

إن موطن الضعف في كل الشفرات التي استُخدمت لآلاف السنوات حتى سبعينيات القرن العشرين هو أنها كانت «شفرات متماثلة» كلها؛ مما يعني أن التشفير وفك التشفير كانا يَتِمَّان باستخدام مفتاح واحد. وسواء كانت الشفرات بسيطة، عبارة عن تغيير في ترتيب الحروف الأبجدية البسيطة كالتي استخدمها يوليوس قيصر، أو معقدة كشفرة إنيجما المعقدة التي استخدمت في الحرب العالمية الثانية، فقد عانت جميعها من موطنِ ضعفٍ مشترك؛ هو أنه بمجرد أن يعرِف العدو كيفية تشفيرك لرسائلك، يمكنه فك تشفيرها تمامًا كما تفعل أنت. ومن أجل الاستفادة من الشفرة المتماثلة يحتاج الطرفان المتواصلان تبادُل مفتاح الشفرة على نحو آمن.

يبدو أنه افتُرض ضمنًا أن هذا مبدأ لا مفرَّ منه في الشفرات السرية؛ فمن أجل استخدام الشفرة يحتاج الطرفان، بطريقة أو بأخرى، تبادُلَ مفتاح الشفرة وإبقاءه سرًّا عن الأعداء. وبالطبع ربما يعبِّر هذا الأمر عن منطق رياضي سليم.

وهذا نوع من الافتراض يثير الشك لدى علماء الرياضيات. فنحن نتعامل مع موقف رياضي في الأساس؛ لذا قد يتوقع المرء ترسيخ هذا المبدأ على أسس قوية وتمثيله من خلال نظرية رياضية. بَيْدَ أنه لا توجد مثل هذه النظرية، والسبب في عدم وجود مثل هذه النظرية هو أن هذا المبدأ ببساطة ليس صحيحًا، كما تكشف التجربة الفكرية التالية.

لا يتطلب النقل الآمن لرسالةٍ من أليس لبوب — في حد ذاته — تبادُل مفتاح الشفرة؛ حيث يمكنهما متابعة الأمر كما يلي. تكتب أليس النص العادي لرسالتها لبوب، وتضعه في صندوق تؤمنه من خلال قفل، على أن تملك هي فقط مفتاح هذا القفل، ثم ترسل الصندوق إلى بوب الذي لا يستطيع بالطبع فتْحه، غير أن بوب يضيف قفلًا آخر للصندوق، الذي يمتلك هو وحده مفتاحه، وبعد ذلك يُعاد الصندوق إلى أليس، فتزيل قفلها عنه، وترسله للمرة الثانية إلى بوب، وهذه المرة يفتح بوب الصندوق ويقرأ رسالة أليس على نحو آمن؛ إذ لديه عِلم بأن إيف المتطفلة لم تستطع اختلاس النظر لمحتويات الصندوق خلال عملية التسليم. وبهذه الطريقة يمكن إرسال رسالة سرية إرسالًا آمنًا — باستخدام قناة تواصل غير آمنة — دون أن يتبادل أليس وبوب المفاتيح. يبين هذا السيناريو الخيالي أنه لا يوجد قانون ينص على وجوب تبادل المفتاح خلال تبادل الرسائل المؤمَّنة. وفي النظام الحقيقي، ربما يكون مفتاح أليس وبوب هو شفرتهما الخاصة للرسالة وليس شيئًا ماديًّا يمنع المتلصصين المحتملين من الوصول للنص العادي. وربما يستخدم أليس وبوب هذا التبادل الأول فيما بعدُ لإرساء شفرة متماثلة عادية يمكن أن تُستخدم في إخفاء كل الاتصالات المستقبلية.

في الحقيقة، هذه هي الطريقة التي غالبًا ما تنشأ من خلالها قناة تواصل غير آمنة في العالم الواقعي. مع ذلك، فاستبدال الشفرات الشخصية بالأقفال المادية ليس أمرًا سهلًا. فعلى النقيض من الأقفال، يمكن أن تتداخل شفرتا أليس وبوب معًا؛ مما يجعل فك التشفير (أي فتح القفل) الذي تقوم به أليس أولًا ثم بوب لا ينجح. مع ذلك، كان وايتفيلد ديفي ومارتن هيلمان أول من أثبت علنًا أن هذه الطريقة يمكن أن تكون فعالة في عام ١٩٧٦.

يوجد منهج آخر ذو صلة هو «التشفير غير المتماثل» أو «التشفير بالمفتاح العام»، وفيه يعلِن كلُّ شخص عن مفتاحه العام الذي يستخدم لتشفير الرسائل المرسلة للشخص الآخر. بيد أن كل شخص يحمل أيضًا مفتاحًا خاصًّا لا يمكن بدونه قراءة الرسائل المشفرة باستخدام مفتاحه العام الفريد. وباستخدام تشبيه القفل، تُقَدِّم أليس لبوب صندوقًا يضع فيه النص العادي لرسالته مع قفل مفتوح (مفتاحها العام) تمتلك هي فقط مفتاحه (مفتاحها الخاص).

قد يبدو نظام المفتاح العام العملي مَطلبًا مبالغًا فيه؛ إذ إن المطلبين المتلازمين — الأمان وسهولة الاستخدام — يبدوان متعارضين. غير أن التشفير السريع الآمن متاح للعامة على الإنترنت، حتى لو أدركوا بقدر ضئيل أنه موجود ويحمي مصالحهم. ويتعلق الأمر برمَّته بالأعداد، والأعداد الأولية في هذا الموضوع بالذات.

كيف تحمي الأعدادُ الأولية السرية أسرارَنا؟

تذكَّرْ أن كلَّ رسالةِ نصٍّ عاديٍّ تُمثَّل بعدد واحد فحسب؛ لذا فمن الطبيعي محاولة إخفاء هذا العدد باستخدام أعداد أخرى. أكثر الطرق شيوعًا للقيام بذلك تكون باستخدام ما يطلق عليه عملية تشفير ريفيست وشامير وأدلمان، التي نُشرت في عام ١٩٧٨ عن طريق مبتكريها رون ريفيست وآدي شامير وليوناردو أدلمان. وفي هذه الطريقة، يتكون المفتاح الخاص بكل شخص من ثلاثة أعداد و و ، بحيث يكون و عددين أوليَّين (كبيرين للغاية) والمكون الثالث هو عدد التشفير السري لأليس، وسوف نشرح دوره في الوقت المناسب. تُقدم أليس للآخرين ، وهذا ناتج عدديها الأوليَّين السريين، وعدد التشفير (الذي يكون عددًا صحيحًا عاديًّا، لا يرتبط بأي شكل من الأشكال بالثابت الخاص الذي يطلق عليه المذكور في الفصل الثاني).
إليك المثال البسيط التالي للتوضيح: لدى أليس العدد الأولي والعدد الأولي بحيث . إذا حددتْ أليس عدد التشفير الخاص بها ليكون ، إذن فسيكون مفتاحها العام . ولتشفير الرسالة ، يحتاج بوب فقط و . مع ذلك، يتطلب فك تشفير الرسالة المشفرة التي أرسلها بوب إلى أليس عددَ فكِّ التشفير ، الذي اتضح في هذه الحالة أنه ، كما سنوضح بعد قليل. إن العمليات الرياضية التي تسمح بحساب تتطلب بأن يكون العددان الأوَّليان و معلومَين. في هذا المثال التوضيحي، بمعرفة أن ، يمكن لأي شخص أن يكتشف سريعًا أن و . مع ذلك، إذا كان العددان الأوليان و كبيرين للغاية (عادة ما يتكونان من مئات الخانات)، تصبح هذه المهمة مستحيلة عمليًّا لأي نظام حاسوبي تقريبًا، على الأقل لفترة قصيرة معتدلة، على غرار أسبوعين أو ثلاثة أسابيع. بإيجاز، يعتمد نظام التشفير بطريقة عملية تشفير ريفيست وشامير وأدلمان على الحقيقة التجريبية التي تنص على أنه من الصعب للغاية إيجاد العوامل الأولية للعدد الكبير جدًّا جدًّا. أما الجزء الأروع الذي سنشرحه في بقية الفصل فيتمثل في تصميم طريقة يمكن من خلالها تشفير عدد الرسالة باستخدام العددين المعروفين علانيةً و فحسب، ولكن فك التشفير في الواقع يتطلب امتلاك العوامل الأولية للعدد .
إليك طريقة العمل. ما يرسله بوب عبر الأثير ليس نفسه، وإنما العدد الباقي من قسمة على . بعد ذلك يمكن لأليس استعادة من خلال أخذ هذا العدد الباقي وبالمثل حساب العدد الباقي من قسمة على . تضمن الأساليب الرياضية الأساسية أن يكون الناتج لدى أليس هو الرسالة الأصلية ، التي يمكن حينها فك تشفيرها وتحويلها إلى نص عادي باستخدام النظام الحاسوبي لدى أليس. وبالطبع يحدث هذا الأمر على نحو مثالي خلف الكواليس بالنسبة لأي أليس وبوب حقيقيَّين.
يبدو أن الشيء الوحيد المهم حقًّا الذي تفتقده إيف هو عدد فك الشفرة . إذا عرفتْ إيف هذا العدد يمكنها أن تفك شفرة الرسالة مثلها مثل أليس. ويبدو أن هو حل لمعادلة معينة. وحل هذه المعادلة سهل للغاية حاسوبيًّا، ويعتمد على خوارزميات إقليدس المنشورة في «كتب إقليدس» في عام ٣٠٠ قبل الميلاد. ليس هذا مكمن الصعوبة، إنما تتمثل الصعوبة في أنه ليس ممكنًا اكتشافُ المعادلة التي يجب حلها بالضبط ما لم تكن تعلم على الأقل أحد العددين الأوليَّين و ، وهذه هي العقبة التي تعوق إيف عن تحقيق هدفها.
يمكننا توضيح المزيد عن كيفية عمل هذه الأعداد المتضمنة في العملية؛ أولًا: توجد مشكلة واضحة بالفعل في مهمة بوب الأولى. فالعدد كبير، والعدد ضخم (يتكون تقريبًا من مائتي خانة) وحتى إذا لم يكن كبيرًا بهذا الحجم، فسيكون العدد كبيرًا للغاية أيضًا. وبعد حسابه، علينا قسمة على العدد للحصول على الباقي ، الذي يمثل النص المشفر. ربما يبدو أن الحسابات صعبة للغاية لدرجة لا تجعلها عملية. وينبغي أن نعي أنه بالرغم من قوة أجهزة الكمبيوتر الحديثة، فإن لها حدودًا. وعندما تتضمن الحسابات أعدادًا مرفوعة لقوة كبيرة للغاية، فإنها يمكن أن تتخطى قدرات أي نظام حاسوبي. ولا يمكننا بالتأكيد افتراض أن أي حسابات عملية نخضعها للكمبيوتر يمكن إجراؤها في فترة زمنية قصيرة.
الأمر المبشِّر بالنسبة لبوب هو أنه من الممكن إيجاد العدد الباقي المطلوب دون القيام بعملية قسمة مطولة على الإطلاق. في الواقع، تعتمد البواقي على البواقي فحسب، وإليك مثالًا لتوضيح المقصود. ما هما الرقمان الأخيران في العدد ؟ (هذا يعني: ما الباقي عند قسمة هذا الرقم على ؟) لكي نجيب على هذا السؤال، ربما نبدأ في حساب القوى الأولى القليلة المرفوع إليها العدد 7: ، ، ، ، … مع ذلك، سوف يتضح سريعًا أن الحجم الكامل لهذه الأعداد سيصعب التعامل معه قبل الاقتراب من العدد . على الجانب الآخر، إذا حسبنا قوةً بعد أخرى، فسنجد نمطًا يظهر. والملاحظة الرئيسية هي أننا حينما نحسب القوى المتتالية، نجد أن الخانتين الأخيرتين من النتيجة تعتمدان فقط على الخانتين الأخيرتين في العدد السابق؛ إذ إنه عندما نقوم بالضرب، فإن الأرقام الموجودة في خانة المئات وما بعدها لا يكون لها تأثير على ما تنتهي إليه خانتا الآحاد والعشرات.
الأكثر من ذلك أنه نظرًا لأن ناتج ينتهي بالرقمين في الخانتين الأخيرتين، فإن ناتج رفع العدد للقوى الأربعة التالية سوف ينتهي بالأعداد ، ، ، ثم مرة أخرى. وهكذا، بينما نحسب القوى المتتالية، سوف يكرر نمط الخانتين الأخيرتين هذه الدورة الرباعية ببساطة مرارًا وتكرارًا. وبالعودة للسؤال المذكور سابقًا، نظرًا لأن ، فسوف نمر خلال هذه الدورة تسع مرات ثم نأخذ ثلاث خطوات إضافية من أجل حساب الرقمين الموجودين في الخانتين الأخيرتين من ناتج ؛ ومن ثم فلا بد أن يكون .
ينجح هذا بوجه عام. لكي تجد الباقي عند قسمة العدد المرفوع لقوة ما على مثلًا، نحتاج فقط أن نأخذ الباقي عند قسمة على ونتتبع البواقي على حين نأخذ القوى المتتالية المرفوع إليها . وعندما نعمل على الباقي ، الذي سيكون عددًا يتراوح بين صفر و ، يقول علماء الرياضيات إننا نستنبط باقي القسمة على ، ونتخلص من أي مضاعفات لعدد قد تظهر؛ إذ إنها تترك باقيًا يساوي صفرًا عند قسمتها على ؛ ومن ثم لا يمكنها أن تسهم في قيمة الباقي المتناهي .
ربما لا تزال تشك في أني قد تلاعبتُ بالأدلة عن طريق اختيار مثال تترك فيه قوةٌ صغيرةٌ للغاية باقيًا يساوي ؛ في هذا المثال كان أكبر من مضاعف بمقدار . مع ذلك، فهذا صحيح جزئيًّا فقط؛ إذ يتضح أنه إذا أخذنا أي عددين و ، يكون القاسم المشترك الأعظم بينهما هو (نطلق على هذين العددين «عددين أوليَّين فيما بينهما»)، فإنه يوجد دائمًا قوة ؛ حيث تساوي عند قسمتها على ، بمعنى بقاء عند القسمة على . ومن هذه النقطة، فإن بواقي القوى المتتالية تتبع دورة من الطول . مع ذلك، يمكن أن يكون من الصعب التنبؤ بقيمة ، ولكن من المعروف أن يجب أن تساوي أو تكون أحد عوامل العدد الذي يُكتب عادة بالصورة ؛ أيْ قيمة «دالة فاي» لأويلر.
والآن، ما هي ؟ تُعرَّف بأنها عدد الأعداد حتى التي تكوِّن مع أعدادًا أولية فيما بينها. على سبيل المثال، إذا كان ، فإن مجموعة الأعداد المقصودة هي ، وتتضمن كل الأعداد حتى العدد ، التي ليس لها عامل مشترك مع (عدا العامل الحتمي ). ونظرًا لأن هذه المجموعة تتضمن عناصر، نرى أن . لحسن الحظ، توجد طريقة أسهل لإيجاد لا تستلزم وضع قائمة واضحة بكل الأعداد الصحيحة التي تكوِّن مع أعدادًا أولية فيما بينها ثم حساب عددها. فكما هي الحال مع كل الدوال ذات هذه الطبيعة، يمكن التعبير عن قيمتها من خلال عملية تحليل لعوامله الأولية. وبالفعل نحتاج فحسب لمعرفة العوامل الأولية للعدد ، لكي يمكن إيجاد عن طريق ضرب في كل كسر ؛ حيث تمثل كل القواسم الأولية للعدد . على سبيل المثال، العوامل الأولية للعدد هي و ؛ لذا الإجابة في هذه الحالة هي:
وهي النتيجة نفسها التي حصلنا عليها مباشرةً من التعريف. وباستخدام هذه الطريقة، ربما ترغب في التحقق بنفسك من أن ، وهكذا — على سبيل المثال — يتبع ذلك أن تساوي عند قسمتها على . مع ذلك، كما رأينا بالفعل، أقل قوة للعدد يَنتج عنها باقٍ يساوي ليست وإنما القاسم الخاص بها.
كل هذا يعطي إشارة إلى أن العدد الذي أرسله بوب إلى أليس — مقسومًا على — يمكن حسابه بالفعل دون جهد كبير من جانب كمبيوتر بوب. مع ذلك، فالأعداد المستخدمة في الواقع كبيرة للغاية؛ لذا يلزم مزيد من التوضيح لإظهار أنه يمكن التعامل معها. والقوى الكبيرة المستعملة في حساب باستخدام الكمبيوتر يمكن التعامل معها على مراحل عن طريق عملية تُعرف باسم «رفع القوة الجبرية السريع». ودون الخوض في تفاصيل، تتضمن العمليةُ عملياتِ تربيعٍ وضرب متتالية للقوى من أجل الوصول إلى مقسومًا على ؛ حيث تقود الصيغة الثنائية للعدد الخوارزميةَ للوصول السريع للباقي المطلوب في خطوات قليلة نسبيًّا.

إقليدس يوضح لأليس كيفية التوصل لعدد فك الشفرة

العدد الذي يفك الشفرة هو العصا السحرية لدى المتلقي التي تسمح له باستنباط الرسالة. يُختار هذا العدد على أساس أن يَترك ناتجُ باقيًا يساوي عند القسمة على . ونظرًا لأن هو ناتج ضرب عددين أوليَّين مختلفين، فإن قيمة . ويتضح أنه يوجد دائمًا قيمة واحدة فقط للعدد في نطاق الأعداد وصولًا إلى الذي يملك السمة المطلوبة.
يستطيع كمبيوتر أليس أن يجد باستخدام أداة جبرية عمرها أكثر من ٢٣٠٠ عام، وهي خوارزمية إقليدس التي سنشرحها بعد قليل. ويمكن لكمبيوتر إيف أيضًا أن يفعل الأمر نفسه إذا كان يَعرف فحسب المعادلةَ التي يجب حلُّها. مع ذلك، نظرًا لأن و لا يعلمهما إلا أليس، فكذلك أيضًا ، ولا تَعرف إيف من أين ستبدأ.
إن وجود مضمون فقط إذا وُضع قَيْد بسيط معين على عدد التشفير (المعلَن). يجب أن تَضْمن أليس أن ليس لديه عامل أوَّلي مشترك مع . ويمكن فعل ذلك بسهولة تامة؛ حيث يمكن لأليس أن تَختبر قسمة على أعداد أولية معينة؛ ومن ثم تتأكد من أن يفي بهذه المتطلبات دون كشف هوية و . وفي الواقع، قيمة المستخدمة في أغلب الأحيان فعليًّا هي «عدد فيرما الأولي» الرابع ؛ وهذه القيمة لديها سمة نادرة على نحو خاص، وهي أنه من الممكن رسم مضلع منتظم بأضلاع باستخدام مسطرة وفرجار. مع ذلك، ترجع فائدته في التشفير إلى كونه عددًا أوليًّا كبيرًا باعتدال يتخطى مضاعفات بمقدار بالضبط، وهو ما يتوافق جيدًا مع عملية الرفع الجبري السريع المذكورة سابقًا.
وبالعودة إلى خوارزمية إقليدس، فإنها تبدأ بملاحظة أنه من الممكن إيجاد العامل المشترك الأعظم لأي عددين بالطرح المتتابع. (العامل المشترك الأعظم يُعرف أيضًا باسم «القاسم المشترك الأعظم».) نلاحظ أن يتمتع بِسَمة أن أيَّ عامل مشترك بين أي عددين من الثلاثة أعداد و و سوف يكون أيضًا أحد عوامل العدد الثالث. على سبيل المثال، إذا كان عاملًا مشتركًا بين و ؛ حيث و مثلًا، نجد أن ؛ مما يمنحنا تحليلًا للعدد إلى عوامل أولية يتضمن القاسم . على وجه الخصوص، العامل المشترك الأعظم للعددين و هو العامل المشترك الأعظم نفسه للعددين و . ونظرًا لأن هذين العددين أصغر من ، فإننا نواجه الآن المشكلة نفسها ولكنها تنطبق على زوج من الأعداد الأصغر. وسوف يؤدي تكرار هذه الفكرة في النهاية إلى زوج يكون فيه العامل المشترك الأعظم بديهيًّا. (في الواقع، العددان الموجودان لدينا سوف يكونان في النهاية متطابقين؛ إذ إنه إن لم يكونا كذلك، يمكننا مواصلة الأمر باتخاذ خطوة أخرى؛ وقيمتهما المتطابقة ستكون هي العدد الذي نبحث عنه.)
على سبيل المثال، لإيجاد العامل المشترك الأعظم للعددين و ، فإن عملية الطرح الأولى سوف تعطينا ؛ لذا فإن الزوج الجديد سيكون و . ونظرًا لأن ، فإن الزوج الثالث يصبح و ، وعندما نواصل الطرح، ستكون القائمة الكاملة لأزواج الأعداد هي:
ومن ثم فإن العامل المشترك الأعظم للعددين و هو .
من الممكن كتابة العامل المشترك الأعظم لزوج من الأعداد، من تحليل العددين لعواملهما الأولية. في هذا المثال، ، بينما ؛ وبأخذ القوة المشتركة لكل عدد أولي داخل في عملية التحليل، نحصل على العامل المشترك الأعظم . مع ذلك، الأعداد الكبيرة تتطلب جهدًا أقل في استخدام خوارزمية إقليدس؛ إذ إن إجراء عمليات الطرح أسهل عمومًا من التحليل للعوامل الأولية.
توجد ميزة أخرى لخوارزمية إقليدس؛ وهي أنه من الممكن دائمًا العمل على نحو معاكس، ومن ثم التعبير عن العامل المشترك الأعظم في سياق العددين الأصليين. ولرؤية تطبيق ذلك على الواقع في المثال السابق، من الأفضل ضغط الحسابات عندما يظهر العدد نفسه عدة مرات على مدار عملية الطرح، ويمثَّل هذا في معادلة واحدة كما يلي:
بدءًا من السطر الثاني حتى السطر الأخير، نستخدم الآن كل معادلة صغيرة للتخلص من البواقي الوسيطة، واحدًا تلو الآخر. وفي هذا المثال، عن طريق استخدام المعادلة قبل الأخيرة أولًا، ثم المعادلة السابقة لها، نحصل على:
وفي النهاية نستخدم المعادلة الأولى للتخلص من الباقي الوسيط الأول :
إن القدرة على إجراء هذه العملية العكسية مهمة لأسباب تطبيقية ونظرية. وعلى نحو خاص، لإيجاد عدد فك الشفرة لأليس، نريد أن يفي بشرط أن يترك باقيًا يساوي عند القسمة على . (من أجل الاختصار، سوف نشير إلى برمز واحد هو .) نستطيع الآن إدراك السبب في إصرارنا على أن يكون و عددين أوليَّين فيما بينهما — كما لو كان العامل المشترك الأعظم لهما هو — فعندما نطبق خوارزمية إقليدس على زوج الأعداد و ، فإن الباقي المتناهي الذي يظهر هو بالطبع. وعن طريق عكس الخوارزمية، سوف نعبِّر في النهاية عن بصفته مزيجًا من و ، وبصفة خاصة سوف نجد أعدادًا صحيحة مثل و ؛ حيث أو بعبارة أخرى، ؛ ومن ثم فإن