# Tag Info

7

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$. Alternatively, if you ...

5

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.

2

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$. To clarify, there are no complex numbers used at all. The elliptic curve is over a quadratic extension of $F_p$, i.e. $K = F_{p^2}$, and a root $i$ of $x^2+1$ is chosen, so that elements of $K$ can be represented as uniquely as elements of $F_p \oplus i\... 2 Bruteforce appears to work well enough. The following Sage script finds an instance quickly: from sage.libs.fplll.fplll import FP_LLL from sage.libs.fplll.fplll import gen_uniform n = 5 # dimension q = 16 # size of matrix entries while True: M = gen_uniform(n, n, q) L = M.LLL(delta=0.999) S = FP_LLL(L).shortest_vector(algorithm='proved') ... 1 I think your proof of correctness may be hampered by the fact that you are setting the ciphertext to$(c_0, c_1) = (a, as + 2e + m)$when in fact the paper you cite sets the ciphertext to$(c_0, c_1) = (as + 2e + m, -a)$. You correctly state that decryption is then computed as$c_0 + c_1s \text{ (mod } 2)$. This reduces to$(as + 2e + m) + (-a)s \text{ (mod }...

1

I'ld say the answer is “no”. Usually you need to factor the modulus $N$ to break RSA. Now $N$ is not available to the attacker. So with a single plain text and cipher text I'm pretty sure the attacker has too little information to retrieve N or any other key component. Your pre-condition of not having the public key and therefore the modulus $N$ available ...

Only top voted, non community-wiki answers of a minimum length are eligible