0
$\begingroup$

Someone has incorrectly created a public/private key pair where $N$ (modulus) is a prime number.

This makes $p$ and $q$ trivial as they they are $n$ and $1$.

$d$ is solved from $d \cdot e = \bmod (p-1)(q-1)$ which becomes $d \cdot e = \bmod (n-1)$

I want to create the private key knowing this information but no PEM generators I've found correctly handle $p$ or $q$ being $1$ because when you need to find $e_1$ or $e_2$ you are looking for $d \bmod (p-1)$ and $(p-1)$ [or $q-1$] would be zero and it crashes.

I've tried python's RSA.construct and attempted to make a asn1.cnf but I am unable to calculated $e_1/e_2$.

I am confident it can be cracked though because RSA decrypt is just ciphertext to the $d$-power, $\bmod n$.

$\endgroup$
6
  • $\begingroup$ N being composite is necessary for security. Otherwise calculating decryption exponent from encryption exponent is trivial. Generate a new key pair buddy. $\endgroup$
    – DannyNiu
    Jan 4, 2019 at 6:55
  • $\begingroup$ What is the point? I don't know any RSA key gen that can output 1 as a prime! $\endgroup$
    – kelalaka
    Jan 4, 2019 at 7:06
  • $\begingroup$ Hint: $q$ is not $1$ (which is not a prime). $q$ is absent. $\endgroup$
    – fgrieu
    Jan 4, 2019 at 8:04
  • $\begingroup$ related Encryption and decryption example using the Pohlig-Hellman Exponentiation Cipher $\endgroup$
    – kelalaka
    Jan 4, 2019 at 16:21
  • $\begingroup$ What is the reason you want a private key? You already know how to decrypt/sign; is it because you need to hand it off to some software that expects a private key? $\endgroup$
    – poncho
    Jan 5, 2019 at 0:19

2 Answers 2

2
$\begingroup$

You already stated the answer yourself: You know $N$ (which is prime by your assumption) and from the public key $e$ you can compute $d = e^{-1} \bmod N-1$, e.g. using the EEA.

With this $d$ you can then decrypt any ciphertext $c$ into the corresponding $m = c^d \bmod N$.

$\endgroup$
1
  • 2
    $\begingroup$ Yes. Notably, anyone with $(N,e)$ can compute $d$ as $e^{-1}\bmod(N-1)$. With $e$ secret considered as the key, this is a symmetric scheme, called the Pohlig-Hellman exponentiation cipher. $\endgroup$
    – fgrieu
    Jan 4, 2019 at 15:59
2
$\begingroup$

FWIW, (desktop=Oracle) Java accepts and successfully uses a n,d-only/non-CRT-form RSA private key with an invalidly prime n, and it even generates and reads back what it claims to be a PKCS8/PKCS1 encoding (that could easily be PEMified) -- by setting the unused fields to zero! In my mind that takes Postelianism too far by half. But this does 'work', in the very limited sense of recovering the correct plaintext:

    BigInteger p = new BigInteger (1024, 128, new SecureRandom());
    BigInteger e = BigInteger.valueOf(3), d; 
    while( !p.subtract(BigInteger.ONE).gcd(e).equals(BigInteger.ONE) ) e.add(BigInteger.valueOf(2));
    d = e.modInverse(p.subtract(BigInteger.ONE));

    KeyFactory fact = KeyFactory.getInstance("RSA");
    PublicKey pub = fact.generatePublic(new RSAPublicKeySpec(p,e));
    System.out.println (DatatypeConverter.printHexBinary(pub.getEncoded()));
    PrivateKey prv = fact.generatePrivate(new RSAPrivateKeySpec(p,d));
    System.out.println (DatatypeConverter.printHexBinary(prv.getEncoded()));
    PrivateKey pr2 = fact.generatePrivate(new PKCS8EncodedKeySpec(prv.getEncoded()));

    Cipher ciph = Cipher.getInstance("RSA");
    ciph.init(Cipher.ENCRYPT_MODE, pub);
    byte[] enc = ciph.doFinal("TEST".getBytes()); // FOR TEST charset 
    ciph.init(Cipher.DECRYPT_MODE, pr2);
    System.out.println (new String (ciph.doFinal(enc))); // doesn't matter 

-->
30819D300D06092A864886F70D010101050003818B0030818702818100C906C38BD8F2790F34D7DD453F8D8F26309E13748F6C394EF9F3698E35089D0447987DAF31AA207203358F27E9DF009BFBAA530386C30188076A9A085FA81E48087EB9817DDBBBFE7878B36DF7C6B74DCAC16E5492F2DC2F346E6C2E03585D59CDF2F918EBED73CA8F6B5C449F68A95EECB5B0798B89254F72E077BAAEF4A583020103
30820137020100300D06092A864886F70D0101010500048201213082011D02010002818100C906C38BD8F2790F34D7DD453F8D8F26309E13748F6C394EF9F3698E35089D0447987DAF31AA207203358F27E9DF009BFBAA530386C30188076A9A085FA81E48087EB9817DDBBBFE7878B36DF7C6B74DCAC16E5492F2DC2F346E6C2E03585D59CDF2F918EBED73CA8F6B5C449F68A95EECB5B0798B89254F72E077BAAEF4A583020100028181008604825D3B4C50B4CDE53E2E2A5E5F6ECB140CF85F9D7B89FBF79BB4235B13582FBAFE74CBC6C04C0223B4C54694AB12A7C6E20259D7565AAF9C66B03FC569855AFF265653E7D2A9A5A5CCF3FA847A33DC80F43861F73D74CD9EF2C957903E3BDEA1FB65F29E4D31B4F23D8314F070E9F323CAFBB25B6E34F7404FD1C9F86E57020100020100020100020100020100
TEST

It is course totally insecure, as already described.

$\endgroup$
1
  • $\begingroup$ Postelianism? Oh, I got it: "Perhaps his most famous legacy is from RFC 760, which includes a robustness principle often called Postel's law: "an implementation should be conservative in its sending behavior, and liberal in its receiving behavior" (reworded in RFC 1122 as "Be liberal in what you accept, and conservative in what you send"). " As a cryptographer and security professional I'm not a fan. Don't allow complexity in your system, I tells you. $\endgroup$
    – Maarten Bodewes
    Jan 5, 2019 at 13:09

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.