Generate Rsa Public Key from Modulus and Exponent

Generate RSA Public Key from Modulus and Exponent

If you want to create a .PEM format you need to base64 encode the output from the berData method. You also need to add the header and footer lines.

Test data and code, see the end of the answer for bytesFromHexString:

NSString *modulusString =  @"c19bccae1e67743fab1c978f03122fb1a78ef05d565a2964728062ad0365e4751b8253df5fd13ab4ecb95c81ff17b91f969e4fb3d8274c30533338684278f6e5548027df775c055943a24a4117b0274c296c68b722c71670d4b21489a3da05d37ba06f2fb771b671a2c746bae4a049dc718fba19a75f1fb8ae1dd715b33d66a3";
NSString *exponentString = @"010001";

NSData *pubKeyModData = bytesFromHexString(modulusString);
NSData *pubKeyExpData = bytesFromHexString(exponentString);
NSArray *keyArray = @[pubKeyModData, pubKeyExpData];

//Given that you are using SCZ-BasicEncodingRules-iOS:
NSData *berData = [keyArray berData];
NSLog(@"berData:\n%@", berData);

NSString *berBase64 = [berData base64EncodedStringWithOptions:0];
NSString *preamble = @"-----BEGIN CERTIFICATE REQUEST-----";
NSString *postamble = @"-----END CERTIFICATE REQUEST-----";
NSString *pem = [NSString stringWithFormat:@"%@\n%@\n%@", preamble, berBase64, postamble];
NSLog(@"pem:\n%@", pem);

Output with test data:

berData:
30818802 8180c19b ccae1e67 743fab1c 978f0312 2fb1a78e f05d565a 29647280 62ad0365 e4751b82 53df5fd1 3ab4ecb9 5c81ff17 b91f969e 4fb3d827 4c305333 38684278 f6e55480 27df775c 055943a2 4a4117b0 274c296c 68b722c7 1670d4b2 1489a3da 05d37ba0 6f2fb771 b671a2c7 46bae4a0 49dc718f ba19a75f 1fb8ae1d d715b33d 66a30203 010001

pem:
-----BEGIN CERTIFICATE REQUEST-----
  MIGIAoGAwZvMrh5ndD+rHJePAxIvsaeO8F1WWilkcoBirQNl5HUbglPfX9E6tOy5XIH/F7kflp5Ps9gnTDBTMzhoQnj25VSAJ993XAVZQ6JKQRewJ0wpbGi3IscWcNSyFImj2gXTe6BvL7dxtnGix0a65KBJ3HGPuhmnXx+4rh3XFbM9ZqMCAwEAAQ==
-----END CERTIFICATE REQUEST-----

Convert hex-ascii to data:

NSData* bytesFromHexString(NSString * aString) {
    NSString *theString = [[aString componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]] componentsJoinedByString:nil];

    NSMutableData* data = [NSMutableData data];
    int idx;
    for (idx = 0; idx+2 <= theString.length; idx+=2) {
        NSRange range = NSMakeRange(idx, 2);
        NSString* hexStr = [theString substringWithRange:range];
        NSScanner* scanner = [NSScanner scannerWithString:hexStr];
        unsigned int intValue;
        if ([scanner scanHexInt:&intValue])
            [data appendBytes:&intValue length:1];
    }
    return data;
}

How to create public RSA key using modulus and exponent for Sign In with Apple?

To generate public key from the exponent and modulus, they need to be transformed to BigInteger, and then KeyFactory from Java security can be used.

For example:

  String modulus = "modulus from Apple";
  String exponent = "exponent from Apple";
  byte[] modulusByte = Base64.getUrlDecoder().decode(modulus);

  BigInteger modulusAsBigInt = new BigInteger(1, modulusByte);
  byte[] exponentByte = Base64.getUrlDecoder().decode(exponent);
  BigInteger exponentAsBigInt = new BigInteger(1, exponentByte);

  RSAPublicKeySpec spec = new RSAPublicKeySpec(modulusAsBigInt, exponentAsBigInt);
  KeyFactory factory = KeyFactory.getInstance("RSA");
  PublicKey pub = factory.generatePublic(spec);

Rebuild of a RSA Private Key from modulus & exponent fails

