Cryptography

Part I: ECC

  1. Given an elliptic curve equation y2 = x3 + 25x + 17 (mod 29), answer the following questions.
(a)    For the point P = (4, 6) and Q = (5, 8), work out P+Q and 2P by hand and verify that P+Q and 2P are still on the curve.  

4 marks

(b)   Use maple to find all the points on this curve. How many points are there in the EC-based group and then plot all the points of this curve (you need to show your maple code of how you get the points).  

4 marks

(c)    If the curve is defined over real numbers, i.e., y2 = x3 + 25x + 17, plot the curve with -5<x<5 and -5<y<5.  

4 marks

 

  1. An important usage of the elliptic curves is to factorize big integers. Comparing to the difference of squares method, the advantage of EC-based factorization is that it can be parallelized This question asks you to practice integer factorization with EC-based method.

The smallest 3-digit prime is p = 101. And you need to find another prime q as follows. Take the last three digits of your student ID, and then run the maple command “nextprime()” and set the result as q. For example, if my ID is “7654321”, then the last three digits are “321”, then q = nextprime(321)= 331. Now, set n = p*q (note that the value q must be derived from your own student ID but not copy this constant 331).

Set up two elliptic curves randomly (so they are up to your own choice) and factorize the number n=p*q you obtained above. Observe your maple result, which curve gives you the factors p, q faster?

  10 marks

 

 

Part II: What is security and security in the NIST standard (HD tasks)

The importance of defining security is that, if you don’t know what security means, then you never know whether you have achieved your security goal or not in real applications. Let’s work through the strict definitions of security under different attack assumptions gradually and then see how the NIST standard applies the definitions (implicitly).

 

From a high-level-point of view, any private key cryptosystem  (for example, AES) can be defined as a collection of three algorithms (Gen, Enc, Dec) over the message space M (the symbol  means “belong to”):

  • Gen (key-generation algorithm): an algorithm produces the key k;
  • Enc (encryption algorithm): takes key k and message mÎM as input; outputs ciphertext c (c , C is the ciphertext space);
  • Dec (decryption algorithm): takes key k and ciphertext c as input; outputs m or “error”.

The correctness of Enc and Dec indicates that, for all mÎM and k output by Gen, Deck(Enck(m)) = m.

 

First, let’s consider the case of security definition under Ciphertext-Only-Attack (in short as COA, and COA is also called eavesdropping attack). It starts with a game between the adversary A and a Challenger C. The Challenger C is in charge of , so he can do encryptions and decryptions. And all the technique details of  are known to the Adversary A but the key, A wants to learn the information about plaintext as much as he can through interaction with C. In the case of COA, the interactions can be captured by this game:

COA-Game:

  • The attacker A chooses two message m0 and m1 of equal length, say n bits, and sends them both to C.
  • The challenger C tosses a coin and determines a random bit b (say for example, “head” as “1” and “tail” as “0”). Then he set cb = Enck(mb) and sends cb to A.
  • The attacker tries his best to work out b and outputs another bit b’. If b’ = b, then A wins this game.

We say the cryptosystem = (Gen, Enc, Dec) is perfect indistinguishable under the COA attack if the probability that A wins the above COA-Game is ½, formally, we denote this as

Prob(ACOA(b’= b)) = ½.

 

  1. Prove that the one-time-pad (OTP) is perfect secure under COA attack, i.e., the challenge ciphertext cb could come from either m0 or m1 with equal probability from the best of the attacker’s knowledge. 5 marks

The definition of perfect indistinguishable is too strong to be applied in real life, and so does the OTP. So, we need to relax it to a more realistic definition and it is called computational indistinguishable in the literature. Informally, computational indistinguishable means that we allow a tiny chance (for example, 1/2128) that the attacker A can tell the cb is from m0 or m1 better than random guessing. That is, the cryptosystem = (Gen, Enc, Dec) is computational indistinguishable under the COA attack if the probability that A wins the above COA-Game is ½ + neg. Formally, we denote it as

Prob(ACOA(b’= b)) = ½ + neg.,

where neg. is a negligible probability (say for example, 1/2128). In short, we write computational indistinguishable under the COA-Game as COA-IND.

  1. How computational indistinguishable under the COA can be achieved by modifying OTP? And why modifying it in the way you suggest can achieve COA-IND? 3 marks

 

So far, we have “strictly” defined computational secrecy under COA attack. But in reality, we need to consider Known-Plaintext Attack (KPA), Chosen-Plaintext Attack (CPA) and Chosen-Ciphertext Attack (CCA), because the attacker can be smarter than merely reading the ciphertexts in the internet.

  1. Considering the power of the attackers in KPA, CPA, and CCA assumptions (given in the lecture slides), define the KPA-Game, CPA-Game, CCA-Game and the associated computational indistinguishable definition under these attack games. 5 marks

Note, computational indistinguishability under CPA-Game is the minimum requirement for message confidentiality in real applications. And once again, we write computational indistinguishable under KPA-Game, CPA-Game, CCA-Game as KPA-IND, CPA-IND, and CCA-IND, respectively.

 

  1. Now, take a brief look at the NIST SP800-38A publication: Recommendation for Block Cipher Modes of Operation and list all the AES modes of encryption. From all these listed modes, which mode achieves COA-IND, which achieves KPA-IND, CPA-IND, and CCA-IND? 5 marks

Note: It is expected to list all the satisfied security definition for the mode of AES. For example, mode a of AES achieves COA-IND, CPA-IND, and CCA-IND (implicitly, it reflects the fact that mode a of AES fails to satisfy KPA-IND).

 

Order a unique copy of this paper
(550 words)

Approximate price: $22

Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

We value our customers and so we ensure that what we do is 100% original..
At Custom Writing, we believe in exemplary services that are fully geared toward customer satisfaction. That is why we don’t shy away from giving you the following guarantees;

Money-back guarantee

Trusting us with your work is the best decision you have made, our pleasure lies in seeing you satisfied at 100%. If in the rear chance it happens that you are not satisfied, then know that we will equally not be satisfied. But worry not, our 30 days- Money back guarantee is all you need and that is what we promise you..

Read more

Zero-plagiarism guarantee

We utilize profoundly equipped and gifted writers who produce unique papers liberated from any form of plagiarism. To guarantee this, we run all papers finished by our scholars through a Plagiarism checker to ensure uniqueness and originality. In any case, on the off chance that you have vulnerabilities about the originality or falsification of any paper we have finished and conveyed to you, please get in touch with us straight away. We will quickly investigate, and if the paper is seen as counterfeited, we will take suitable actions including but not limited to, revising the paper for free and in extreme cases we will activate the money back guarantee.

Read more

Free-revision policy

We have an obligation deliver great and specially composed assignments. Our revision strategy endeavors to ensure total client satisfaction, comfort, and a genuine feelings of serenity. We make minor updates and corrections to the underlying request as part of our continuous assistance. However, revisions should just incorporate changes and alterations that were not effectively met, in the underlying request and that are inside the rules as per the current request structure..

Read more

Privacy policy

Our client's Data is an Integral part of our business but clearly, we are not in the business of offering our clients' very own data to others. We realize that you care how your online data is utilized and shared, we equally value your trust that we will do so cautiously and sensibly. We Promise to ensure the security of your own data during transmission by utilizing encryption conventions and programming. Likewise assist us with securing your information by not sharing your passwords and usernames.

Read more

Fair-cooperation guarantee

In submitting a request with us, you consent to the services we give. We will strive to take the necessary steps to convey a far reaching paper according to your prerequisites. Equally we depend on your cooperation to guarantee that we convey on this order.

Read more

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency