It took roughly seconds to test values... Since the sought-after exponent (if it exists) is no bigger than , a full brute-force search would "only" take roughly
Using this knowledge, you should be able to quite easily find the value of by:
Let's first find an such that (a reasonable thing to brute-force, since is only roughly half as long as ):
and the same thing mod :
Now we only need to recover , knowing that it satisfies the system of congruences: where and are the multiplicative orders of modulo and , respectively. To find these partial moduli, we can use the fact that:
which means that and (a quite general fact, actually).
This does not leave a lot of possibilities for and ...
Likewise, we find that the multiplicative order of modulo is the full :
Now we know that , so that we can write for some integer . If we look at this modulo , we get that we can now solve for : In this equation, we can divide both sides by (i.e. multiply by its modular inverse) – provided and share no common factor.
But that's not so bad, we can just divide everything by this common factor:
It's always good practice to check the result of such an involved computation...
The 1's should jump to the eye! What we observe is that : in other words, the multiplicative order of modulo is 5. The space of exponents cannot possibly offer much more than 2 bits of security! Said differently: it is very easy to compute discrete logarithms with this : given , just find its position in the 5-element list above (repeated thrice).
Well, since is of multiplicative order and we know that this multiplicative order must divide (because is prime), we can say for sure that , i.e. is of the form . We really cannot say much more than that without further information. In particular, the fact that one base mod is unsuitable for cryptography does not mean that it is the case for all bases mod .
Let's now start doing things properly and help Alice and Bob set up a secure shared secret. First:
Generating parameters can take a while (depending on your luck)... the good news is that we can safely reuse them so this is not the kind of operation that need to be performed very often in practice.
The multiplicative group mod is a cyclic group of order , which can be seen as a direct product of a cyclic group of order 2 and a cyclic group of prime order . Consequently: almost all (only 2 exceptions!) elements have multiplicative order or (in the second case, taking the square of the element would be an element of exact order , if needed).
Now for the Diffie-Hellman key agreement protocol: first Alice chooses a random exponent and computes the corresponding power, to be sent to Bob.
Bob does the same thing on his side:
Now Alice, knowing and , can compute her version of the shared secret:
Bob does the same thing using and :
We can check that Alice and Bob do indeed share a common secret (protected by the hardness of the base DLP):
We first import from the document the parameters that define the elliptic curve and the base point :
We may check that is indeed a point of prime (additive) order on :
Now let's consider the signature as a couple of points on and proceed to the actual decryption: