QuestionQuestion

Transcribed TextTranscribed Text

Cryptography I Written Problems: There are three steps to follow for the written problems. Step 1: Do them as if they were homework assigned to be graded (ie, take them seriously and try to do a good job). Step 2: Self-assess your work by comparing your solutions to the solutions provided by me. Step 3: Revise your original attempts as little as possible to make them correct. Submit both your original attempt and your revision as separate files. Submit two files to DBInbox following the procedure documented on Piazza. The first file should be named exactly hw6.pdf and should be your homework solutions before looking at my solutions. The second file should be named exactly hw6revised.pdf and should be your homework solutions after looking at my solutions and revising your answers. NOTE: Ifyou wish to handwrite your solutions you may, but only if your handwriting is easy to read and the file you submit is less than IMB in size. 1) Every element of a group generates a subgroup, and the size of the groupis always a multiple of the size of the subgroup. For Z; and Zà determine the subgroups generated by each of its elements 2) Let's say Diffie-Hellman key-exchange is being done with generator g = 4 and prime p = 467. Note that g generates a subgroup of size 233. What is the key produced when the exponents chosen by the two parties are 400 and 134? What is the key produced when the exponents chosen by the two parties are 167 and 134? Why are the keys identical? 3) Let's say that you capture two ciphertexts encrypted using Elgamal in group 201 using g 3: (A 6,y = 17) and (A = 6.y = 25). Furthermore, you know that the first ciphertext is of plaintext x = 21. What is the second plaintext? Hint: The two A values can only be the same if the two e exponents are the same. 4) A small elliptic curve group has elements from ax b mod where a = 1, b 6 and p = 11. Let's say you choose 6 as your multiplier in a Diffie-Hellman key exchange and you receive (5,9) as your communication partner's contribution. What is the shared key generated? 5) Follow the method seen in class to generate a multiplicative group with a number of elements requiring 10 bits to represent (ie, 1000000000 to 1111111111) and identify a generator of the group. Note: At http: / (wol framalpha con you can type "11 prime?" to check if 11 is prime and you can check a generator with "order of 11 mod 29". 6) Elliptic curve groups are made from elements of l(x,y) Zp Zply = x3 + ax + b mod pf U (0) where p is prime, a and b are in Zp and (0) is the identity. All of these points do not necessarily make a cyclic group, but it is known that a subset of these points will make a cyclic group. Find an a, b, prime p, and generator (x,y) that generatesa group with aprime number of elements (including 0). I suggest you do this by writinga program that takes a, b and p.and for each ordered pair (x, in the above set, outputs all of the elements generated by (x.y). You can then look for a generated group of prime length. 7) In Elgamal encryption a public key consists of the specification of a group, a generator, and a Diffie-Helman contribution. Let's say that my public key specifies group Zip generator 2, and DH contribution 5. Tell me what grade you think you should get in this class A, B or C, and then encrypt it using my public key using A=2, B=3, C=4. If you need a random number during encryption, use 4. Programming: Read: Cprogram requirementsal http://krovetz.net/152/programs.html. A) Submit the following program using DBInbox and name the file hw6 c. You to writea program that reads seven integers a,b, from standard input (each value separated by a single space), and prints the result of adding elliptic curve points (x1,y1) and (x2, y2). If either of the points is not valid, you should output "Error" instead. If the sum is the identity, you should output "0". For example: > echo "2 2 17 5 1 5 1" I a out (6,3) > echo "2 2 17 5 1 5 16" I a out > echo "2 2 17 0 0 5 1" I out Error Your program does not need to be robust in the sense that your program may assume the input will be correctly formatted, p will bea prime, and all the inputs will be in Zp. You do not need to handle the identity "0" as an input. 2

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

/*
* File:   EllipticCurves.c
* Author:
*
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/**
* 2*9 = 18 mod 17 = 1
* @param val 9
* @param p 17
* @return 2
*/
int pow_1(int val, int p) {
int i;
for (i = 1; i < p; i++) {
if ((i * val) % p == 1) {
return i;
}
}
return val;
}

/**
* 5-6 = -1 → -1 + 17 = 16
* @param val -1
* @param p 17
* @return 16
*/
int negative(int val, int p) {
if (val >= 0) {
return val;
}
int tmp = val * (-1);
tmp = tmp % p;
tmp = tmp * (-1);
return tmp + p;
}

/**
* S = (y2 - y1) / (x2 - x1)
* @param x1
* @param y1
* @param x2
* @param y2
* @param p
* @return
*/
int S3(int x1, int y1, int x2, int y2, int p) {
int x = negative(x2 - x1, p);
int y = negative(y2 - y1, p);
return (y * pow_1(x, p)) % p;
}


/**
* Xresult = S^2 - (x1 + x2)
* @param s
* @param x1
* @param x2
* @param p
* @return
*/
int X3(int s, int x1, int x2, int p) {
int tmp = s * s;
int x = (x1 + x2);
if (x >= 0) {
tmp = tmp - x;
}
else {
tmp = tmp - negative(x, p);
}

if (tmp >= 0) {
return tmp % p;
}

return negative(tmp, p);
}

/**
* Yresult = S(x1 - Xresult) - y1
* @param s
* @param x1
* @param x
* @param y1
* @param p
* @return
*/
int Y3(int s, int x1, int x, int y1, int p) {
x = negative(x1 - x, p);
int tmp = s * x - y1;
if (tmp < 0) {
tmp = negative(tmp, p);
}
return tmp % p;
}


/**
* 3g
* @param a
* @param b
* @param p
* @param x1
* @param y1
* @param x2
* @param y2
*/
void G3(int a, int b, int p, int x1, int y1, int x2, int y2) {
int s = S3(x1, y1, x2, y2, p);
int x = X3(s, x1, x2, p);
int y = Y3(s, x1, x, y1, p);

printf("(%d,%d)", x, y);
}

/**
* S = (3x^2 + a) / (2y)
* @param x
* @param a
* @param y
* @param p
* @return
*/
int S2(int x, int a, int y, int p) {
int tmp = 3 * x * x + a;
tmp = negative(tmp, p);
int y_2 = 2 * y;
y_2 = pow_1(y_2, p);

return (tmp * y_2) % p;
}...

By purchasing this solution you'll be able to access the following files:
Solution.c.

$100.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats