Lecture_8____Random_Bit_Generation
مساء الخير يا شباب، إيه الأخبار؟ النهاردة هنشرح Lecture 8، هنتكلم فيها عن الـ Random Bit Generation. خلينا نبدأ. طيب، أول حاجة إيه هو الـ Random Numbers، أو بستخدمه في إيه؟ الـ Random Numbers من اسمه رقم عشوائي، يعني بيبقى رقم طويل كده، عشوائي، مش قادر أحفظه، مش قادر أعمله Predict. طيب، بستخدم في إيه الـ Random Numbers؟ الـ Random Numbers عندنا في علم الـ Cryptography بستغله في كذا.
حاجة في الـ Key Distribution. زي ما فهمتك قبل كده إن أنت عندك في الـ Symmetric Encryption إن هنا أنتم بتبقوا متفقين على Key، بعيداً إزاي الـ Key ده بدلتوه مع بعض، دي مش قصتنا دلوقتي. الـ Key ده اللي احنا اتفقنا عليه، مين هيعمله Generation؟ أو الـ Key بتاعك ده مش اتفقنا إنه لازم يبقى Key طويل، Key ما حدش قادر يعمله Predict؟ صح؟ أنا بستغل بقى الـ Random Numbers في حتة إن أنا أ Generate أو.
أعمل الـ Key اللي ما بين الـ Sender والـ Receiver. ماشي، تاني حاجة ممكن أستخدمها فيها في حتة الـ Session Key Generation. مش هنخش في تفاصيل أوي بس خلينا ناخد Overview كده. لو أنت ده الـ Server عندك وده الـ PC بتاعك، أنت بتحاول تـ Communicate مع الـ Server، الـ Server عشان يتأكد إن الـ Session دي بتاعتك فبيبعتلك حاجة اسمها الـ Session
ID. الـ Session ID بتبقى حاجة خاصة بيك أنت. طيب، الـ Session ID ده لازم يبقى حاجة ما حدش ييجي في النص يقدر يعملها Predict، بحيث إنه لو جه طرف تاني عايز يعمل Communicate مع الـ Server ما يعملش Communicate على أساس إنه أنا، عشان كدة الـ Session ID ده بتبقى حاجة Unique، فبالتالي لازم الـ Session ID ده يبقى Unpredictable أو يبقى حاجة Random.
متفقين عليها الـ Server والـ PC بتاعي. ماشي. طيب، تالت حاجة بستخدمه في حتة الـ RSA Public Key Encryption. مش هنخش في تفاصيل أوي بس كل اللي محتاجك تعرفه إن الـ RSA بيبقى معتمد على Mathematical Functions، والـ Mathematical Functions دي عشان أ Generate الـ Key الـ Keys الـSender
والـ Receiver، كل واحد بيبقى عنده الـ Public والـ Private، وده بيبقى عنده الـ Public والـ Private. فأنا بستغل الـ Random Numbers في حتة إن أنا أ Generate Public Key و Private Key، الطرفين دول يقدروا يستخدموهم في الـ Encryption والـ Decryption. ماشي. طيب، رابع حاجة ممكن أستخدمه فيها رابع حاجة إن أنا أ Generate Bit Stream، ودي اللي هناخدها في محاضرة النهاردة.
ماشي، طيب عشان أقول على رقم إنه Random لازم يكون بيحقق حاجتين Randomness و Randomness . Unpredictable من اسمها إن الرقم يبقى عشوائي، طيب و Unpredictable؟ إن أنا مش هقدر أعمل Predict للرقم اللي بعد كده حتى لو أنا معايا الرقم الـ Random ده، صح كده؟ صح كده. طيب، الـ Randomness لازم أبقى محقق خاصيتين حاجة اسمها Uniform Distribution
يعني عدد الـ Zeros والـ Ones في الرقم يكاد يكون متشابه، يعني Probability نص، يعني عدد الـ Zeros وعدد الـ Ones يكونوا نص، يعني ما يبقاش Biased لحاجة، يعني ما يبقاش الـ Ones بتظهر أكتر أو ما يبقاش الـ Zeros بتظهر أكتر. طيب، حاجة تانية الـ Independence، يعني إيه Independence؟ يعني الـ Output
أو الـ Sequence اللي بعد كده غير معتمد على اللي قبله، يعني لو أنا مثلاً عندي 0 1 1 0 0 الرقم اللي بعد كده يبقى Independent عن اللي قبله، يعني ماليش دعوة، أنا ماليش دعوة باللي قبلي، أنا بس بـ Generate الرقم ده، ولو أنا معايا الـ Sequence ده كله على بعضه لازم يبقى Independent عن الرقم اللي بعد كده، يعني مثلاً هنا أنا بـ Generate رقم كمان
الرقم اللي جاي ده يبقى Independent عن اللي قبله مالوش دعوة باللي قبله. ماشي. طيب، Unpredictability جاية من اسمها، إنه يبقى Unpredictable، إن أنا ما أقدرش أـPredict الـ Next value في الـ Sequence، يعني مثلاً هنا 0 0 1 0 ما أقدرش أ Predict الرقم اللي جاي ده هيبقى 1 ولا هيبقى 0. ماشي، عشان نقدر نقول على
الرقم ده number لازم يكون محققلي الخاصيتين دول. ماشي. طيب، الـ Random Bit Generator ده ممكن يبقى Device، يعني ممكن يبقى Hardware، أو ممكن يبقى Algorithm، يعني ممكن يبقى Software. لازم الـ Output من في الحالتين دول لازم يبقى Independent، وعرفنا يعني إيه Independent، و Unbiased. Unbiased يعني ما يبقاش في عدد الـ Ones أكتر من الـ Zeros أو العكس.
ماشي، يبقى تاني الـ Random Bit Generator لازم يكون بيحقق حاجتين إنه هو Independent و Unbiased، والـ Generator ده ممكن يبقى Device أو Algorithm عندي. ماشي. طيب، يبقى إحنا بنمشي على Two Strategies. إيه الـ Two Strategies دول؟ حاجة اسمها الـ True Random Number Generator، والتاني اسمه Pseudo-random Number Generator. طيب إيه ده وإيه ده؟
ده، هنمسك أول نوع اللي هو الـ True Random Number Generator ده، بيبقى معتمد على Physical Source. معتمد على Physical Source، يعني إيه Physical Source؟ يعني مثلاً بيستغل حتة الـ Sound اللي طالعة مثلاً من Microphone وبيبقى فيه Converter، يعني هنا دي الـ Sound  الـ Sound waves دي، بياخدها بيبقى فيه هنا Converter، الـ Converter ده بيحول الحاجات دي لـ Binary
فالـ Output بيبقى Binary كده، أيًا يكن الـ Values اللي هتطلع. فالـ True Random Number Generator قلنا ده بيبقى معتمد على Physical Source وبيبقى بيحقق خاصية حاجة اسمها Non-deterministic. يعني إيه Non-deterministic؟ يعني أنا ما بقدرش أحدد الـ Value اللي بعد كدة، يعني لو جيت خدت أنا كـ Converter أهو، خدت برضه Sound waves
مش هقدر أ Predict الـ Value اللي هنا، برضه صعب، موضوع الـ Prediction ده بيبقى ما بيحصلش في حتة الـ True Random Number Generator. أكيد استنتجت إن هو آه بيبقى Secure وكل حاجة بس بيبقى صعب في إن أنا أعمله Implement، لأن أنت طبعاً محتاج Physical Source ومحتاج Converter ومحتاج تحول الكلام ده يبقى Binary value.
وطبعاً الـ Values اللي طالعة دي أنت محتاج إن هي تبقى Independent و Unbiased في نفس الوقت، فالموضوع بيبقى صعب حبتين، هنخش في التفصيل كمان شوية. طيب، والـ Pseudo-random Number Generator؟ ده بيبقى زي Algorithm كدة، الـ Algorithm ده هو اللي بيعملك Generation للـ Values اللي بتبقى طالعة. طيب ده بيبقى إيه؟ بيبقى Deterministic، ساعات إن أنا بقدر أحدد الـ Values اللي طالعة من الـ Algorithm ده.
طيب عشان كدة بنستغل الـ True Random Number Generator مع الـ Pseudo-random Number Generator عشان نعمل حاجة أو Combine ما بين الاتنين في إننا نـ Generate Random Numbers، وهنعرف إن في حاجة اسمها الـ Seed كمان شوية هناخدها بالتفصيل. ماشي خلاص عرفنا إن الـ Random Number Generators بنستخدم Two Strategies، اللي هي الـ True Random Number Generator والـ Pseudo-random Number Generator، قلنا الـ True Random Number Generator ده ممكن يبقى Hardware-based أو Software-based و
هناخدهم دلوقتي. طيب، والـ Pseudo-random Number Generator ده بيبقى Algorithm هو اللي بيقدر يعمل Generation للـ Random Numbers دول، وهناخد كمان شوية إن أنا ممكن أستغل من المحاضرة اللي فاتت بقى إن أنا أستغل حتة الـ Block Cipher Modes اللي هي الـ Output Feedback Mode والـ Counter Mode
في إن أنا أقدر أعمل Generation لـ Random Numbers. ماشي خلينا نمسك أول نوع اللي هو الـ True Random Number Generator، قلنا إنه بيبقى معتمد على Physical Source. طيب، احنا قلنا إنه ممكن يبقى Hardware-based، Hardware-based يعني زي ما هو بيقولك ممكن تستغل الـ Thermal Noise دي اللي خارجة من الـ Semiconductor
في إن أنت تقدر تعمل للـ Waves دي كدة Convert يطلع هنا Binary values، أو اللي هو الـ Output بيبقى Random Number. طيب Software-based؟ لأ، ده بيبقى زي Software كدة، يعني بتستغل مثلاً حركة الـ Keystroke sorry حركة  الـ Mouse أو الـ Keystroke، أو تستغل الـ Input والـ Output buffer، أو تستغل Values طالعة من الـ Operating System بتاعك
طيب يبقى إحنا خلاص عرفنا إن الـ True Random Number Generator معتمد يا إما Hardware يا إما Software زي ما قلنا. ماشي، طيب زي ما قلتلك إن هو  إن أنا  أعمل Generation لـ Random Numbers من خلال الـ True Random Number Generator دي بتبقى Difficult task لأن أنت محتاج إن الـ Output بتاعك يبقى Unbiased ومحتاجه يبقى Independent ومحتاج طبعاً Physical Source
عشان كدة الموضوع بيبقى صعب حبتين، عشان كدة لجأنا للـ Pseudo-random Number Generator. ماشي، نمسك بقى الـ Pseudo-random Number Generator، وزي ما قلتلك إن هو Deterministic Algorithm، يعني لو أنا اديتك الـ Initial Seed، إيه هي الـ Seed دي؟ الـ Seed دي بتبقى زي حاجة مبدئية كدة بتخش للـ Algorithm، ده الـ Algorithm هنا بتاعي
الـ Algorithm وهنا بيبقى الـ Seed، الـ Seed ده بيخش كدة كـ Input للـ Algorithm ده فالـ Algorithm ده بيطلعلي Random Number. قلنا ليه إن هو Deterministic Algorithm؟ عشان لو أنا فضلت أديلك نفس الـ Initial Seed دي اللي أنا بديهالك في كل مرة، فالـ Generator بتاعك أو الـ Algorithm بتاعك هنا في الخطوة دي هيطلع الـ Same output sequence
عشان كدة إحنا بنستغل زي ما قلتلك الـ True Random Number Generator عشان إن أنا أعمل الـ Seed ده، والـ Seed ده لعلمك لازم يبقى طبعاً يبقى Random في حد ذاته، وفي نفس الوقت يبقى Unpredictable Unpredictable، ليه Unpredictable؟ لأن أنا كـ Attacker ماجيش أعمل الـ Seed كدة وأروح مباصيه للـ Algorithm بحيث إنه يطلعلي الـ
ماشي، فهو بيقولك أهو إن هو بـ Produce sequence of numbers that are not statistically random، عشان كدة إحنا بنحاول نستغل الـ True Random Number Generator في إن أنا أعمل الـ Seed وإن أنا أ Combine ما بين الحاجتين دول، ولكن طبعاً أنت أكيد استنتجت إن الـ Algorithm اللي هنا لازم يبقى Algorithm قوي
Algorithm قوي عشان يقدر يعمل Generate لـ Random Numbers، فبالتالي الـ Random Numbers اللي هتطلع دول هيباصوا Many tests. لحد هنا الكلام مفهوم. طيب أهو قلنا الـ True Random Number Generator لازم يبقى هنا عندك حاجة بـت Convert، وهنا بيبقى عندك Physical Source، الـ Physical Source ده بيطلع أيًا يكن بيطلع Waves بيطلع أي حاجة بدخلها على الـ
الـ Converter ده بيطلعلي Random Bit Stream. طيب، الـ Pseudo-random Number Generator ده بيبقى داخله الـ Seed وهنا بيبقى في Algorithm معين جوه بيطلعي Random Numbers، الـ Output باخده كـ Input للـ Next iteration وهكذا. طيب، الـ Pseudo-random function ده هنا ما بيبقاش في حاجة تانية غير الـ Seed بتبقى داخلة والـ Input من الـ Previous iteration لكن هنا أنا باخد الـ Seed برضه وبيبقى في Value أنا مثبتها بتخش على الـ Algo
Algorithm بيطلع Output، الـ Output ده بيخش كـ Input للـ Next iteration. لحد هنا الكلام مفهوم. طيب تعال كدة نعمل Comparison كدة ما بينهم سريعة، الـ True Random Number Generator قلنا إنه Non-deterministic وقلنا إن هو معتمد علي حتة الـ Conversion من الـ Analog source to Binary output
وطبعاً أنت محتاج طبعاً Processing power عالية لأن أنت محتاج تحول للـ Waves دي لـ Binary numbers. طيب، الـ Pseudo-random Number Generator قلنا ده بيبقى خلاص Algorithm بيطلع Continuous stream of bits وبنستخدمه في حتة إن أنا أعمل Stream cipher application. طيب، الـ Pseudo-random number function
دي بتبقى برضه زي ما قلتلك هي هي زي اللي فاتت دي بس هنا أنا ببقى مثبت Value كدة بحيث إنها تخش على الـ Algorithm بتاعي، فهي.. وتخلي بالك إن ده بـي Produce اللي هو الـ Pseudo-random function ده بـي Produce أ Pseudo-random string of bits of fixed length، الخارج بيبقى Fixed length
ماشي، طب بستخدمه في إيه؟ بستخدمه في حتة الـ Symmetric encryption أو الـ Nonce وزي ما فهمتك إيه هو الـ Nonce المحاضرة اللي فاتت، قلتلك الـ Nonce ده بتبقى حاجة عشوائية كدة وما ينفعش تتكرر. ماشي، طيب عشان أعمل بقى Pseudo-random number generator ده في كذا حاجة لازم تتحقق
اللي هي أول حاجة الـ Unpredictability، Randomness، والـ Seed characteristics. Randomness يعني الحاجة اللي خارجة لازم تبقى Random. طيب Unpredictable؟ يعني الحاجة اللي خارجة ما ينفعش إن أنا أقدر أعمل لها Predict إذا كان Forward أو Backward، وهنفهم إزاي Forward و Backward. طيب الـ Seed؟ قلتلك إن الـ Seed ده اللي أنا ببقى مدخله للـ Algorithm لازم يبقى Secure ويبقى Unpredictable ما حدش يقدر يعمل له Predict
لأن لو حد قدر يعمل Predict للـ Seed وممكن وهو عارف الـ Algorithm المستخدم فخلاص الراجل يقدر يعمل Generate للـ Random number اللي هو نفس الـ Random number بتاعك. لحد هنا الكلام مفهوم. ماشي، نكمل. طيب إحنا قلنا أول حاجة الـ Randomness يعني عشان أعمل Pseudo-random number generator لازم يحققلي خاصية الـ Random
الـ Randomness دي زي ما قلتلك فوق إن أنا الحاجة بتاعتي اللي خارجة تبقى Random. طيب Random إزاي؟ زي ما قلتلك يبقى Uniform، يعني إيه Uniform؟ يعني عدد ظهور الـ Zeros أو الـ Ones يكاد يكون متساوي، يعني الـ Probability بتاعة ظهور الـ Zeros تبقى بـ Half وفي نفس الوقت الـ Ones تبقى بـ Half، يعني
Almost half. ماشي. Scalability؟ يعني إيه Scalability؟ يعني لو Sequence of random string، الـ Sequence ده يبقى Random، يعني مثلاً عندي 0 0 0 1 0 1 0 0 0 1 وهكذا، لو أنا جيت خدت ده أو ده أو ده، كل دول أو الـ Sub-sequence دول لازم يبقوا برضه  sorry Random
تمام؟ تالت حاجة الـ Consistency، الـ Behavior بتاع الـ Generator بتاعك ده ما تقدرش تعمل له Predict، يعني ما تقدرش تعمل Predict للـ Behavior بتاع الـ Algorithm أو الـ Generator بتاعك، يعني مثلاً أنا ببقى مديك الـ Seed في الأول والـ Algorithm بتاعك أهو بيخرج Value، الـ Value دي أنا ما أقدرش أ Predict الـ Behavior بتاعها، يعني ما أقدرش أ Predict مثلاً الـ Sequence اللي جاي هيبقى إزاي أو مثلاً الـ Value اللي جاية هتبقى 0 ولا 1 وهكذا.
تمام، يبقى كدة اتكلمنا على الـ Randomness. طيب الـ Randomness أكيد عشان الحاجة اللي خارجة أقدر أقول عليها Random، أكيد في تيستات لازم أعملها، طب إيه الـتيستات دي؟ فعندي تلات تيستات الـ Frequency test، الـ Runs test، الـ Maurer's universal statistical test. خلينا نمسك واحد واحد، الـ Frequency test دا زي ما قولتلك أو جاي من اسمه Frequency، يعني بيشوف الـ Frequency بتاعت الـ Zeros وبتاعت الـ Ones، وبيحاول عشان أقول عليه Random لازم قلنا إن
إن عدد الـ Zeros بيساوي عدد ظهور الـ Ones أو يكاد يكون متساوي. ماشي، يعني الـ Probability بتاعة كل الـ Zeros أو عدد ظهور الـ Zeros بـ Half وعدد ظهور الـ Ones بـ Half برضه. ماشي، طيب تاني Test اللي هو بنقول عليه الـ Runs test، لو إنت يعني في الـ Test دا أنا بشوف عدد ظهور الـ Zeros ورا بعض قد إيه، عدد ظهور الـ Ones قد إيه، فدا بنقول عليه الـ Runs test.
طيب تالت Test معانا اللي هو الـ Maurer's universal test، دا بيبقى بيـ Focus على حاجتين يعني، اللي هو إن عدد الـ Bits between الـ matching patterns، يعني لو في مثلاً Patterns بتتكرر هنا وهنا بيشوف عدد الـ Bits اللي اتكررت هنا وهنا، ماشي؟ طيب وحاجة كمان، الغرض بتاعه إنه بيـ Detect لو ينفع أنا في Sequence معين في الـ
في الـ Stream بتاعي ينفع أعمله Compress ولا لأ؟ يبقى تاني الـ Maurer's universal test دا بيـ Focus على حاجتين عدد الـ Bits between الـ matching patterns دي أول حاجة، وتاني حاجة بيشوف لو أنا أقدر أعمل Compress لـ Sequence معين، لو Sequence من أو Sub-sequence أقدر أعمله Compress ولا لأ.
ماشي، فكده إحنا عملنا تلات تيستات عشان أشوف إذا كان الـ Random ده أو الـ Random number ده فعلاً Random ولا لأ. ماشي، طيب إحنا قلنا برضه إن تاني حاجة معانا هي الـ Unpredictability. طيب إيه الـ Unpredictability؟ إحنا مش قولتلك إن إنت في الأول أدي دا الـ Algorithm بتاعك بيبقى داخله الـ Seed.
وبيبقى في هنا Algorithm وهنا الـ Output، وقلنا إن الـ Output داخل Input على الـ Next iteration. طيب لو أنا بقى معايا الـ Seed، لو أنا معايا الـ  Sorry Seed  خلينا نمسك الـ Forward الأول، لو أنا مش معايا الـ Seed أنا مقدرش أ Predict الـ Output دا، مقدرش أقول الـ Output دا هيبقى إيه.
طيب Backward بقى، لو أنا معايا الـ Output دا بقى أنا مقدرش أحدد الـ Seed. تمام كدة؟ تمام كدة، يبقى تاني لازم Unpredictable على مستوى حاجتين يا إما Forward يا إما Forward. Backward لو أنا الـ Seed مش عارفه مقدرش أ Predict الـ Output دا هيبقى شكله إزاي. طيب تاني حاجة الـ Backward إن أنا لو أنا معايا الـ Output صعب إن أنا أعمل Predict للـ Seed
كان بإيه. بمعنى آخر إن مفيش Correlation ما بين الـ Seed والـ Output، لازم ميبقاش في Correlation ما بين الـ Seed والـ Output. ماشي، لحد هنا الكلام مفهوم. طيب الـ Seed بقى اللي إنت شغلتني بيه دا، لازم يبقى زي ما قولتلك فوق إن هو لازم يبقى حاجة Secure وحاجة Unpredictable عشان محدش يجي يقدر يعمل له Predict.
طيب إحنا قلنا إن الـ Pseudo-random number generator قلنا دا Deterministic algorithm، يعني لو أنا عارف الـ Seed ممكن أقدر أعمل أو أ Predict ال value بتاعة الـ Output، صح كدة؟ صح كدة. تمام، فعشان كدة بيقولك إن الـ Seed دا حاجة Critical في الـ Algorithm بتاعك، لازم يبقى Unpredictable وفي نفس الوقت Secure.
وفي نفس الوقت لازم يبقى Random، يعني لازم يبقى Random وUnpredictable وبرضه أنا مسيفه بشكل Secure. طيب الـ Seed دا عشان أعمل له Generation زي ما قولتلك فوق، هعمله Generation إزاي؟ بستغل بقى حتة الـ True random number generator عشان أكريت الـ Seed دا. ماشي، يبقى لحد هنا مفهوم، يبقى تاني مراجعة سريعة، الـ Pseudo-random number generator لازم يكون بيحقق تلات حاجات.
الـ Randomness والـ Unpredictability والـ Seed. الـ Randomness لازم يبقى الحاجة Random، طيب تاني حاجة لازم Unpredictable إذا كان Forward أو Backward مقدرش أعمل Predict للـ Output من الـ Seed أو العكس. تالت حاجة اختيار الـ Seed ذات نفسه، الـ Seed لازم يبقى Random وSecure وUnpredictable، وقلنا إن أنا عشان أعمله Generation بستغل بقى الـ True Random Number Generator.
لحد هنا الكلام تمام. طيب نمسك أول واحد معانا اللي هو Linear Congruential Generator أو الـ LCG. طيب هو ليه Linear؟ أدي بص تعال نبص على الـ Equation بتاعته أهي: الـ X بتاعة الـ Iteration اللي أنا واقف فيها بتساوي الـ Xبتاعة الـ Iteration اللي قبلي مضروبة في الـ A، مجموع عليها الـ C، كل دا متخدله Linear. Mod M لأن الـ Degree بتاعة الـ Function دي.
1، فهو Just، Linear بضرب الـ X بتاعة الـ Iteration اللي قبلي في A وبـ Plus عليها الـ C وباخدلها Mod. طيب ليه Congruential؟ علشان إنت بتاخد الـ Mod. ماشي، يبقى دي الـ Equation بتاعته. طيب اختيار الـ A والـ C والـ M دا Critical بالنسبة لي
لازم أختار الـ Values دي بعناية علشان محدش يجي يقدر يحاول يـ Predict الـ Value بتاعة الـ Iteration اللي واقف فيها من الـ Iteration اللي قبل كدة. ماشي، وفي اللي هو الـ X0 دا، دا بيبقى الـ Seed اللي داخل للـ Algorithm في الأول خالص. طيب تعال ناخد كدة Example يفهمنا الدنيا ماشية إزاي.
أدي الـ Values أهي بتاعة الـ A والـ C والـ M والـ X0 زي ما قولتلك دا الـ Seed. طيب هعمل إيه؟ أنا عايز X1، هعمل إيه؟ X1 هتساوي الـ A اللي هي الـ 7 مضروبة في الـ X0 اللي هي 1 Plus الـ C، الـ C اللي هي بـ 0، خلاص يبقى هنشيل ده كأنها 7 مضروبة في واحد، ولما أضربها في واحد كأنها 7.
واخد لها Mod M،  Mod M اللي هو كام؟ Mod 32. يعني أول حاجة هتطلعلي بـ 7.
طيب التانية الـ X2 هتساوي اللي قبلك اللي هي كانت خارجة بـ 7، يبقى أدي الـ 7 مضروبة في الـ A، الـ A اللي هي كانت بـ 7 برضه، 7 فى 7 زائد، زائد مين؟ الـ C اللي هي بـ 0، خلاص إحنا مش هنضيف.
وخد الكلام ده Mod 32. Mod 32، ‏7 فى 7 بـ 49 Mod 32، الـ Mod هيطلع بـ 17. وهكذا. طيب يبقى دا الـ Sequence اللي طالع. لو خدت بالك إن الvalue بتاعة الـ A كانت صغيرة جداً، 7، يعني صغيرة جداً، والـ M كانت صغيرة جداً، والـ C يعني أنا محطتش قيمة للـ C.
فلو أنا بصيت على الـ Period، طب إيه الـ Period بس الأول؟ الـ Period هو عدد الـ Values الـ Unique اللي هتفضل تظهر لحد ما رقم منهم يتكرر . يعني إيه برضه؟ يعني هنا لو إنت خدت بالك أول مرة طلعت 7، 17، 23، 1، السبعة بدأت تظهر تاني.يبقى إيه الـ Period بتاعتك؟ يبقى دول هما الـ Period بتاعتك اللي هما 1، 2، 3، 4، يبقى الـ Period بتاعتك بـ 4.
يبقى الـ Period هو الـ Maximum number of outputs until the generator repeats itself، يعني لحد ما هيكرر نفس الـ Value.طب لو خدت بالك بقى لو أنا كبرت الـ A شوية، لو بص كدة الـ Period بقت بـ 8، يعني هو حسب حسبته بنفس الـ Steps اللي عملناها فوق لقى إن الـ Period بتاعته في 8. يعني إنت كل ما تكبر الـ A دي.
كل ما الـ Generator بتاعك يطلع Unique values، كل ما تكبر الـ A كل ما الـ Generator بتاعك يطلع Unique values. طب هل أنا محتاجه يطلع Unique values كبيرة؟ آه طبعاً، لأن أنا عاوز أول مرة يطلع Value، تاني مرة يطلع Value مختلفة عن اللي قبل وهكذا. عشان كدة إن إنت اختيار الـ A والـ M برضه لازم يبقوا Large Prime Number.
Large prime number. الـ M دي لازم تبقى Large prime number، ليه Large؟ عشان زي ما قولتلك فوق عاوز أكبر الـ Period اللي أنا بختار منها. طيب وليه Prime؟ زي ما فهمتك قبل كدة إن الـ Prime ملوش Pattern بيتكرر بيه أقدر أعمله Predict. لحد هنا الكلام مفهوم. طيب هل الكلام ده Secure؟ لا مش Secure، لإنه من اسمه هو Linear.
فبيقولك لو الـ Attacker Know Any Three Subsequent Output، يعني لو عرف تلاتة Values، يعني مثلاً X1 مثلاً و X2 و X3، ممكن يقدر يعمل Predict لمين؟ للـ A والـ C. وطالما قدر يعمل Predict للـ A والـ C كدة هيقدر يعمل Predict للـ Stream كله، عشان كدة هو مش Secure أوي.
طيب عشان كدة عملنا حاجة اسمها الـ Blum Blum Shub Generator أو الـ BBS. الـ BBS ده بيبقى برضه معتمد على Steps أو Mathematical Function. طيب بيعمل إيه ده؟ أول حاجة بيختار P و Q عشان من خلالهم يحسب N وبيختار حاجة الـ S، الـ S دي بتبقى Random. الـ P والـ Q دول لازم يبقوا Large Prime Number.
عشان من خلالهم هحسب الـ N ومن الـ N دي أنا معايا Value برضه بختارها اللي هي الـ S، ولازم تبقى Relatively Prime مع الـ N. الـ Algorithm بقى شغال إزاي؟ الـ Algorithm في الأول عشان بيحسب الـ Seed اللي هي الـ X0 بياخد الـ S اللي إنت حاسبها فوق دي اللي هي الـ Random بيرفعها لـ Power وبياخدها Mod N اللي هي عبارة عن حاصل ضرب الـ P في الـ Q.
فكده طلع الـ X0، يبقى كده طلع الـ Seed. طيب وبعد ما طلع الـ Seed أنا محتاج أطلع الـ X بقى 1 والـ X 2 والـ X 3 To Infinity، صح كدة؟ صح، عشان كدة بخش في Loop من 1 To Infinity. فبقولك إن الـ X بتاعة الـ Iteration اللي أنا واقف فيها بتساوي الـ X بتاعة الـ Iteration اللي قبلي.
مرفوعة لـ Power 2 وخد لها Mod N. طيب ده الـ X، أنا عاوز الـ Bit لأن ده بيطلع Bits صح كدة؟ Sequence of Bits. يبقى الـ Bit اللي أنا واقف فيه بيبقى الـ X اللي هي اللي أنا لسه حاسبها فوق دي Mod 2. طب ليه Mod 2؟ عشان يطلعلي يا 0 يا 1، يا يطلعلي يا 0 يا 1. طيب من خلال بقى الـ Steps واللي قلناه ده وإن أنا بختار Large Prime Numbers، هل الكلام ده Secure؟ آه Secure.
قوة الـ Algorithm معتمدة في إن إنت تـ Factorize الـ N دي، تـ Factorize الـ N دي لـ P و Q. طيب لو الـ N دي كبيرة، فإن إنت تـ Factorize الـ N دي بيبقى صعب، فالـ Algorithm في الحالة دي بيبقى Secure. يبقى إنت الحاجة الـ Critical عندك هو اختيار الـ N، وطبعاً مننساش برضه إن الـ S دي لازم تبقى برضه.
رقم Relatively Prime مع الـ N وبرضه في نفس الوقت لازم يبقى Large Prime Number. ماشي، فهو بيوريك هنا Table بيوريك بس لو هو اختيار الـ N والـ S، خلاص اختيار الـ N والـ S أهو. فهو عشان يعمل X0 عمل برضه بنفس الـ Steps قالك إن الـ X0 دي عبارة عن الـ S Square وخد لها Mod N، فهو بياخد الـ S دي اللي هي الـ Value دي Square وخد لها Mod N طلعت له مثلاً بـ Value معينة، ياخد الـ Value دي
على الـ Iteration اللي بعد كدة يخش في الـ Loop دي يعمل الـ Steps فيطلع يا 1 يا 1 0 0 وهكذا. ولو خدت بالك مش هتلاقي إن Pattern بيتكرر، يعني مثلاً هنا 1 1 0 0 وبعد كده 1 1 1 0 0 0 0 وبعد كده 1 0 0 1 1 1 0 وهكذا هتلاقي إن الأرقام يعني مفيش Pattern قادر تحدده.
ماشي. طيب نكمل، آه حاجة أخيرة قبل ما نطلع من الحتة دي، لو أنا مثلاً أنا خلاص الـ Sequence بقيت عارف إنه 1 1 0 0 1 وهكذا، يعني مثلاً لو واقف هنا أنا مقدرش أعمل Predict يعني أنا مثلاً لو مديك الـ Values دي كلها أنا مقدرش أ Predict إن الـ Value اللي بعد كدة هتطلع يا 0 يا 1، المفروض إن الـ Generator بتاعه يحقق إنه مينفعش أعمل Predict للـ Next Bit.
طب أنا لو عرفت مثلاً دول مقدرش أ Predict ده وهكذا، ماشي؟ وقلتلك زي ما فهمتك إن قوة الـ Algorithm في حتة إن إنت تـ Factorize الـ N دي. ماشي، زي ما بيفهمك أهو بيقولك إنه لازم يعدي حاجة اسمها الـ Next Bit Test، إيه هو الـ Next Bit Test؟ فبيقولك لو إنت معاك K Bits، لسه قايلنها من الـ Sequence كله.
مفيش أو مستحيل إن إنت تقدر تـ Predict إذا كانت الـ Next Value دي هتبقى يا 1 يا 0. وزي ما قلنا إن الـ BBS معتمد على أو صعوبته معتمدة على في حتة إن إنت تـ Factorize الـ N. ماشي. طيب في بقى طريقة تانية بيستغلوها زي ما فهمتك اللي هو إن هو بيستغل الـ Counter Mode والـ Output Feedback Mode اللي أخدناهم المحاضرة اللي فاتت في إن هو يـ Generate.
Random Numbers، يعني إيه برضه؟ يعني بيبقى عنده Algorithm هنا، لو نفتكر كدة الـ Counter كنت بدخل Initial Value كدة اللي هو الـ Counter، وبعد كدة الـ Output بيطلع هنا، هنا كنت بعمل Encrypt للي داخل والـ Output كان بيبقى حاجة Unique على مستوى الـ Block والـ Counter دا كان بيزيد مع كل Iteration. والـ Output Feedback Mode لو نفتكر كان هو برضه كدة وبالشكل ده وإن الـ Output هنا كان بيخش هنا Input هنا وهكذا.
ده كان الـ Two Modes دول، طب هتستغلهم إزاي في حاجة زي كدة إن إنت تـ Generate Random Bits؟ فإنت بيبقى داخل للـ Algorithm دا حاجة اسمها الـ Seed. الـ Seed دا كل مرة هعمله Increment لو مثلاً هتكلم على مستوى الـ Counter، كل مرة هعمله Increment يعني بدل ما لسه بقى.
هعمل Algorithm وكل حاجة؟ لا، أنا عندي الـ DES أو الـ AES جاهزين، هنا مثلاً الـ AES المستخدم، مجرد اعمل Increment، خش اعمل Encryption، طلع Output. الـ Output دا هيبقى حاجة Random على مستوى الـ Block دي. طيب بعد كدة Increment الـ Seed، وبعد كدة هتعمل إيه؟ برضه هتعمل Encrypt لنفس الكلام وتعمل Generation لـ Random.
ماشي، أهو بيوريك زي كدة تفصيلة ما بينهم، هنا إنت بيبقى عندك اللي هو الـ Seed بتاعك أو الـ Value اللي هي بتبقى حاجة بتـ Initialize بيها الـ Algorithm بتاعك، وهنا إنت بيبقى داخل للـ Algorithm بتاعك طبعاً Key، الـ Key دا بتعمل Encrypt بيه للـ Message، الحاجة اللي طالعة أهو بيطلعلك Random Bits أو Pseudo Random Bits، بعد كدة تعمل Increment بـ 1 وهكذا بتفضل تكرر نفس الـ Step.
الـ Output Feedback Mode إنت برضه بتعمل هنا Initialize برضه للـ Algorithm بتاعك بالـ Seed والـ بتخش تعمل Increment بالـ Key، يخرج Value، تدخلها كـ Input للي بعد للـ Next Iteration وتكرر بقى نفس الـ Steps. إنت ميزة حاجة زي كدة إيه؟ إن إنت استغليت الـ Counter Mode أو الـ Output Feedback Mode في إن إنت بدل ما لسه هتعمل Algorithm وتـ Test الـ Algorithm لا، إنت بس استغليت الـ Algorithm وأديته الـ Initial Seed بتاعته علشان.
يطلعلك Random Bits أو Pseudo Random Number Bits. ماشي، لحد هنا الكلام واضح وصريح. هنا بس بيكلمك في حتة إن الـ Counter Mode اللي استغلناه فوق ده بس هو بيعيد تسميته اللي هو مسمينه اللي هو الـ Counter Mode Deterministic Random Bit Generator، وبيقولك إن الـ Algorithm دا مستخدمينه في حتة الـ Hardware Random Number Generator اللي موجودة في الـ Intel Processor Chip.
مش علينا التفاصيل دي أوي، وبيقولك إن طبعاً زي ما قلنا فوق إن الـ Algorithm المستخدم يا إما AES أو DES. طيب لو DES بيبقى مستخدم 3 Keys الـ Version بتاع الـ 3 Key Encryption. ولو AES بيبقى مستخدم بقى على حسب هو مستخدم إيه 128 Key Bit أو 192 أو 256، دي الكيهات اللي مستخدمة مع الـ AES.
لحد هنا الكلام تمام. طيب خلينا نقول كم حاجة كدة فوق. إنت باستنتاجك كدة إيه الـ Critical؟ إيه الـ Critical في الـ Algorithm بتاعك ده؟ هتقولي الـ Size بتاع الـ Seed، صح، والـ Size بتاع الـ Key اللي داخل، والـ Size اللي خارج.
كل ده مؤثر على الـ Algorithm بتاعي، بس هو ده اللي هيقولهولك بقى تحت. يبقى في Four parameters معتمد عليهم الـ Algorithm بتاعي، اللي هو الـ Length بتاع الـ Output block من كل Encryption algorithm، الـ Key length اللي داخل على الـ Algorithm بتاعي، الـ Seed length اللي أنا بـ Initialize بيه الـ Algorithm بتاعي وبكل مرة بقعد أعمله Increment فبالتالي هو اللي بيحقق الـ Seed ده أو الـ value بتاع أو الـ Length بتاع .
الـ Seed هو اللي بيحدد الـ Length اللي خارج من الـ Algorithm بتاعي. آخر حاجة اللي هو الـ Maximum number of output blocks generated before updating the algorithm with new seed. يعني إنت لما هتيجي تغير قيمة الـ Seed إنت هتغيره إمتى؟ بعد عدد Blocks معينة، أنا يهمني بقى عدد الـ Blocks اللي قبله قبل ما أغير عدد الـ Seed ده. يبقى ده برضه شيء Critical بالنسبة لي.
يبقي تاني هما أربع حاجات الـ Output block length، الـ Key length، الـ Seed length، الـ Output block length هو ده الـ Output اللي خارج من الـ Algorithm، الـ Key length ده الـ Key أو الـ Size بتاع الـ Key اللي داخل للـ Algorithm، الـ Seed length الـ Length بتاع الـ Seed اللي داخل للـ Algorithm بتاعي، آخر حاجة الـ Reseed interval دي الـ Maximum number of blocks اللي المفروض يحصل لها Generation قبل ما أعمل Update
الـ Value بتاعة الـ Seed بتاعي. ماشي، فهو بيقولك هنا لو إنت مستخدم Triple DES فالمفروض تستخدم الـ Output length بـ 64، الـ Key length تستخدمه بالرقم ده. الأرقام دي طبعاً مش حفظ ده هو بس الجدول ده بس للتوضيح. هنا بقى بالنسبة للـ Counter
الـ Counter mode بيعمل إيه برضه؟ زي ما قلناه فوق، إحنا بيبقى هنا قيمة الـ Seed اللي هي بتبقى داخلة هنا الـ V دي، بتبقى بـ Initialize بيها الـ Algorithm، بيحصل لها Encryption، Encryption بالـ Key، بيبقى خارج Output. الـ Output ده بدخله على Entropy source، Entropy source زي ما فكرتك ده Physical source أو حاجة بتحقق لي.
بتـ Check الـ Randomness Randomness، تمام؟ بعد كدة بيقسمها قيمتين Key و Value، بياخد الـ Key والـ Value دول للـ Iteration اللي بعد كدة الـ V دي اللي هي الـ Seed بيعمل لها Increment يدخلها للـ Algorithm والـ Key ده هو بيعمل بيه Increment في الـ Step دي.
فهنا الـ Seed بتاعك هيخش هنا للـ Function أو الـ Algorithm يحصل له Encrypt ويكرر نفس الـ Steps. الـ Output هيقسمه يدخله على Entropy source، الـ Value اللي طالعة من هنا تخش على Entropy source، يقسمها Key و Value، الـ Value دي برضه هتخش كـ Seed للـ Next iteration والـ Key ده هيبقى مستخدم في الـ Algorithm اللي مستخدم جوه.
ماشي، لحد هنا الكلام تمام. تعال نحل الكام سؤال دول كدة مع بعض قلنا أول واحد اللي بيقولك Use to produce a pseudo-random string of bits of some fixed length. زي ما فهمتك فوق some fixed length ده كان مين؟ الـ Pseudo-random function. تاني سؤال معانا اللي بيقولك A source that is effectively random is referred to as entropy source. قلنا الـ Entropy source ده.
إن هو مصدر بيحقق لك إن هو يبقى Random ده بالنسبة للـ Entropy source. طيب تالت حاجة مين الـ Approaches اللي استخدمناها في إن أنا أ build الـ Pseudo-random number generator اللي بيستخدم في حتة الـ Block cipher؟ قلنا إن عندي Two modes اللي هما الـ Counter mode والـ Output feedback mode.
طيب آخر حاجة معانا Uses a non-deterministic source. قلنا مين اللي بيستخدم Non-deterministic؟ الـ True random number generator. طب اللي بيستخدم الـ Deterministic اللي هو الـ Pseudo-random number generator. كدة المحاضرة خلصت، بعتذر على الإطالة يا شباب ولو في أي سؤال يا ريت نتفضل. شكراً.