Practical Aspects of Modern Cryptography Problem Solutions
Explore detailed solutions to problems related to modern cryptography, including group formations and integer properties. Understand the patterns and structures of different integer groups in this practical guide from October 4, 2016.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Assignment 1 Solutions
Problem 1 October 4, 2016 Practical Aspects of Modern Cryptography 2
Problem 1 The Positive INTEGERS 1 5 9 13 17 21 25 29 2 6 10 14 18 22 26 30 3 7 11 15 19 23 27 31 4 8 12 16 20 24 28 32 Group 4: Group 1: Group 2: Group 3: October 4, 2016 Practical Aspects of Modern Cryptography 3
Problem 1 Group 1 integers all have the form: 4? + 1, where ? . The product of two Group 1 integers looks like 4? + 1 4? + 1 = 16?? + 4? + 4? + 1 = 4 4?? + ? + ? + 1 which is a Group 1 integer. October 4, 2016 Practical Aspects of Modern Cryptography 4
Problem 1 Group 3 integers all have the form: 4? 1, where ? . The product of two Group 3 integers looks like 4? 1 4? 1 = 16?? 4? 4? + 1 = 4 4?? ? ? + 1 which is a Group 1 integer. October 4, 2016 Practical Aspects of Modern Cryptography 5
Problem 1 The Positive INTEGERS 1 4 7 10 13 16 19 22 2 5 8 11 14 17 20 23 3 6 9 12 15 18 21 24 Group 3: Group 1: Group 2: October 4, 2016 Practical Aspects of Modern Cryptography 6
Problem 1 Group 1 integers all have the form: 3? + 1, where ? . The product of two Group 1 integers looks like 3? + 1 3? + 1 = 9?? + 3? + 3? + 1 = 3 3?? + ? + ? + 1 which is a Group 1 integer. October 4, 2016 Practical Aspects of Modern Cryptography 7
Problem 1 Group 2 integers all have the form: 3? 1, where ? . The product of two Group 2 integers looks like 3? 1 3? 1 = 9?? 3? 3? + 1 = 3 3?? ? ? + 1 which is a Group 1 integer. October 4, 2016 Practical Aspects of Modern Cryptography 8
Problem 1 The Positive INTEGERS 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 Group 1: Group 2: October 4, 2016 Practical Aspects of Modern Cryptography 9
Problem 1 The Positive INTEGERS 1 7 13 19 25 31 37 43 2 8 14 20 26 32 38 44 3 9 15 21 27 33 39 45 4 10 16 22 28 34 40 46 5 11 17 23 29 35 41 47 6 12 18 24 30 36 42 48 Group 6: Group 1: Group 2: Group 3: Group 4: Group 5: October 4, 2016 Practical Aspects of Modern Cryptography 10
Problem 2 October 4, 2016 Practical Aspects of Modern Cryptography 11
Problem 2 ?1= ??1+ ?1 with ?1= ?1 mod ? ?2= ??2+ ?2 with ?2= ?2 mod ? ?1= ?2 ?1 ??1= ?2 ??2 ?1 ?2= ? ?1 ?2 ?1 ??2 (with ? = ?1 ?2) October 4, 2016 Practical Aspects of Modern Cryptography 12
Problem 2 ?1= ??1+ ?1 with ?1= ?1 mod ? ?2= ??2+ ?2 with ?2= ?2 mod ? ?1 ??2 ?1 ?2= ??, for some integer ? ?1= ?2+ ?? = ??2+ ?2 + ?? = ? ?2+ ? + ?2 ?1= ?2 (since division theorem gives unique ?) October 4, 2016 Practical Aspects of Modern Cryptography 13
Problem 3 October 4, 2016 Practical Aspects of Modern Cryptography 14
Problem 3 ?1= ??1+ ?1 with ?1= ?1 mod ? ?1 mod ? + ?2= (?1 ??1) + ?2= (?1+ ?2) ??1 ?1 mod ? + ?2 ??1+ ?2 ((?1 mod ?) + ?2) mod ? = (?1+ ?2) mod ? October 4, 2016 Practical Aspects of Modern Cryptography 15
Problem 3 ?1= ??1+ ?1 with ?1= ?1 mod ? (?1 mod ?) ?2= (?1 ??1) ?2 = (?1 ?2) ?(?1 ?2) (?1 mod ?) ?2 ??1 ?2 ((?1 mod ?) ?2) mod ? = (?1 ?2) mod ? October 4, 2016 Practical Aspects of Modern Cryptography 16
Problem 4 October 4, 2016 Practical Aspects of Modern Cryptography 17
Problem 4 ? ? ? ? ? ? 83 = 59 1 + 24 59 = 24 2 + 11 24 = 11 2 + 2 83 59 24 59 24 11 1 0 1 0 1 -1 1 2 3 1 2 11 = 2 5 + 1 2 = 1 2 + 0 11 2 1 2 1 0 -2 5 -27 59 3 -7 38 -83 2 5 2 4 5 6 October 4, 2016 Practical Aspects of Modern Cryptography 18
Problem 4 ? ? ? ? ? ? 83 = 59 1 + 24 59 = 24 2 + 11 24 = 11 2 + 2 83 59 24 59 24 11 1 0 1 0 1 -1 1 2 3 1 2 11 = 2 5 + 1 2 = 1 2 + 0 11 2 1 2 1 0 -2 5 -27 59 3 -7 38 -83 2 5 2 4 5 6 October 4, 2016 Practical Aspects of Modern Cryptography 19
Problem 4 ? ? ? ? ? ? 83 = 59 1 + 24 59 = 24 2 + 11 24 = 11 2 + 2 83 59 24 59 24 11 1 0 1 0 1 -1 1 2 3 1 2 11 = 2 5 + 1 2 = 1 2 + 0 11 2 1 2 1 0 -2 5 -27 59 3 -7 38 -83 2 5 2 4 5 6 83 27 + 59 38 = 1 October 4, 2016 Practical Aspects of Modern Cryptography 20
Problem 4 ? ? ? ? ? ? 83 = 59 1 + 24 59 = 24 2 + 11 24 = 11 2 + 2 83 59 24 59 24 11 1 0 1 0 1 -1 1 2 3 1 59 mod 83 = 38 1 2 11 = 2 5 + 1 2 = 1 2 + 0 11 2 1 2 1 0 -2 5 -27 59 3 -7 38 -83 2 5 2 4 5 6 83 27 + 59 38 = 1 October 4, 2016 Practical Aspects of Modern Cryptography 21
Problem 5 October 4, 2016 Practical Aspects of Modern Cryptography 22
Problem 5 Alice Bob Randomly select a large integer ? and send ? = ?? mod ?. Compute the key ? = ?? mod ?. Randomly select a large integer ?and send ? = ?? mod ?. Compute the key ? = ?? mod ?. ??= ???= ???= ?? 23 October 4, 2016 Practical Aspects of Modern Cryptography
Problem 5 Alice Bob Randomly select a large integer ? and send ? = ?? mod ?. Compute the key ? = ?? mod ?. Randomly select a large integer ?and send ? = ?? mod ?. Compute the key ? = ?? mod ?. ?? = ??? = ??? = ?? 24 October 4, 2016 Practical Aspects of Modern Cryptography
Problem 5 What does Eve see? ?, ??, ?? but the exchanged key is ???. Belief: Given ?, ??, ??it is difficult to compute Yab. October 4, 2016 Practical Aspects of Modern Cryptography 25
Problem 5 What does Eve see? ?, ??, ?? (all mod ?) but the exchanged key is ???. But given?? and ?, one can use the Extended Euclidean Algorithm to compute ?? ? mod ? to determine ? mod ?. From ?? mod ? and ? mod ?, ??? mod ? can be computed. So the key exchange is insecure. October 4, 2016 Practical Aspects of Modern Cryptography 26
