## Transcribed 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

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;

}...