Chapter 2

From my understanding, many questions in this chapter is more about the theory behind everything. There isn't way too many technical stuff about it. I will update this page with better information in the future, hopefully.

Note from the future: Hurray! I actually remembered to update it.

For now, there is a program below to help you with the discrete logarithm problems. Just give it a base number, the result you are looking for and a modulo value. It uses the collision, or meet-in-the-middle algorithm that was given in the textbook.

Even if we didn't have a good algorithm for this, we already have a really fast way of computing powers of a number in modulo p. We could theoretically try every possible value, and it would take us linear time. However, there is no need. Some brilliant mathematician out there already had a convenient way of doing it, isn't that nice ? You may try it below.

It is also possible to use this to find where an element starts to repeat itself, if you specify a result value of 1. Enjoy!

Solve g^x = h mod(p)

g (base): h (result): p (modulo):

Here is the program behind this operation, for the interested reader.

// We defined this function on Chapter 1, if you have no idea // you are encouraged to check it out function square_n_multiply($N, $g, $A){ $a = $g; $b = 1; //setting necessary variables while($A > 0){ if(($A % 2) == 1) $b = ($b * $a) % $N; // We will not be storing different values // of $A , therefore we do the necessary // operation on the fly $a = ($a * $a) % $N; // updating 'A' for the next cycle $A = floor($A / 2); } return $b; } function discrete_logarithm($g, $h, $N){ $n = 1 + floor(sqrt($N)); // allocating memory to store values in our array $list_462 = array_fill(0, $N, 0); // Store values of the form g^(1*i)..... g^(n*i) for ($i = 1; $i <= $n; $i++){ $list_462[square_n_multiply($N, $g, $i * $n)] = $i; } for ($i = 0; $i < $n; $i++){ // Now , we calculate different values of h * g^(j) // and see if there is an intersection or not // We are interested in the values up to N - 1, as there are infinitely many // solutions for any possible solution. So we take modulo N , at the end $current_element = (square_n_multiply($N, $g, $i) * $h) % $N; // If there is an intersection, the value corresponding to $current_element // in our list, namely list_462, should be a positive value. if ($list_462[$current_element] > 0){ // In this environment, calculating h * g^(-j) ' s were cumbersome, for that reason // we calculate elements of the form hg^(j*n) above , for this little sign alteration // our solution becomes x = jn - i , if you are following the textbook , do not get confused // they essentially create the same set of elements, as we are in modulo N $answer = $list_462[$current_element] * $n - $i; // We expect the answer to be inside the range [1, N-1]. So, we return // the found answer only if that criteria is met if (!($answer >= $N)) return $answer; } } // After the loop above is completed, if we have not returned a value yet, then // there are no solutions to begin with, it is an impossible case return -1; }

Question 2.3

Question 2.4

With the help of the square_n_multiply program we defined in Chapter 1, it is easy to see that 2⁹⁴⁷ = 177 (mod 1373), which is denoted by A (aka. Alice's public key).

According to the given information, Alice then encrypt the plaintext m = 583 and she uses the random value k = 877. Then, according to Elgemal she needs to calculate c₁ = g^k = 2⁸⁷⁷ (mod 1373) and c₂ = m.B^k = m.B⁸⁷⁷ (mod 1373). After calculation we see that c₁ = 719 and c₂ = m.644 (mod 1373), which at the end simplifies to c₂ = 375462 = 623 (mod 1373). Hence, Alice sends bob the pair (719, 623).

For part (c), Alice decides to use a new secret key 299, and her public key becomes 34. She gets an encrypted message from Bob, the pair (661, 1325). Remember that 661 = 2^k mod(1373) where k is a randomly chosen number. Using the calculator above we see that 2⁵⁶⁶ = 661 mod(1373). We also know that 1325 = m . 34⁶⁶¹ mod(1373) = m . 201 mod(1373). Therefore, all we need to calculate is 1325 . 201^-1 mod(1373). This is quite easy using our fast powering algorithm or even extended euclidean algorithm. 1325 . 201^-1 = 1325 . 929 = 1230925 = 717 mod(1373).

Observe that we did not even use Alice's private key to decrypt this message, because finding the random number k was quite simple. This is a representation of what Eve(the third party) would do if she has the intention to decrypt our message.

The part (d) is also very similar to this. Using the meet-in-the-middle algorithm above you may find the necessary random value k, and help Eve out.

Question 2.10

The idea behind the system in this question is simple. The only number that is public is the modulo value 32611. Alice has a message that he wants to send to Bob, but Bob has no public key. Alice only has her own private key, the only thing she can do here is to encrypt it using her private key 3589 and send it to Bob. Right now Eve knows the fact that m^a = 15950. Bob receives this message but he can not decrypt it, because he has no clue what Alice's secret key is, and the message he received is not encrypted with his private key in mind.

At this stage, Bob does the only logical thing, and encrypts the message he received with his private key. On the transfer Eve sees that v = m^{(4037 . 3589)} = m^(a.b) = 15422. Eve does not have the private key values 4037 and 3589, but using the two equations she has, if she can calculate for which value 15950^x = 15422 is satisfied, then she basically finds the value b, which is Bob's private key. In the optimum circumstances this should not be easier than solving the DLP problem. However, if the order of 15950 is easily decomposable into small primes, then by Pohlig-Hellman's p-1 algorithm the value x can be found easily. Therefore, Bob needs to keep an eye out for the possibility that the value he calculated is not vulnerable to such an attack.

This makes the message exchange between Alice and Bob a little more complicated, not only they need to transfer multiple data just to send one message but also there are other variables they need to be aware of. The third party Eve, has more information to decrypt the message.

Now, the value 15422 has reached Alice. There is one big problem. She has no way of understanding whether this came from Bob. Bob has no public information available and the algorithm does not include a signing method. Therefore, Eve could act like the (wo)man-in-the-middle and intercept the messages on their way. This is also quite problematic.

Let us assume that everything went according to the plan. Alice has the plaintext value 11111 and she knows that 11111^{(3589 . 15619)} = 1 mod(32611), this is because 3589 . 15619 = 1 mod(32610). Remember that a value to the power p-1 is actually 1, by Fermat's theorem. So, by taking powers of 11111 by 3589 and 15619 respectively, Alice basically made no changes to 11111, which is the plaintext message she wanted to send. She made it more obscure by first taking its 3589th power, and then se reverted those changes back, so that Bob can now actually read the message.

Bob knows that 4037 . 31883 = 1 mod(32610). He then makes the necessary operation to revert his changes back to the original. At the end both Alice's and Bob's effect on the plaintext is neutralized. What is left is the one and only m.

As you probably noticed know, the attack surface of this algorithm is quite big, considering Alice and Bob exchanges two pieces of data for one single message. Both Alice and Bob needs to be extra careful about the information they are sending. There is one more reverse effect of this. When Bob decrypts the message and finds 11111, he also knows from the previous steps that 11111^a = 15950, where a is the private key of Alice, which is quite funny. Bob can become Eve if he wants to.

The same is also true for Alice, she knows from all these transactions that 11111^b = 27257, which is what Bob send to Alice as a response. If she is able to solve this, she can obtain Bob's private key.

I feel like you get the point, this algorithm would work, but the attack surface is much larger, it is more costly and also requires extra attention to the value being transmitted. Depending on how often Alice and Bob can reach each other, sending one message will require multiple transactions of arbitrary data, which as a result makes this much inferior compared to Elgemal.