Lecture_8___Public_Key_Cryptography
مساء الخير يا شباب، إيه الأخبار؟ النهاردة هنشرح Lecture 8، هنتكلم فيها عن الـ Public Key Cryptography، اتكلمنا المحاضرات اللي فاتت عن الـ Encryption والأنواع المختلفة من الـ Encryption وأخدنا فيه نوعين إن في نوع Symmetric ونوع Asymmetric، وقلنا إن كل واحد ليه استخداماته. طيب النهاردة هنتكلم باستفاضة على الـ Public Key Cryptography أو زي ما هنقول الـ Asymmetric Encryption. خلينا نبدأ.
أول حاجة نيجي للمسمى، هو بيقولوا عليه Public Key Encryption، أو بيقولوا عليه Public و Private، أو بيقولوا عليه Asymmetric Encryption، كل دي مسميات للـ Public Key Encryption. ماشي، طيب ليه بنقول عليه Public و Private؟ لأن زي ما قلتلك إن إنت في الـ Encryption process اللي حاصلة بيبقى عندك Two Keys، زي ما كلمتك قبل كدة، قلتلك إن إنت بيبقى عندك واحد Public وواحد Private.
والـ Receiver برضه عنده الـ Public بتاعه وعنده الـ Private بتاعه. ماشي، فعشان كدة بنقول عليه Public و Private Encryption. ماشي. طيب، اتكلمنا قلنا إن الـ Symmetric Encryption Based على Substitution function Substitution function . طيب، الـ Asymmetric بقى لأ، ده بيبقى على Mathematical function Mathematical functions أكتر.
ماشي؟ ماشي. طيب، خلينا نصحح بس كام مفهوم الأول قبل ما نبتدي محاضرة النهاردة وهدردش معاك شوية عشان إيه الكلام يبقى بسيط. خلينا نتفق الأول أول لما أقولك إن أنا هـ Encyrpt Public تقولي هفك بـ Private. طيب لو هـ Encyrpt بـ Private تقولي هفك بـ Public. دي كدة Rule خليها قاعدة ثابتة في دماغك وهنعرف ليه كمان شوية. طيب خلينا نصحح بقى كام مفهوم.
أول حاجة بيقولك إن الـ Public Key Cryptography أحسن من الـ Symmetric Cryptography، الكلام ده مش صحيح. طيب ليه مش صحيح؟ كل حاجة ليها استخداماتها، وكل حاجة ليها مميزاتها وليها عيوبها. يعني مثلاً عندك في الـ Public Key Encryption عشان هو بيبقى على Mathematical functions أكتر فالعملية بتبقى بطيئة حبتين. طيب أنا دلوقتي لو أنا محتاج الـ Encryption process تبقى بتم بسرعة.
فساعتها الـ Asymmetric Encryption مش هيبقى أحسن حاجة، فبالتالي مفيش حاجة Secure أكتر من حاجة، لأ، كل حاجة ليها استخداماتها وكل حاجة ليها قوتها وليها مميزاتها وليها عيوبها. ماشي. طيب، بيقولك إن الـ Public Key Cryptography هو Technique اللي خلى الـ Symmetric Encryption يختفي، لأ، ما حصلش، ليه بقى؟ لأن إحنا لحد يومنا هذا بنستخدم Symmetric encryption algorithms برضه قوية زي الـ AES اللي اتكلمنا عنه المحاضرات اللي فاتت.
ماشي، فكل زي ما قلتلك كل حاجة ليها استخداماتها، والاتنين مستخدمين لحد دلوقتي، مش أكتر. تمام. بيقولك في آخر Point إن الـ Distribution بتاع الـ Keys في الـ Public Key أسهل من الـ Symmetric Encryption، والكلام ده برضه مش صح وهنفهم ليه كمان شوية. هنا بس هيكلمك على الـ KDC، الـ KDC اللي هو الـ Key Distribution Center.
اللي هو أصلاً بيوزع الـ Keys عندي في الـ Network وهفهمك يعني إيه كمان شوية. ماشي، خلاص عرفنا يعني إيه Public Key Encryption، واتكلمنا عاوزين نصحح بقى الكام مفهوم اللي كانوا في دماغنا، خلينا بقى نبتدي. طيب، اتعمل ليه؟ يعني إنت دلوقتي عملت ليه الـ ليه ما استكفيتش بالـ Symmetric Encryption؟
لأن إحنا كان أحد اهتماماتنا حاجتين. دلوقتي إنت في الـ Symmetric Encryption، لو إنت ده الـ Sender وده الـ Receiver، وده بعت Message عمل لها Encryption بـ Key، الـ Key ده ثابت طبعاً هنا وهنا، وده الكلام اللي جه لمثلاً اللي هو الـ Receiver B، الـ A بيبعت للـ B.
هل أنا كدة اتأكدت إن A اللي بعت الـ Message؟ لأ، ما اتأكدتش إن A بعت الـ Message. ليه؟ لأن إنت مجرد الـ Key اللي معاك هو هو اللي معاه، فإنت بس لما تبعت الـ Message ما اتأكدتش إن الشخص ده هو اللي معاه الـ Message، ممكن يكون شخص تاني واخد الـ Key أو حاجة، فما اتأكدتش إن الـ Sender هو اللي بعت الـ Message.
دي أول Point. طيب تاني Point كان في مشكلة في الـ Key ده، إن أنا أوزع الـ Key، أوزع الـ Key أو الـ Key distribution. إزاي هبدل مع الشخص التاني الـ Key بتاعي والشخص التاني هيبدل معاه الـ Key بتاعه، يعني هنتفق على Key إزاي؟ فدي كانت مشكلة، عشان كدة اتجهنا للـ Public Key Encryption.
زي ما فهمتك إن إنت بيبقى عندك Two Keys لكل واحد، Public و Private. ماشي، يبقى عرفت ليه الـ Public Key Encryption استخدمته، ليه؟ عشان الـ Key Distribution والـ Digital Signature. الـ Digital Signature اللي هو التوقيع بتاعك على الـ Message يعني في الآخر، يعني بحيث إن أنا كـ Sender أتأكد إن فعلياً الـ Sender هو اللي بعت الـ هو اللي باعت  الـ Message دي.
ماشي. طيب، Diffie-Hellman هو أول شخص أو العالمين يعني، الـ Algorithm بتاعهم هما Based على الـ Public Key Cryptography، اتعمل سنة 1976، مش مشكلتنا دلوقتي. تمام. وزي ما كلمتك من شوية إن إنت بتعمل Encryption بـ.
One Key وبتـ Decrypt بـ Key مختلف، يعني مثلاً لو هـ Encrypt بالـ Private بفك بالـ Public. ولو هـ Encrypt بالـ Public هفك بـ Private. دي خدها قاعدة ثابتة. ماشي. في حاجتين لازم يتحققوا في الـ Encryption، حاجة Mandatory وحاجة Optional. إيه الـ Mandatory؟ بيقولك It's computationally infeasible to determine the encryption key  أو sorry الـ  decryption key .
Given the encryption key. يعني إيه؟ يعني لو إنت عارف الـ Encryption key مستحيل، مستحيل إن إنت تخمن الـ Decryption key. ليه؟ لأن إنت مثلاً لو بتـ Encrypt بـ Public مستحيل تخمن الـ Private، والعكس. ماشي؟ ده حاجة Mandatory عندي في الـ Algorithm، لازم يحققها. طيب تاني حاجه بيقولك.
إن الـ Two Keys ينفع أقدر أستخدمهم في الـ Encryption والـ Decryption. يعني أنا مثلاً أقدر أستخدم الـ Private في الـ Encryption وبقدر برضه أقدر أستخدم الـ Public في الـ Encryption. والناحية التانية برضه أقدر أستخدم الـ Public وأقدر أستخدم الـ Private في الـ Decryption. دي حاجات لازم الـ Algorithm بتاعي يحققها. ماشي. طيب، خلينا نبص على الـ Rule العامة. بص، أنا ده Plain text.
ودا شخص تاني أنا عايز أبعتله، ولنفترض إن دا A ودا B. الـ Message بتاعتي بتخش على Algorithm معين Encryption Algorithm ولنفترض الـ RSA، هناخده كمان شوية. الـ RSA ده اللي هو إيه؟ Asymmetric Encryption. طيب، هتـ Encrypt بإيه؟ بـ Public. طيب، الـ Public ده من اسمه.
كل الناس عارفاه، يعني الـ Public ده مش بتاعي أنا، لأ الـ Public ده بتاع Alice. أنا دايماً بـ Encrypt بالـ Key بتاع الشخص اللي أنا لو Public يبقى بالـ Public بتاع اللي أنا رايحله. يعني مثلاً عايز أبعت Message لـ Alice وأ Encryptها بالـ Public بـ Encryptها بالـ Public بتاع Alice. مفيش مشكلة. طيب، أنا دلوقتي عملت Encryption بـ.
الـ Key ده. بعت هناك، طيب قلتلك إنت هتـ Encrypt بـ Public تفك بـ Private. طب هفك بـ Private مين؟ بتاعي أنا. بفك بالـ Private بتاعي أنا. يعني أنا هنا أنا بعت بالـ Public أو عملت Encryption بالـ Public بتاع Alice، الشخص التاني Alice. هنا هفك بالـ Private بتاع.
ماشي. طيب، لو أنا عملت Encryption بالـ Private، الـ Private Key دا بيبقى حاجة Unique، حاجة مش معروفة أو حد المفروض مستحيل تبقى متشافة لحد غير الشخص بتاعه. يعني إيه؟ يعني أنا عندي Private، الـ Private دا بتاعي أنا، حتى الشخص التاني ما يعرفش الـ Private بتاعي، أنا بس اللي أبقى عارف الـ Private Key ده.
يعني الـ Private بتاعي بيبقى عندي أنا بس. طيب لو أنا هـ Encrypt بقى بالـ Private اللي هو بتاعي أنا خلاص مش مشكلة، هـ Encrypt بالـ Private اللي هو بتاعي كمثلاً اسمي مثلاً أحمد، هفك هناك إزاي؟ هفك هناك بالـ Public، طب الـ Public بتاع مين؟ بتاع أحمد. تمام، خلاص فهمنا الكلام .
طيب خلينا نتناقش بقى في كام حاجة، أنا دلوقتي عملت Encryption بالـ Key بتاع Alice، ماشي؟ وبعتها لـ Alice، Alice تمام عرف يعمل لها Decryption وكل حاجة. طيب هل أنا كدة اتأكدت إن الشخص ده هو اللي باعت الـ Message؟ يعني هل لو هنا أحمد هل كدة أنا اتأكدت إن أحمد هو اللي باعت الـ Message؟ هتقولي لأ، تقولي ليه.
لو أنا مثلا إحنا عارفين إن الـ Key Public يعني أي حد عارفه، يعني مثلاً لو هنا شخص تالت اسمه علي، معاه الـ Key طبعاً بتاع Alice، طب ما أنا لو عملتلك Encryption بالـ Key بتاعك اللي هو الـ Key الـ Public بتاعك كـ Alice إنت بس مجرد هتاخد الـ Message تعمل لها Decrypt.
طب هل إنت كدة اتأكدت الـ Message جالك من أحمد؟ لأ ما حصلش، مفيش حاجة قالتلي إن الـ Message دي فعلياً جاية من أحمد. ليه؟ لأن أنا فكيت بالـ Private بتاعي، والـ Message جالي بالـ Public، طب ما أي حد ده معاه الـ Public. طيب يبقى أنا هنا حققت إيه؟ أنا هنا طالما عملت ما فكتش مفيش شخص تاني عرف يفك الـ Message دي غيري أنا، لأن أنا الوحيد اللي عارف الـ Private بتاعي أنا.
يبقى أنا كدة حققت Confidentiality، تمام؟ تمام، طب أنا هل كدة حققت Authentication أو حققت إن الـ Message أو Authenticate الراجل اللي باعت الـ Message؟ لأ، ما حققتش الكلام ده، يبقى الشكل ده ما حققش الكلام ده. طيب، هو بيقولك أهو هنا لو إنت مثلاً أدي الـ Message بعت دخلتها على Encryption Algorithm، هنا.
الشخص أو الـ Key Distribution Center هو اللي بيوزع الـ Keys، يعني هو اللي بيوزع بيدي ده الـ Public ويدي ده الـ Private، وهكذا. طيب إنت عايز تعمل إيه؟ هـت Encrypt بالـ Public خلاص مفيش مشكلة، أنا عايز أبعت للشخص اللي هو B هـ Encrypt بالـ Public بتاعه، بعت الـ Message هناك المفروض ده يبقى معاه الـ Private بتاعه هو، الـ Private بتاعه هو، هو اللي يقدر يـ Decrypt بيه.
ماشي، هل بقى لو جيه شخص في النص اللي هو الـ Crypt-analyst خد الـ Message دي هيعرف يفكها؟ لأ مش هيعرف يفكها. طيب المشكلة فين؟ المشكلة اللي تحصل لو هو بعتلي Message لأن هو معاه الـ Public بتاعي أنا كـ Destination B. تمام، الكلام ده مفهوم لحد دلوقتي. طيب لو أنا دلوقتي عاوز أ Authenticate الشخص.
عاوز أ Authenticate إن مثلاً لو هنا أحمد، أ Authenticate إن أحمد هو اللي باعت الـ Message. طيب أعملها إزاي؟ هتقولي هـ Encrypt بالـ Private بتاع أحمد. ليه؟ لأن إنت هتفك بـ Public هناك، طب الـ Public بتاع مين؟ بتاع أحمد. طالما إنت قدرت تفك بالـ Public بتاع أحمد يبقى فعلياً الـ Message جاية من أحمد.
صح؟ لأن مفيش حد معاه الـ Private key غير أحمد بس، ده بيبقى حاجة Secure، حاجة مينفعش حد غير أحمد يبقى شايفها. تمام، فعشان كدة إنت تأكدت إن الـ Message فعلياً جاية من أحمد. طب سؤال، هل بقى إنت كدة حققت Confidentiality؟ يعني مثلاً.
لو أنا واقف في النص هنا، طب ما هو أنا عارف الـ Public بتاع أحمد، هنا أحمد صح؟ أنا عارف الـ Public بتاع أحمد. خلاص أنا مجرد الـ Message دي هاخدها كدة Copy عندي وأفكها بالـ Public بتاع أحمد، يبقى أنا كدة ما حققتش Confidentiality ولكن حققت Authentication. طيب ما أنا مش عايز أحقق الكلام ده أنا عايز أحقق الاتنين مع بعض.
هنحققهم، بس خلينا نفهم برضه الكلام هنا، هنا برضه في Key Distribution Center أو شخص تاني بيوزع الـ Keys بيدي ده الـ Public وبيدي ده الـ Private. أنا مثلاً هـ Encrypt بالـ Private بتاعي يبقى هفك هناك بالـ Public، Public بتاع مين؟ بتاع الشخص اللي بعت، يبقى الـ Public بتاع هو هنا A يبقي A.
طيب قلنا الكلام ده مافيهوش Confidentiality، لأنه لو جه راجل في النص هو أصلاً يقدر يجيب الـ Public Key ده، وطالما الـ Public Key معاه هيقدر يفك الـ Message بكل سهولة. ماشي. طب إحنا دلوقتي عاوزين نحقق الحاجتين، عاوز أشوف إن أحمد أو الـ Source اللي هو A هو اللي بعت الـ Message ومحدش غيري.
يقدر يفك الـ Message، وحتى لو جه شخص في النص ماحدش يقدر يفك أي Message من المبعوتة ما بينا. طب هنعمل إيه؟ اللي بيحصل ايه كالاتي، إن أنا أدي الـ Message الأصلية بتاعتي بتخش على Encryption Algorithm، بعمل لها Encryption بالـ Private بتاعي، بالـ Private بتاع A. طيب ليه عملت الحركة دي؟ عشان هناك أقدر أفك بالـ Public وأتأكد إن أحمد أو الـ Source A هو اللي باعت، صح؟
دي الحاجة الوحيدة. ماشي. طيب طالما الـ Private وفك. طالما أنا قدرت أفك  الـ Public بتاعه يبقى أنا اتأكدت الـ Message جاية منه هو. طيب أنا عايز أحقق بقى Confidentiality، يبقى هـ Encrypt بالـ Public بتاع الشخص اللي أنا رايحله، هـ Encrypt بالـ Public بتاع الشخص اللي أنا رايحله. طب أنا عملت Encrypt بالـ Public اللي أنا رايحله
الشخص اللي هناك لما يجي يفك هيفك بمين؟ بالـ Private بتاع مين؟ بتاعه هو اللي هو B. طيب يعني معنى كدة إن مفيش شخص تاني هيقدر يفك الـ Message دي في النص. يبقى أنا كدة حققت Confidentiality. يبقى أنا عن طريق إن أنا عملت مرة Encrypt بالـ Private وبعد كدة عملت Encrypt مرة كمان بالـ Public.
قدرت أحقق Confidentiality وأ Authenticate إن الشخص التاني هو اللي بعتلي الكلام ده، ماشي؟ طيب هنا برضه الـ Key Distribution Center هو اللي بيوزع الـ Keys، يعني بيدي الـ Key ده بتاعه، ده بيدي بيقول إن ده الـ Private بتاعك إنت، ويروح يدي الراجل اللي هناك الـ Public بتاعه هو بحيث لو حب يفك.طيب و ادي الـ Key Distribution Center اللي هناك الـ العند الـ Receiver.
بيوزع يقوله خد إنت الـ Private بتاعك وأنا هدي اللي هناك الراجل اللي هناك الـ Public Key. ماشي، طيب يبقى أنا كدة حققت Confidentiality وحققت عملت Authentication. ماشي، الكلام هنا مفهوم. طب تعال كدة مش عاوزين نحفظ حاجة، عاوزين نستنتج الكلام كدة مع بعض الـ Symmetric والـ Asymmetric، عاوزين نعمل كدة Comparison كدة سريع.
في أي Encryption قلتلك اللي حاصل إن نفس الـ Algorithm اللي أنا بستخدمه هنا هو هو الـ Algorithm اللي أنا بستخدمه هنا. يبقى دي حاجة ثابتة. طيب، الفكرة فين؟ إن ده عنده Key واحد في الـ Symmetric Encryption ده عنده Key واحد، وفي الـ Asymmetric ده عنده Two Keys، واحد Public وواحد Private.
طيب، وبيستخدم واحد من الـ Two Keys دول للـ Encryption وواحد تاني مختلف للـ Decryption. ده اللي إحنا متفقين عليه. ماشي، بيقولك إن الـ Parties هنا بيـ Share Algorithm and Key في الـ Symmetric، إحنا قلنا آه بنـ Share الـ Algorithm وبنـ Share نفس الـ Key. طب هناك في الـ Asymmetric، إحنا آه بنـ Share الـ Algorithm.
بس كل واحد عنده الـ Key اللي هيـ Encrypt بيه، وكل واحد عنده الـ Pair من الـ Keys بتوعه هو. ماشي. طب هنا إحنا مبنستخدمش غير Key واحد صح؟ وقلنا إن الـ Key ده مهم يبقى أخزنه بشكل Secure. يبقى الـ Key ده Must kept secret. طيب هنا إحنا بنستخدم اتنين، واحد Public .
واحد private، طيب مين الفي دول لازم يبقى secure؟ الـ private، لازم يبقى secure محدش طرف تاني يعرف يعمله، يستنتجه أو يعرف يجيبه أو يسرقه تحت أي ظرف ما. طيب الـ public كدة كدة معروف للكل، يبقى أنا بس اللي كل يهمني الـ private اللي هو يبقى keep secret. طيب و قولتلك مميزات أي algorithm في الدنيا، أي encryption algorithm أنت هتستخدمه لازم الـ cipher اللي طالع يبقى strong cipher، ميبقاش cipher أقدر أعمله cipher، analysis
في مثلاً patterns بتتكرر أقدر أعمل منها analysis للـ cipher، لازم الـ cipher اللي خارج من أي encryption algorithm إذا كان symmetric أو asymmetric لازم يبقى strong cipher، يبقى strong cipher هنا أو هنا مش هيفرق معايا. وكمان الـ plain text اللي طالع مأقدرش من خلاله أستنتج منه الـ key، إذا كان هنا أو إذا كان هنا.
في الـ symmetric والـ asymmetric، يبقى إحنا كدة عملنا كدة comparison سريعة ما بين الـ two algorithms، ماشي؟ ماشي. طيب هو هنا بيكلمك إن الـ function لازم تبقى one way function، يعني أنت مثلاً y دي عبارة عن إيه؟ y دي عبارة عن function حاصلة على الـ x عشان أستنتج الـ cipher، طيب والمفروض يبقى العكس
infeasible، صح؟ صح. طيب يبقى أنت المفروض لو أنت معاك الـ key ومعاك الـ x أو الـ plain text أقدر أعمل encryption بكل سهولة، لازم الـ function بتاعتي تعمل encryption بكل سلاسة، وفي الـ decryption لازم يحصل نفس الكلام، يعني عشان أجيب x هعمل الـ inverse للـ function اللي أنا عملتها فوق على الـ y بالـ key، لازم يبقى معايا الـ key.
طب لو أنا مش معايا الـ key، هل أقدر أعمل decryption؟ لأ الكلام ده يبقى infeasible، الكلام لحد هنا مفهوم وبسيط جداً مافهوش أي مشكلة. نيجي بقى لأول algorithm، أول algorithm ظهر بعد Diffie-Hellman كان بـ implement الكلام بتاعه، هو بس RSA اختصاراً يعني للتلات علماء اللي عملوه مع بعض. طيب خلينا نتفق على حاجة، هو الـ cipher أو الـ encryption بيبقى حاصل إزاي؟ بيقولك
أنا الـ cipher بتاعي إحنا قولنا معتمد على mathematical function. طيب الـ mathematical function دي إيه هي؟ بيقولك عشان أقدر أجيب الـ cipher أنا هاخد الـ message دي، هحولها لـ binary، يعني الـ m دي binary، أرفعها power e وأخدها mod n أطلع بالـ cipher. ماشي، طيب الـ e دي
هنعرف العلاقة بتاعتها بالـ n كمان شوية. طيب الناحية التانية عشان أوصل لل message الأصلية، هاخد الـ cipher بتاعي، هرفعه لـ power معين، الـ power ده لما أخودله mod n يرجعلى الـ m الـ message الأصلية. طيب ما ممكن نستعيض عن الـ c اللي هي دي
بالخطوة اللي فوق، الـ c دي كانت عبارة عن m power e mod n، خلاص حط m power e mod n واضربها في الـ d يبقى m power ed mod n. ماشي، طيب الـ public ده بيبقى عبارة عن إيه؟ إحنا قولنا الـ RSA ده معتمد على أو هو نوعه إيه؟ نوعه asymmetric algorithm. طيب هو لازم يبقى عنده private ولازم يبقى عنده public، طيب الـ private ده هو إيه؟ أو الـ public ده إيه بقى
الـ public هو الـ e والـ n مع بعض وهنشوف العلاقة ما بينهم كمان شوية، يبقى الـ e دي والـ n ده الـ public. طيب الـ private بقى بتاع الشخص نفسه ده الـ d والـ n وبردو هنشوف العلاقة كمان شوية، يبقى لازم يبقى في public ولازم يبقى في private.
ماشي، فهو بيقولك إن الـ plain text بيتقسم blocks، الـ blocks دي بتتحول لـ binary value، الـ value دي لازم تبقى أقل من n، متنساش، لازم تبقى أقل من n عشان كدة كدة باخد mod، فلازم الـ value دي تبقى أقل من n. ماشي، لحد هنا الكلام مفهوم. طب إيه الـ requirements بقى اللي تحققلي الكلام ده؟ لازم يبقى في عندي شوية rules هنتفق عليها.
لازم ال E دي وال D وال N اللي مستخدمة هنا وهنا such that إن m power ed، احنا قلنا إن m power ed اللي هي كانت ال message الأصلية صح؟ فهي هتساوي نفس الكلام أو congruent modulo ل m mod n لكل ال values بتاعت m اللي أقل من مين؟ اللي أقل من n.
تمام؟ واحنا قلنا إن أنا ال encryption لازم يتم بسلاسة وال decryption لازم يتم بسلاسة في حالة إن انت معاك ال private وال public، ماشي، فهو بيقولك لازم يبقى relatively easy to compute m power e يعني أنت في مرحلة ال encryption طيب و تاخدلها mod n طبعًا ، وال c power d mod n ده في حالة ال decryption، ويقولك كمان infeasible to determine d يعني مينفعش أوصل ل d حتى لو معايا e و n، الكلام ده يبقى infeas.
ماشي سيبك من الكلام النظري ده خلينا نبص على ال algorithm شغال إزاي أو ال steps بتاعة ال algorithm، إحنا قلنا إن في ال cipher بيبقى عندي message برفعها ل power e واخدلها mod n صح؟ صح، طب أنا عاوز إيه؟ عاوز n دي وعاوز e دي، ماشي طيب ال steps بقى.
ال steps بيقولك أنت اختار p و q random، طيب ال p و q دول أي رقمين في الدنيا؟ لأ لازم يبقوا large prime numbers، ليه large؟ أول large لأن محدش عشان الحسبه او محدش يقدر يعمل brute force attack، طيب ليه prime؟ قلنا prime لأن مبقدرش أ detect patterns في ال prime numbers، الكلام نفتكره من ال number theory.
تمام خدت p و q، احسب n، n دي كانت عبارة عن إيه؟ n دي كانت عبارة عن p في q، بعد كدا احسب phi n، phi n لو تفتكر بقى دي p يبقى p minus 1 لأن n دي كانت عبارة عن p في q، فأنا بحسب phi n للأولانية اللي هي p يبقى p minus 1، وبحسب phi n للتانية يبقى q minus 1.
حسبت كدا مين؟ حسبت phi n، هنعرف ليه كمان شوية، ماشي، بيقولك بقى select بقى integer e، إحنا بنعمل الحركات دي كلها عشان أوصل ل public و private لأن إحنا عارفين إن ال public هو e و n وال private هو d و n، ماشي كمل بقى، هن select integer e، يبقى ولازم يبقى relatively prime مع الخطوة اللي قبلك يعني phi n اللي طلعت دي.
لازم تبقى relatively prime مع ال e، ماشي، ولازم ال e تبقى أصغر من ال phi n دي، يبقى لازم شرطين ال e تبقى أقل من phi n وكمان relatively prime معاها، طيب هحسب d، d تتحسب إزاي d دي؟ d عبارة عن حسبة ال e اللي أنا أخدتها من الخطوة اللي قبلي اوس سالب 1.
وخدها mod phi n، أنا كدا معايا d ومعايا e ومعايا n، أنا كدا خلاص معايا ال private ومعايا ال public، ماشي وأقدر استخدم في ال decryption وال encryption، تعالى ناخد مثال عملي عشان يوضح الفكرة، طيب أول حاجة احنا قلنا هناخد ايه هناخد p و q، هن select p و q، خطوات سريعة سريعة.
بس طبعًا الأرقام دي صغيرة بس توضيحًا للمثال مش أكتر، p و q دول لازم يبقوا large prime numbers، خدت مثلا ال 17 وال 11 كدا أنا بقى معايا p و q، عايز أحسب n، n دي عبارة عن ايه ، n عبارة عن حاصل الضرب بتاع p و q فإدتني 187، طيب أنا كدا بقى معايا n، احسب phi n بعد كدا، خطوات سلسة متقلقش.
طيب phi n دي عبارة عن إيه؟ يعني كأني بقول phi ل p في phi q، طيب phi p يبقى p minus 1 p minus 1، ال p كانت بكام ب 17 يبقى 16، طيب وال q minus 1 الهى 11 يبقى 10، ضربتهم في بعض، طيب بعد كدا المفروض هاخد رقم اللي هو e، هـ select رقم كدا.
لازم يبقى relatively prime مع phi n ولازم يكون أقل من phi n، ولنفترض مثلا في ال case دي هاخد 7، ماشي، وبردو لازم ال e كل الأرقام اللي أنا بستخدمها دي تبقى large prime numbers، مننساش. طيب ال e اخترتها ب 7، حسبت e، طيب أنت تفتكر عايزين نحسب مين؟ عايزين نحسب d.
اللي هي كانت عبارة عن e اوس سالب واحد وتاخدلها mod phi n اللي أنت طلعتها، phi n اللي كانت phi 160. طيب ومعنى كلمة e اوس سالب واحد أنت شغال under modular arithmetic، يعني أنت عاوز تجيب ال inverse لل e، عاوز تجيب ال inverse لل e، تمام طيب يبقى.
كأني بقول ال d في ال e الكلام ده بيساوي 1 mod 160 ، ماشي، طيب إيه الرقم اللي أضربه في ال e يطلعلي وأخده mod phi n يطلعلي يطلعلي 1؟
لما جربنا لقينا لما هضرب ال 7 دي اللي هي ال e في ال inverse اللي هو 23 وأخدتها mod phi n إدتني 1، ممكن بقى تعملها extended Euclidean algorithm براحتك، تمام بس إحنا هنقولهم سريعًا هنا يعني مش هنخش في التفاصيل دي أوي، يبقى أنا كدا حسبت d، خلاص يبقى ال public بتاعي.
هو ال 7 وال 187، مين ال 7؟ ال 7 اللي هو ال e، مين ال 187؟ اللي هو كان ال n. طيب ومين ال private؟ ال private هو ال 23، مين ال 23؟ دي ال d اللي أنا حسبتها من الخطوة اللي قبلي، ومين ال 187؟ ده ال n. تعال نبص بقى إيه اللي هيتم.
أنا دلوقتي عندي ال plaintext اللي هو 88، المفروض الكلام ده بيتحول ل binary بقى، طيب هناخد بقى ال 88 دي أرفعها power e، متنساش الشكل m power e هاخده mod n يطلعلي ال cipher. طيب ال m أهي ب 88، هرفعها power e، power e اللي هي كانت ب 7 وأخدها mod n يبقى mod 187.
هيطلعلي مين؟ هيطلعلي ال 11، متنساش إن هنا ده ال public هو دول مع بعض. ماشي طب أنت كدا عملت إيه بردو من الآخر؟ أنا عملت encrypt بال public، عايز أفك هناك بال private، هعمل إيه؟ هاخد ال cipher اللي طلع اللي هو كان ال 11، خدت ال 11 هرفعه لمين؟ ل power d، مين كان d؟ ال 23، يبقى 23.
mod n ال n كانت بكام ب 187، لازم لازم لازم ال plaintext اللي يطلع هو هو ال plaintext اللي يطلع هنا. هنقولهم سريعًا سريعًا، أول خطوة بختار large prime numbers أو large two prime numbers ال p وال q، تاني خطوة بحسب n اللي هو حاصل ضربهم، تالت خطوة احسب phi m.
اللي هو حاصل p minus 1 في q minus 1، بعد كدا ب select e اللي هي relatively prime مع اللي قبلها وتكون أقل منها. بعد كدا بحسب d اللي هو d تتحسب إزاي؟ اللي هو e inverse، يعني أنا عايز أحسب ال inverse بتاع ال e. طيب هحسبها إزاي؟ احسبها بال extended Euclidean تحسبها بالطريقة اللي قولتهالك براحتك. حسبت ال d خلاص أنت كدا بقى معاك public و private، تقدر ت encrypt بال public وتفك بال private أو.
العكس. ماشي، الكلام اللي إحنا قولناه ده معرض ل attacks؟ أه بتحصل attacks على ال algorithm ده. طيب أول حاجة ال brute force attack، دايمًا أي algorithm معرض لل brute force attack، بحاول أجرب كل ال combinations على ال algorithm ده. طيب إيه اللي بيحصل؟ الراجل ب try all private keys، ب try كل ال possible private key.
وبيستخدم large keys علشان أنا أحاول أتجنب ال brute force attack ده، يبقى تاني إيه اللي بيحصل؟ brute force attack يعني أنت بتجرب كل ال combinations، أتجنبه إزاي؟ استخدم large keys يا معلم. لو استخدمت large keys فأنت كل شوية بتجرب sorry بتكبر ال keyspace اللي الراجل بيدور فيه، فهيقعد يجرب سنين عشان يفك ال algorithm.
طيب mathematical attacks، دي بتبقى حاصلة على بيحاول يلعب يعني بيحاول يلاقي ثغرة في ال process اللي إحنا عملناها فوق دي يحاول من خلالها يحاول يعمل factorizing للأرقام اللي فوق دي، يحاول يعمل factorizing بحيث يوصل ل ال plaintext الأصلي. chosen ciphertext attacks، فالراجل بيعمل إيه يعني؟ الراجل بيحاول يعني معاه ciphertext.
بيختار من ال ciphertext ده أجزاء يحاول يوصل لل plaintext الأصلي. ماشي، طب إيه كمان؟ طيب فوق إحنا قولنا ال steps اختار p و q واحسب n واحسب phi n والكلام ده، كل خطوة من دول معرضة إن هي يحصل لها attack، يعني في أول خطوة الراجل بيحاول ي factorize n دي لأن إحنا قلنا n ده عبارة عن حاصل ضرب p في q.
يحاول ي factorize n دي يجرب كل ال values، يجرب كل ال values. طيب ليه يعمل الحركة دي؟ علشان يحاول يحسب phi n، يحاول يحسب phi n. طيب وهو بيحسب ليه phi n؟ علشان يحاول يكمل بقية ال steps اللي إحنا عملناها فوق، يعني إحنا وصلنا لفين؟ وصلنا هنا phi n، phi n تمام؟ تمام. يبقى يقدر يحاول يكمل ال steps بحيث إنه يقدر يوصل ل.
أو ي break ال algorithm. طيب تاني خطوة، هو يحدد phi n على طول، أنا مش هعمل factorizing للكلام ده، أنا معايا n، هحسب phi n على طول. هو بقى يحسب phi n من خلال إن n دي عبارة عن p في q ويحاول يشتغلها بحيث إنه ي inverse العملية. ماشي، طيب الخطوة الأخيرة أو الخطوة التالتة إن هو يحسب d.
يحسب يخش على d direct كدا يحاول يحسبها. d دي كانت عبارة عن إيه؟ عبارة عن e اوس سالب واحد mod phi n، صح؟ صح. طيب الراجل يحاول يحسب دي كلها على بعضها، يحاول يحسبها كدا يقعد يجرب في ال e ويجرب في ال phi n لحد ما يحاول يوصل لمين؟ يحاول يوصل لل d.
طيب آخر حاجة بيقولك factoring from the decryption exponent، يعني ال message اللي طلعت في الآخر اللي هي هنا، يعني هنا أنا لو ال private key بتاعي اللي أنا مستخدمه يعني أو ال d اللي أنا حسبتها كانت ضعيفة بشكل ما، الراجل يقدر ي recover ساعتها n ويحاول يقدر ي break ال algorithm ده.
عشان السبب إيه؟ إن أنا مستخدم d، أو فقلنا إن d هي اللي مستخدمة مع ال n، فبالتالي d دي ضعيفة أو واخدها small مثلا، كان ال size بتاعها صغير ما كانتش مثلا مناسبة لل algorithm بتاعي، فساعتها الراجل بيحاول يستنتج n من الكلام ده، التفصيل دي مش علينا بس توضيحًا بس للمعلومة.