This is the modified version of my program that has the additional code from @President James K. Polk (see link of Topaco above). Even if the rebuild CRT-private key is now longer than the rebuild Private Key it does not match the original (encoded)
private key. As I'm using the encoded private and public keys for a PHP RSA encryption/decryption there is the funny fact that the original keys run successfully but the rebuild ones not...

This version uses a 512 bit keylength that is insecure is for demonstration only (to keep the keys shorter).

result:

Rebuilding of a RSA PrivateKey from modulus & exponent
privateKey equals rebuild: false
publicKey equals rebuild: true
privateKey original    encoded: 30820154020100300d06092a864886f70d01010105000482013e3082013a020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b0203010001024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441022100e3b260dcced139557591b609470d8f0e518351a97bdbf26a59a41140a68778e9022100b8c1ab98f7b7280bd4b53fa3ed09c11d12aec9873d8a4a05e43152bc0d3346e302201d801ff29bcd19bb8bc6fc29c98de529fabfa3d5ec993b9831d302f5385e36f90220009e0d0fbecc2ae3173bdfd1916a35edfdf0fd95691c3c3116d91f58a786a357022100a810110da3d9d4de34e64029a3535368bb52e7b81055239cb4443d5172aea8e5
privateKey rebuild     encoded: 3081b2020100300d06092a864886f70d010101050004819d30819a020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b020100024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441020100020100020100020100020100
privateKey rebuild CRT encoded: 30820153020100300d06092a864886f70d01010105000482013d30820139020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b0203010001024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441022100b8c1ab98f7b7280bd4b53fa3ed09c11d12aec9873d8a4a05e43152bc0d3346e3022100e3b260dcced139557591b609470d8f0e518351a97bdbf26a59a41140a68778e90220009e0d0fbecc2ae3173bdfd1916a35edfdf0fd95691c3c3116d91f58a786a35702201d801ff29bcd19bb8bc6fc29c98de529fabfa3d5ec993b9831d302f5385e36f9022030634f5490e1bb4b56a68715d3c80a92c6e8f7c9f3e79f125a9969e6fc095705

code:

import java.math.BigInteger;
import java.security.*;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.RSAPrivateCrtKeySpec;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;
import java.util.Arrays;

public class RebuildRSAPrivateKey2 {
    public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException {
        System.out.println("Rebuilding of a RSA PrivateKey from modulus & exponent");
        // rsa key generation
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        //kpGen.initialize(2048, new SecureRandom());
        kpGen.initialize(512, new SecureRandom()); // don't use 512 bit keys as they are insecure !!
        KeyPair keyPair = kpGen.generateKeyPair();
        // private key
        PrivateKey privateKey = keyPair.getPrivate();
        // get modulus & exponent
        RSAPrivateKey rsaPrivateKey = (RSAPrivateKey) privateKey;
        BigInteger modulus = rsaPrivateKey.getModulus();
        BigInteger privateExponent = rsaPrivateKey.getPrivateExponent();
        // rebuild the private key
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(modulus, privateExponent);
        PrivateKey privateKeyRebuild = keyFactory.generatePrivate(rsaPrivateKeySpec);
        System.out.println("privateKey equals rebuild: " + Arrays.equals(privateKey.getEncoded(), privateKeyRebuild.getEncoded()));
        // public key
        PublicKey publicKey = keyPair.getPublic();
        // get modulus & exponent
        RSAPublicKey rsaPublicKey = (RSAPublicKey) publicKey;
        BigInteger modulusPub = rsaPublicKey.getModulus();
        BigInteger publicExponent = rsaPublicKey.getPublicExponent();
        // rebuild the public key
        KeyFactory keyFactoryPub = KeyFactory.getInstance("RSA");
        RSAPublicKeySpec rsaPublicKeySpec = new RSAPublicKeySpec(modulusPub, publicExponent);
        PublicKey publicKeyRebuild = keyFactory.generatePublic(rsaPublicKeySpec);
        System.out.println("publicKey equals rebuild: " + Arrays.equals(publicKey.getEncoded(), publicKeyRebuild.getEncoded()));
        System.out.println("\nprivateKey original    encoded: " + bytesToHex(privateKey.getEncoded()));
        System.out.println("privateKey rebuild     encoded: " + bytesToHex(privateKeyRebuild.getEncoded()));
        RSAPrivateKey rsaPrivateKeyRebuild = (RSAPrivateKey) privateKeyRebuild;
        RSAPublicKey rsaPublicKeyRebuild = (RSAPublicKey) publicKeyRebuild;
        RSAPrivateCrtKey rsaPrivateCrtKey = createCrtKey(rsaPublicKeyRebuild, rsaPrivateKeyRebuild);
        System.out.println("privateKey rebuild CRT encoded: " + bytesToHex(rsaPrivateCrtKey.getEncoded()));
    }

