, Page 1 of 8 School of Science COSC2536/2537 Security in Computing and Information Technology Assignment 1 Assessment Type: Individual assignment; no group work. Submit online via Canvas → Assignments → Assignment 1. Marks awarded for meeting requirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums. Due date: Week 5, Friday the 23rd Aug 2019 11:59pm Deadlines will not be advanced, but they may be extended. Please check Canvas→Syllabus or via Canvas → Assignments → Assignment 1 for the most up to date information. As this is a major assignment in which you demonstrate your understanding, a university standard late penalty of 10% of full mark (i.e. 1.5 marks) per each working day applies for up to 5 working days late, unless special consideration has been granted. Weighting: 15 marks (Contributes 15% of the total grade) 1. Overview The objective of Assignment 1 is evaluating your knowledge on the topics covered in Lecture 1-4. Topics include Basic Cryptographic Techniques, and Public-Key Cryptography (RSA, ElGamal and Paillier cryptosystems). Assignment 1 will focus on developing your abilities in application of knowledge, critical analysis and decision making. Assignment 1 contains several problems related to the topics mentioned above. You are required to prepare the solutions and upload them as a single PDF or Word document in CANVAS. In this assignment, there are 6 (six) questions in total. The first question Q1 is on cryptanalysis. The term Cryptanalysis is used to breach cryptographic security systems and gains access to the contents of encrypted messages, even if the cryptographic key is unknown. Therefore, you are expected to apply cryptanalysis in order to obtain plaintext from the given ciphertext in Q1. The second question Q2 is about the application of hash algorithm. Q2 has two parts. In the first part, you are expected to perform a forward search attack for a given protocol that uses hash algorithm for providing security. In the second part, you have to discuss a modified version of the given protocol where the forward search attack would not work. The third question Q3 is related to RSA Encryption algorithm. In this question, you are expected to demonstrate your understanding of the RSA Encryption algorithm. Values of required parameters are provided including the plaintext or message M and you should demonstrate the key generation, encryption and decryption processes with detail computations and brief explanations. Marks will be deducted if you fail to show the detailed computation correctly, skip the computation steps, or do not provide explanations. The fourth question Q4 is related to breaking the RSA Encryption algorithm. In this question, you are expected to determine the plaintext M from the ciphertext C without knowing the RSA private-key. Public-key parameters and ciphertext are provided to you. You should demonstrate the detailed steps with explanations about how the RSA encryption algorithm can be broken. Marks will be deducted if you fail to show the detailed computation correctly, skip the computation steps, or do not provide explanations. The fifth question Q5 is related to ElGamal Encryption algorithm. In this question, you are expected to demonstrate your understanding of the ElGamal Encryption algorithm. Values of required parameters are provided including the , Page 2 of 8 plaintext or message M and you should demonstrate the key generation, encryption and decryption processes with detailed computations and brief explanations. Marks will be deducted if you fail to show the detail computation correctly, skip the computation steps, or do not provide explanations. The final question Q6 is related to Paillier Encryption algorithm. In this question, you are expected to demonstrate your understanding of the RSA Encryption algorithm. Values of required parameters are provided including the plaintext or message M and you should demonstrate the key generation, encryption and decryption processes with detail computations and brief explanations. Marks will be deducted if you fail to show the detailed computation correctly, skip the computation steps, or do not provide explanations. Develop this assignment in an iterative fashion (as opposed to completing it in one sitting). You should be able to start preparing your answers immediately after the Lecture-1 (in Week-1). At the end of each week starting from Week-1 to Week-4, you should be able to solve at least one question. If there are questions, you must ask via the relevant Canvas discussion forums in a general manner. Overall, you must follow the following special instructions: • You must use the values provided in the questions. • Hand-written answers are not allowed and will not be assessed. Compose your answers using any word processing software (e.g. MS Word). • You are required to show all of the steps and intermediate results for each question. • Please DO NOT provide codes as an answer. Only codes will not be assessed. • Upload your solution as a single PDF or Word document in CANVAS. 2. Assessment Criteria This assessment will determine your ability to: • Follow requirements provided in this document and in the lessons. • Independently solve a problem by using cryptography and cryptanalysis concepts taught over the first four weeks of the course. • Meeting deadlines. 3. Learning Outcomes This assessment is relevant to the following Learning Outcomes: • understand the fundamentals of cryptographic techniques. • analyse the security limitations of early cryptographic techniques. • learn the fundamentals of cryptanalysis. • learn how hash algorithms and public-key cryptography scheme works. • understand the applications of hash algorithms and public-key cryptography scheme. • develop libraries of public-key cryptographic techniques using any programming language of your choice. • use public-key cryptographic techniques in small and large scale applications. 4. Assessment details Please ensure that you have read Section 1 to 3 of this document before going further. Assessment details (i.e. question Q1 to Q6) are provided in the next page. , Page 3 of 8 Q1. Cryptanalysis (Marks: 4.5) (a) [Cryptanalysis on Simple Substituion Cipher] (Marks 1) Show step-by-step process to find the plaintext and the key for the following ciphertext using the concept of simple substitution cipher ‘shift by n’ as discussed in Lecture-1: Ciphertext: NZXMTYLETZYD Find the plaintext using shift by n as discussed in Lecture-1 and tutorial-1. (b) [Cryptanalysis on Double Transposition Cipher] (Marks 1.5) Decrypt the following ciphertext using the double transposition cipher (as discussed in the Lecture-1 and Tute-1) using a matrix of 7 rows and 8 columns. Ciphertext: NAGEIDVTATLNIITYNDFAOICENHANICTICPRTEYHTPTOSMRIAAYPORHGI Hint: The first two words in the plaintext are “THE” and “CRYPTOGRAPHY”. (c) [Cryptanalysis on Substitution Cipher] (Marks 2) Assume that the following ciphertext has been produced using a substitution cipher. Please note that it may not be a simple ‘shift by n’ substitution. The ciphertext is as follows: MDUNPWV UF IYR PEUQUIV BK PT UTLUNULSPQ BD JDBSM IB FRWQSLR IYRZFRQNRF, BD UTKBDZPIUBT PEBSI IYRZFRQNRF, PTL IYRDREV RHMDRFF IYRZFRQNRF FRQRWIUNRQV. IYR EBSTLPDURF PTL WBTIRTI BK AYPI UF WBTFULRDRL MDUNPIR LUKKRD PZBTJ WSQISDRF PTL UTLUNULSPQF. AYRT FBZRIYUTJ UF MDUNPIR IB P MRDFBT, UI SFSPQQV ZRPTF IYPI FBZRIYUTJ UF UTYRDRTIQV FMRWUPQ BD FRTFUIUNR IB IYRZ. IYR LBZPUT BK MDUNPWV MPDIUPQQV BNRDQPMF AUIY FRWSDUIV, AYUWY WPT UTWQSLR IYR WBTWRMIF BK PMMDBMDUPIR SFR, PF ARQQ PF MDBIRWIUBT BK UTKBDZPIUBT. MDUNPWV ZPV PQFB IPCR IYR KBDZ BK EBLUQV UTIRJDUIV. IYR DUJYI TBI IB ER FSEXRWIRL IB STFPTWIUBTRL UTNPFUBTF BK MDUNPWV EV IYR JBNRDTZRTI, WBDMBDPIUBTF BD UTLUNULSPQF UF MPDI BK ZPTV WBSTIDURF' MDUNPWV QPAF, PTL UT FBZR WPFRF, WBTFIUISIUBTF. Find the plaintext by frequency analysis technique as discussed in Lecture-1 and tutorial-1. Q2. Application of Hash Algorithm (Marks: 2) Assume that Alice, Bob and Trudy want to participate in an online auction to purchase an item. The idea here is that these are supposed to be sealed bids, i.e. each bidder gets one chance to submit a secret bid. In order to submit a secret bid, a bidder generates hash value of their bid amount using SHA-256 hash algorithm and sends the hash value as their bid to the auctioneer. All of the bids are revealed when all of the participants send their secret bid to the auctioneer. Trudy is a smart person who is certain that Alice and Bob will both place their bids between $351 and $365. Trudy captures the following hash values of Alice and bob: Hash value of Alice: 73DAA9289DDD08A53BA86F065DDB07BF915ABA208BEC652E999613D2A8444228 Hash value of Bob: 9197E4844ABED2FEA3569A2ACF7B0D584C979C333AB7AE10BA6C339898776F5A , Page 4 of 8 i. Describe a forward search attack step-by-step by which Trudy can determine Alice’s and Bob's bid from their respective hash values. ii. Describe how the above bidding procedure cane be modified to prevent a forward search attack. [Hints: Use the concepts of forward search attack that is discussed in Lecture-2 and Tutorial-2]. Q3. RSA Encryption Algorithm (Marks: 1.5) Say, Alice and Bob are two agents in the federal security services. Alice wants to send a secret message to Bob by encrypting the secret message. In other words, Alice is the sender and Bob is the receiver of the secret message. However, Alice and Bob have never contacted before. Therefore, they do not have any shared secret key. As a result, they have to use Public-Key cryptography. Bob generates public and private keys using RSA encryption algorithm and sends the public key to Alice. Alice encrypts her secret message using RSA encryption and sends the encrypted message to Bob. Consider that Alice has a secret message M=8567 to send to Bob. Bob uses parameter p=1091 and q=593, and chooses a small public key parameter e. What are the values of suitable public and private keys? How would Alice encrypt message M=8567? How would Bob decrypt the encrypted message C with the private key? You need to show every step. [Hints: Use the concept that is discussed in Lecture-3 and Tutorial-3]. Q4. Breaking RSA Encryption Algorithm (Marks: 2) Recently, researchers have successfully decrypted the RSA ciphertext using one of the RSA cryptanalysis techniques, called prime factorization, without knowing the private key. Say, Trudy is an intelligent hacker who knows RSA encryption algorithm and prime factorization very well. Hence, she has been hired by someone who wants to know the secret message between Alice and Bob. Trudy uses her understanding on the prime factorization-based RSA cryptanalysis techniques for retrieving Alice and Bob’s secret message. Assume that Alice wants to send a message to Bob. Bob generates public and private keys using RSA Encryption algorithm and publishes the public key (n=48443, e=59). Alice has a secret message M to send. She encrypts the message M using the public key and generates the ciphertext C=41826. Alice sends the encrypted message C=41826 to Bob. Trudy captures the encrypted message C=41826. She also has the public key (n=48443, e=59) because it is known to all. How can Trudy decrypt the encrypted message C and find the value of M? Show all the steps. How can Trudy verify if she has computed the correct message or not? [Hints: Use the concept that is discussed in Lecture-3]. , Page 5 of 8 Q5. ElGamal Encryption algorithm (Marks: 2.5) From a reliable source, Alice and Bob came to know that their message is being captured by someone. Therefore, Alice and Bob decide to use ElGamal encryption algorithm for their next communication. Alice has a message M=30 to send to Bob. Bob chooses p= 7639, g=3771, and x=91. Alice chooses r=37. Show the encryption and decryption steps. [Hints: Use the concept that is discussed in Lecture-4 and Tutorial-4]. Q6. Paillier Encryption algorithm (Marks: 2.5) Now, Alice and Bob decide to use Paillier encryption algorithm for their new communication. Alice has a message M=4567 to send to Bob securely using Paillier encryption algorithm. Bob chooses p=137, q=83, and selects an integer g =173. Alice selects a random number r=73. Show the encryption and decryption steps. [Hints: Use the concept that is discussed in Lecture-4 and Tutorial-4] 5. Academic integrity and plagiarism (standard warning) Academic integrity is about honest presentation of your academic work. It means acknowledging the work of others while developing your own insights, knowledge and ideas. You should take extreme care that you have: • Acknowledged words, data, diagrams, models, frameworks and/or ideas of others you have quoted (i.e. directly copied), summarized, paraphrased, discussed or mentioned in your assessment through the appropriate referencing methods, • Provided a reference list of the publication details so your reader can locate the source if necessary. This includes material taken from Internet sites. If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work and ideas of another person without appropriate referencing, as if they were your own. RMIT University treats plagiarism as a very serious offence constituting misconduct. Plagiarism covers a variety of inappropriate behaviours, including: • Failure to properly document a source • Copyright material from the internet or databases • Collusion between students For further information on our policies and procedures, please refer to the University website. 6. Assessment declaration When you submit work electronically, you agree to the assessment declaration. , Page 6 of 8 7. Rubric/assessment criteria for marking All of the computations must be correct and only provided values must be used. Instructions must be followed. Criteria The characteristic or outcome that is being judged. Total Question 1(a) Cryptanalysis on Simple Substituion Cipher Plaintext and key are correct All possible values are shown in a systematic way 1 Marks Plaintext and key are correct But all possible values are not shown 0.5 Marks Either plaintext or key is incorrect 0.25 Marks None of the plaintext and key is correct Or Not answered 0 Marks 1 Marks Question 1(b) Cryptanalysis on Double Transposition Cipher Plaintext and key are correct All of the possible values are shown in a systematic way 1.5 Marks Plaintext and key are correct But all steps are not shown 1 Marks Either plaintext or key is incorrect 0.5 Marks None of the plaintext and key is correct Or Not answered 0 Marks 1.5 Marks Question 1(c) Cryptanalysis on Substituion Cipher using frequency analysis technique Plaintext is correct Steps are shown in a systematic way using frequency analysis technique 2 Marks Plaintext is correct But steps are not shown in a systematic way using frequency analysis technique 1 Marks Plaintext is partially correct But steps are shown in a systematic way using frequency analysis technique 1 Marks Plaintext is not correct at all Or Plaintext is correct but frequency analysis technique is not used Or Not answered 0 Marks 2 Marks Question 2 Understanding the forward search attack on hash algorithm Step-by-step processes of forward search attack on hash algorithm are shown correctly All of the hash values are shown correctly Modified method is discussed with appropriate examples Step-by-step processes of forward search attack on hash algorithm are shown correctly All of the hash values are not shown or incorrect Modified method is discussed with appropriate examples Step-by-step processes of forward search attack on hash algorithm are shown correctly All of the hash values are shown correctly Modified method is not discussed with appropriate examples Or Step-by-step processes of forward search attack on hash algorithm are shown with Step-by-step processes of forward search attack on hash algorithm are shown with partially correct/ completely wrong values Modified method is not discussed with appropriate examples None of the steps are shown correctly Modified method is not discussed with appropriate examples Or Not answered 2 Marks , Page 7 of 8 2 Marks 1.5 Marks partially correct/ completely wrong values Modified method is discussed with appropriate examples 1 Marks 0.5 Marks 0 Marks Question 3 RSA Encryption algorithm Step-by-step processes of both encryption and decryption are shown All of the computations are shown correctly in detail 1.5 Marks Step-by-step processes of both encryption and decryption are shown Not all of the computations are shown correctly in detail 1 Marks Step-by-step processes of encryption are shown correctly However, decryption steps are not shown or incorrectly shown 0.75 Marks Step-by-step processes of encryption are shown that are partially correct/ completely wrong Or Only decryption steps are correct 0.5 Marks None of the steps are shown correctly Or Calculations are not shown in detail Or Not answered 0 Marks 1.5 Marks Question 4 Breaking RSA Encryption algorithm Step-by-step processes of both encryption and decryption are shown All of the computations are shown correctly in detail 2 Marks Step-by-step processes of both encryption and decryption are shown Not all of the computations are shown correctly in detail 1.5 Marks Step-by-step processes of encryption are shown correctly However, decryption steps are not shown or incorrectly shown 1 Mark Step-by-step processes of encryption are shown that are partially correct/ completely wrong Or Only decryption steps are correct 0.5 Marks None of the steps are shown correctly Or Calculations are not shown in detail Or Not answered 0 Marks 2 Marks Question 5 ElGamal Encryption algorithm Step-by-step processes of both encryption and decryption are shown All of the computations are shown correctly in detail 2 Marks Step-by-step processes of both encryption and decryption are shown Not all of the computations are shown correctly in detail 1.5 Marks Step-by-step processes of encryption are shown correctly However, decryption steps are not shown or incorrectly shown 1 Mark Step-by-step processes of encryption are shown that are partially correct/ completely wrong Or Only decryption steps are correct 0.5 Marks None of the steps are shown correctly Or Calculations are not shown in detail Or Not answered 0 Marks 2.5 Marks , Page 8 of 8 Question 6 Paillier Encryption algorithm Step-by-step processes of both encryption and decryption are shown All of the computations are shown correctly in detail 2 Marks Step-by-step processes of both encryption and decryption are shown Not all of the computations are shown correctly in detail 1.5 Marks Step-by-step processes of encryption are shown correctly However, decryption steps are not shown or incorrectly shown 1 Mark Step-by-step processes of encryption are shown that are partially correct/ completely wrong Or Only decryption steps are correct 0.5 Marks None of the steps are shown correctly Or Calculations are not shown in detail Or Not answered 0 Marks 2.5 Marks