ASSIGNMENT 3 Marks are given for explanations. This assignment is composed of two parts. Part I is about the elliptic curve cryptography and Part II is about the definition of security. 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<><5 and=""><><5. 4 marks 2. 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 easily. 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 mm 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 mm 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)) = ½. 3. 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. 4. 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. 5. considering the power of the attackers in kpa, cpa, and cca assumptions (given in the lecture slides of week 1a), 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. 6. 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). total: 40 marks 4="" marks="" 2.="" 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="" easily.="" 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="" mm="" 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="" mm="" 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))" =="" ½.="" 3.="" 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.="" 4.="" 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.="" 5.="" considering="" the="" power="" of="" the="" attackers="" in="" kpa,="" cpa,="" and="" cca="" assumptions="" (given="" in="" the="" lecture="" slides="" of="" week="" 1a),="" 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.="" 6.="" 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).="" total:="" 40="">