Samsung .Cert File - Digging deeper

Question

I don't know if I should ask this question in Android Stackexchange or here, but I am sure I am in a right place to ask.

My question is about following Samsung Certificate file:

File name: I9301I-357537065876500.cert

[cert] 
Model=GT-I9301I
IMEI=357537065876500
SerNo=S200013955 
ImeiSign=75779BA6B9FF5269A6828F2EAB02049B874169ACE705F5B6187EFE5F91B619E4D23EC50D7AED63D3F570766B6E03C9A416FC4B760329F43F3C06FF2B5404922BE64B7FAA457B11F3840057E8ED4160537C241B89B36B48842A78D9B5EB359820A8A44DFB1AD9021D5920AD8B856558740CDC8ECDD1981ADEA9ED81873F989221322A2CD8D8FF7DA19DEDABADF2E00D0BC7D1A8331A6C3904CCA8CF7EB97F4413496CC50966ECB12012DAB689EBEFF23ED3C5E48944675E4488A501BE5BF44DBAD20F035E3C5A0E4E7C32653061EB5E8ACA4B26480A19DC3F02EB881A0ED2BE64522228FFCA66B335FECF7DD9113AEE9067DB8AEBB751528A4E9A6B4DF07AF9F1

PubKey=4000000025A3C38C533FFC73439ED6110A953784B1489FAABCC5050059FFB62E6FED9602EEE2752285681D3F888D47E44D509865B76E6CE2D0CCC53928BD9C220792A8B6EC3D7EDA75364B7D3E2057F20CBA44E75C1057D0E85A0BE9C873AFB740ECD20B9BF1CC22CA167A4AC850ADF41CFBDC924A1A8EEBB603274584B50EEA786EB184C5284EDAAF79D8F15BD9A559A4F4A11D11478BA7259182EB2561C6C05BC587C491A60206689BFCE7A463617A7DE64FAF4493D12245BFA9523D58508FC8543E8868AB9C506DA1379BE2954AA35397B2ADA75518F158D5FB691BA8A6309266A714C9A22ACBA4693DC5B2848E45611E0E712FC577A3A50B21B6095744B28FDCD149ADD9F0935367F7FC9D79C3237791D74AD38A47846A117571D91802AE3261DD971ECD968454AD397DE1F413C430EAB7A2B3B1A3B9C94AC031B11B3233F49BD7A165E3D603C3FA274F1F10BE6A3112305F47EFDE511627CDA0010D90F35A90689041384F4FA83BADB8CA8AD523470DF9C556A07E05FC7E33FB945C46EE29BA9082E6C970BE5AFF147750029FD0B51A8CE71BF5F25E6076F02B0AB01DE8F8E742D0CA855E9D89EF6CFEEB41EE819E21256B8E1A1AF25C47E904BACBB891C7C0D173A40F0B4A727DF7F273EDCD2A0B2728BEC9A986259866676E1B1EE743D20D08F977D1AAAEAD3CDD4CECF6B1E0AC67C8CE0F158C1093CE04B7F4E6E4B77B1D05BB1832923B

PubKeySign=719D9FE450D96A5DCFCD05FAC2DD88CD4222D30D396CB1760EF9C3024E7EC686F45C44AA6D1ED4648733389C5945130F567949A7E55419B1765B4FC0B829F4487528CC85AE552E6F3A8759B25C95AE658F1E4C578178230A738B46409A65213DB4246B0A1A7888A4EB72D545F85613309E1C6696AC6C8123566450193594625292AF269BBE1A89A8B77B49C0E65D59910BE886B0A5B1A3A8F5A2595158FC10B408800E840FCE78EA9835B5085D3CCE3DC36FA92DAB7C1373DC563599F32E61C6ED85DA4C0708EF0743FAC5A08904F097BC782FE92102BC511D014806CCEAD4D1EF860A415E3DFE578431513E49E7CC99B7F17852FDFF2EBB75163968E09B67AE

File is downloaded from here

A discussion that I found here says, this cert file is

Imei Cert Is RSA 512

Another users says:

Absolutely wrong! Imei cert is rsa 2048.

My question is how do I know if it is 512 or 2048 as well what are the steps to generate our own cert file according to these parameters given: Model IMEI SerNo

Answer 1

I found a description of the format of the public key here posted by Victor from Blagoevgrad at GSMHosting.com. As mentioned in the comments, both signature sizes are also 2048 bits, so that's pretty conclusive.

Here's the contents of the post of the information in the link:

#define RSANUMBYTES 256           /* 2048 bit key length */
#define RSANUMWORDS (RSANUMBYTES / sizeof(uint32_t))


typedef struct RSAPublicKey {
    int len;                  /* Length of n[] in number of uint32_t */
    uint32_t n0inv;           /* -1 / n[0] mod 2^32 */
    uint32_t n[RSANUMWORDS];  /* modulus as little endian array */
    uint32_t rr[RSANUMWORDS]; /* R^2 as little endian array */
    int exponent;             /* 3 or 65537 */
} RSAPublicKey;

I found out that there is a modexp3 in the rest of the source code which is made more efficient using the n0inv and rr values, so the public exponent has value 3 (it seems missing from the structure, so I guess that part has been deprecated).

Possibly the confusion comes from the 40 00 00 00 hexadecimal value at the front; this encodes 64 when seen as little endian value. However, it doesn't mean 64 bytes: 64 * 8 = 512, but 64 words, where each word is 32 bits, i.e. 4 times as much giving 2048 bits.

This means that the modulus has the following value - in big endian:

93f0d9ad49d1dc8fb2445709b6210ba5a377c52f710e1e61458e84b2c53d69a4cb2aa2c914a7669230a6a81b69fbd558f11855a7adb29753a34a95e29b37a16d
509cab68883e54c88f50583d52a9bf4522d19344af4fe67d7a6163a4e7fc9b680602a691c487c55bc0c66125eb829125a78b47111da1f4a459a5d95bf1d879af
da4e28c584b16e78ea0eb584452703b6eb8e1a4a92dcfb1cf4ad50c84a7a16ca22ccf19b0bd2ec40b7af73c8e90b5ae8d057105ce744ba0cf257203e7d4b3675
da7e3decb6a89207229cbd2839c5ccd0e26c6eb76598504de4478d883f1d68852275e2ee0296ed6f2eb6ff590005c5bcaa9f48b18437950a11d69e4373fc3f53

If I use the key (just using the modulus and public exponent 3) I find that the ImeiSign signature is a PKCS#1 v1.5 signature using SHA-1 as hash. Fortunately for Samsung, the IMEI itself will probably not be susceptible against SHA-1 weaknesses w.r.t. collision resistance.

I cannot seem to verify the IMEI with it though, probably due to some strange (BCD-like?) encoding of the IMEI number. Anyway, the SHA-1 hash within the signature is 824ae6730ee34d365375e791aa2331d5e57c320d in case you want to try a few things.

Answer 2

This isn't any of the commonly used public key formats, but the PubKey section is 1040 bytes of hexidecimal. RSA public keys are formed of a "public exponent" and a "modulus", and the length in bits of the "modulus" is what defines the RSA key size (512, 2048, 3072, 4096, etc). The "public exponent" is usually rather small, 65537 (0x010001) is common.

So with 1040 hex characters (nibbles) being $1040\ nibbles\times 4\frac{bits}{nibble}=4160\ bits$ I'd guess that this is in fact a 4096-bit public key.

You cannot create your own certificate without a private key that the device will accept. Since you don't have access to that private key, you cannot create a valid certificate.