1
$\begingroup$

I'm trying to understand the following signature scheme (Camenisch-Lysanskaya):

Key generation: $n = pq$ special RSA modulus, $a, b, c \in QR_n$. $PK = (n, a, b, c), SK = p$.

Signing algorithm:

  • $m$ message.
  • $e$ random prime number (with some for this question unimportant length restriction).
  • $s$ random number with very big length (unimportant for my question).
  • Compute $v^e \equiv a^m b^s c \bmod n$. Output $(e,s,v)$.

Verification algorithm: Check that $v^e \equiv a^m b^s c \bmod n$ and check the length restriction of $e$.

I don't see why this is a valid signing algorithm. The secret key is not used for signing (or calculating $e$ or $s$). So everyone could make a signature like this and not just the one who created the public key.

Edit: If I understand it right, it's all about the hard computation of a $v$ and $e$ if you just have $a^m b^s c$. But how does it help there to know the factorization of $n$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$
  • Compute $v^e \equiv a^m b^s c \pmod n$. Output $(e,s,v)$.

This should perhaps read:

  • Solve $v^e \equiv a^m b^s c \pmod n$ for $v$. Output $(e,s,v)$.

If you can solve $v^e \equiv u \pmod n$ for $v$ without using $p$ in general, you have found a major breakthrough in cryptanalysis!

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes that is, what I also read. But how does it help for the calculation to know the factorization of $n$? $\endgroup$
    – jhnn
    Mar 25, 2019 at 16:07
  • $\begingroup$ Or the other way around: why can I solve the factorization problem if I would have found some $e, v$ to a given $u, n$ s.t. $v^e \equiv u \bmod n$? $\endgroup$
    – jhnn
    Mar 25, 2019 at 16:11
  • $\begingroup$ How does knowing the factorization of $n$ help to find $v$? If you know $p$ and $q$ so that $n = pq$, you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ for $d$ and compute $v \equiv (a^m b^s c)^d \pmod n$ as in RSA. $$$$ How does finding $v$ help to find the factorization of $n$? We don't know, except in the cases of even exponents, since knowing two distinct square roots $y$ and $y'$ of a common square $x\equiv y^2\equiv (y')^2\pmod n$ so that $(y+y')(y-y')=kn$ for some $k$ reveals the factorization of $n$ by $\gcd(n, y \pm y')$. $\endgroup$
    – Squeamish Ossifrage
    Mar 25, 2019 at 16:24
  • $\begingroup$ From a cursory glance, the security of this system seems to rely on the RSA problem, not directly on factorization. The RSA problem—inverting $x^e \bmod n$ for uniform random $x$ and appropriate choice of $e$—is certainly not harder than factoring, but it may be easier. $\endgroup$
    – Squeamish Ossifrage
    Mar 25, 2019 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.