In ECRSA cryptosystem, I want to know the feasible attacks. For illustrations we have two prime $p$ and $q$ such that $p \equiv 2 \pmod 3$, $q \equiv 2 \pmod 3$ and generate key pair as follows: $$n = pq, \quad \lambda = \operatorname{lcm}(p+1,q+1), \quad d = e^{-1} \pmod \lambda $$ Now $(n, e)$ is public and $(n, d)$ is private key.

For given message $m$, we present $m$ as a pair of integers $(m_1, m_2) \pmod n$ and regards it as a point $P$ on the elliptic curve $E$ given by $y^2 = x^3 + B \pmod n$, such that $B = - m_1^3 + m_2^2$.

For encrypt message $m$, add $P$ to itself $e$ times on E to obtain $C = e.P$

Source: Zhaohui Cheng's Simple Tutorial on Elliptic Curve Cryptography (December 2004).

  • $\begingroup$ Is the curve-order public? $\endgroup$ – SEJPM Jun 26 '16 at 13:14
  • $\begingroup$ So I presume that ECRSA is just the scheme displayed here? I don't see any references about it on the internet... $\endgroup$ – Maarten Bodewes Jun 26 '16 at 13:18
  • $\begingroup$ @MaartenBodewes After a quick glance, it looks like the system described in this paper. $\endgroup$ – yyyyyyy Jun 26 '16 at 14:23
  • 2
    $\begingroup$ My first impression is that the key size must be RSA like, e.g. 2048 bits. This renders the ECC advantage of having small key sizes worthless. So, despite security, what is the advantage of this crypto system? $\endgroup$ – user27950 Jun 26 '16 at 19:24
  • 1
    $\begingroup$ Worse than possible failing inversions, which would reveal the factorization, is the fact that singular curves with $B = 0$ are allowed. In that case, decryption doesn't work due to the different order $pq$ than the $(p+1)(q+1)$ assumed. $\endgroup$ – Samuel Neves Jun 27 '16 at 0:42

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.