0
$\begingroup$

I feel DSA is vulnerable if k is randomly selected over a small set, example, {1,2,...,2^16 -1}.

I am trying to come up with a program where I assume I have the public parameters (p,q,g) , public key : y, message m and its signature pair (r,s) signed with x and k. We also have hash value h (where h=SHA-1(m)).

I want to construct an attack where I can get k by brute force and then use it to get x from s. How do I code an efficient program for this attack ?What modular arithmetic do I need to perform to make the program as efficient as possible ? What crypto libraries are the best for this sort of brute force attack ?

Improve this question
$\endgroup$
5
  • $\begingroup$ Your feeling is right. Donald E. Knuth said "Premature optimization is the root of all evil (or at least most of it) in programming". Use a language with built-in large-integer arithmetic: Python (open path to speed gain with gmpy or SymPy); SageMath, PARI/GP, Mathematica… Java+BigInteger, C(++)+GMP (likely performance king). For the method: write down the equations linking knowns and unknowns, and ponder. You (not we) do the homework. If you want hints, put these equations in the question (see this for how), and tell where you are stuck. $\endgroup$ – fgrieu♦ Nov 29 '20 at 9:54
  • $\begingroup$ Thanks for the help. The homework says find a vulnerability in DSA and write a program to exploits it. My program takes upwards of a couple hours, when I ran this by a TA, he said, it should take seconds at max. He said he is not giving any further information. I need to re-do the math, that's what I understood but I have no clue how to. What's a good starting point ?? $\endgroup$ – confused andstuck Nov 29 '20 at 11:29
  • $\begingroup$ Again: If you want hints, at least write down the equations linking knowns and unknowns in the question. There's a good chance that will be enough to get you unstuck. At worse, it won't, but we'll be able to give you hints using the notation you use (that's no promise it will happen, but there's a chance). $\endgroup$ – fgrieu♦ Nov 29 '20 at 12:07
  • $\begingroup$ I get what you are saying, but I felt writing equations, mentioning what I did and where I am stuck would be too direct, I dont want to get in trouble by asking something that can be a potential honor code violation. $\endgroup$ – confused andstuck Nov 29 '20 at 15:54
  • $\begingroup$ Indeed you should not violate an honor code, but I can't see how adding these equations could be more of a violation than what you already did. Hint: if you really have a working program but it "takes upwards of a couple hours" for $1\le k<2^{16}$: perhaps you are computing $g^k\bmod p$ in a naive way. A better way uses $<2\log_2(k)$ modular multiplications. Another option is computing all $g^k\bmod p$ for $1\le k<n$ with $\le n$ modular multiplications. $\endgroup$ – fgrieu♦ Nov 29 '20 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.