    /**
     * https://stackoverflow.com/questions/43136036/how-to-get-a-rsaprivatecrtkey-from-a-rsaprivatekey
     * answered Mar 31 '17 at 18:16 President James K. Polk
     * Find a factor of n by following the algorithm outlined in Handbook of Applied Cryptography, section
     * 8.2.2(i). See http://cacr.uwaterloo.ca/hac/about/chap8.pdf.
     *
     */

    private static BigInteger findFactor(BigInteger e, BigInteger d, BigInteger n) {
        BigInteger edMinus1 = e.multiply(d).subtract(BigInteger.ONE);
        int s = edMinus1.getLowestSetBit();
        BigInteger t = edMinus1.shiftRight(s);

        for (int aInt = 2; true; aInt++) {
            BigInteger aPow = BigInteger.valueOf(aInt).modPow(t, n);
            for (int i = 1; i <= s; i++) {
                if (aPow.equals(BigInteger.ONE)) {
                    break;
                }
                if (aPow.equals(n.subtract(BigInteger.ONE))) {
                    break;
                }
                BigInteger aPowSquared = aPow.multiply(aPow).mod(n);
                if (aPowSquared.equals(BigInteger.ONE)) {
                    return aPow.subtract(BigInteger.ONE).gcd(n);
                }
                aPow = aPowSquared;
            }
        }
    }

    public static RSAPrivateCrtKey createCrtKey(RSAPublicKey rsaPub, RSAPrivateKey rsaPriv) throws NoSuchAlgorithmException, InvalidKeySpecException {
        BigInteger e = rsaPub.getPublicExponent();
        BigInteger d = rsaPriv.getPrivateExponent();
        BigInteger n = rsaPub.getModulus();
        BigInteger p = findFactor(e, d, n);
        BigInteger q = n.divide(p);
        if (p.compareTo(q) > 0) {
            BigInteger t = p;
            p = q;
            q = t;
        }
        BigInteger exp1 = d.mod(p.subtract(BigInteger.ONE));
        BigInteger exp2 = d.mod(q.subtract(BigInteger.ONE));
        BigInteger coeff = q.modInverse(p);
        RSAPrivateCrtKeySpec keySpec = new RSAPrivateCrtKeySpec(n, e, d, p, q, exp1, exp2, coeff);
        KeyFactory kf = KeyFactory.getInstance("RSA");
        return (RSAPrivateCrtKey) kf.generatePrivate(keySpec);
    }

    private static String bytesToHex(byte[] bytes) {
        StringBuffer result = new StringBuffer();
        for (byte b : bytes) result.append(Integer.toString((b & 0xff) + 0x100, 16).substring(1));
        return result.toString();
    }
}

Get RSA public key from private key modulus and private exponent

Generally the RSA private key contains the following data:

• n - semiprime modulus

• d - private exponent

• p & q - prime factors of n

• e - public exponent

At a minimum, the private key must contain:

• n and d.

So to answer your questions:

can I get the associated public key modulus?

Yep, you already have it. It's the same n used by the private key.

can I get the public exponent?

Not easily without knowing p and q, though you can guess at it, it's nearly always a small prime, most commonly either 3 or 65537.

Try both and check if ciphertext is valid.

I have a RSA public key exponent and modulus. How can I encrypt a string using Python?

With PyCrypto, you can use the Crypto.PublicKey.RSA.construct() function. You'll need to convert the modulus to an int. Here's an example (assuming big-endian):

from Crypto.PublicKey.RSA import construct

e = int('10001', 16)
n = int('d0eeaf...0b6602', 16)  #snipped for brevity
pubkey = construct((n, e))

Then you can do the usual things (like encrypt) with the key:

from Crypto.Cipher import PKCS1_OAEP

cipher = PKCS1_OAEP.new(pubkey)
ciphertext = cipher.encrypt(b'abcde')

Edit: Note that your public exponent, 10001, is mostly likely hexadecimal. This would correspond to the common public exponent 65537. I've updated the above to reflect that.

---

Related Topics