# Schnorr signature security level as compared to AES/RSA

As per the Schnorr's original paper (1991),

The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by known methods. For this we choose $q > 2^{2t}$ and $p$ such that $2^t$ is about $e^{\sqrt{\ln(p)\ln(\ln(p))}}$. ... For $p > 2^{512}$ and $q > 2^{140}$ the discrete logarithm problem requires at least $2^{72}$ steps by known algorithms.

Now I have three questions regarding this.

1. How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$?
2. What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$ bits and $q$ of $512$ bits?
3. Since Schnorr is finite field signature scheme, what is the 'field size', 'group size' and 'subgroup size' in case of schnorr signature scheme?

How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$?

Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability.

Note that Schnorr's complexity estimate for the field is based on the Index-Calculus Algorithm and doesn't yet take into account the Number Field Sieve (original paper as PDF) against discrete logarithms, which would give a different expression, namely $L_p[1/3,3^{2/3}]=e^{(3^{2/3}+o(1))(\ln p)^{1/3}(\ln\ln p)^{2/3}}$, that would yield a much lower required attack complexity.

What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$ bits and $q$ of $512$ bits?

$q$ is the subgroup order and if you get a 512-bit subgroup you'll have roughly 256-bit security for this subgroup. $p$ is the field prime and with it being 1024-bit, you'll get roughly 80-bit security against NFS-based attacks. So the answer is: A 1024-bit RSA modulus will have a comparable security along with AES-128, where 48 key bits are constant zero'ed out. Note that just plugging-in $2^{1024}$ into the complexity equations is a dangerous business, as $o(1)$ hides an implementation-dependenant (constant) factor that was not accounted for. Rather you need a concrete data point as a basis for further extrapolation. Here's a more detailed treatment of keylengths: (simple) (complex) by Lenstra and Verheul.

Since Schnorr is finite field signature scheme, what is the 'field size', 'group size' and 'subgroup size' in case of schnorr signature scheme?

$p$ is the field prime and its bitlength is the field size.
$q$ is the subgroup order and its bitlength is the subgroup size.
There's no relevant "group size" in this case (maybe one could say that's equivalent to the field size though)

• I'm not 100% sure I got everything right, so complain as usual if something is wrong ;) – SEJPM Apr 11 '16 at 20:11
• I didn't get why you told to get log to base 2 (ln means base should be e). If I'm right, you considered lowest of 256 and 80-bit (i.e. 80-bit) as resultant security level. But as per schnorr's formula 1024-bit should give security level of 98-bits. What is the formula to calculate security level against NFS-based attacks in case of p? – mk09 Apr 12 '16 at 8:32
• Now I understood what you intended to say when you told to take log to base 2. Its for final result of exponentiation which will give value of t directly. Please clarify about my second doubt in above comment. – mk09 Apr 12 '16 at 8:42
• @Maheshk, I used "take the logarithm to the base two for better readability." so you see $66$ and not $7.3789*10^{19}$ which is rather unhelpful in cryptography, the result of the logarithm will also be the $t$ value. I've added some treatment of NFS run-time. – SEJPM Apr 12 '16 at 20:55
• I think in equation of Lp[1/3, 3^2/3], power of ln(p) should be 1/3 and power of ln(ln(p)) should be 2/3 as per formula of Lp in ccrwest.org/gordon/log.pdf. One more thing, I didn't find anything on O(1). How can I find value of O(1) based on my implementation? – mk09 Apr 13 '16 at 10:30