Introduction
Diffie-Hellman Key Exchange
Diffie-Hellman key exchange is a protocol that enables two parties who have no prior knowledge of each other to exchange secret keys over an insecure communication channel through the use of modular exponentiation. It was invented by Whitfield Diffie and Martin Hellman in 1976.
The Diffie-Hellman key works as follows:
- Both parties, i.e. Alice and Bob, agree on a large prime number,
p, and a generator,g, a smaller prime number. The values ofpandgare public and can be known by any attacker. - Alice picks a private key
xwhich is less thanp. Bob also picks a private keyywhich is less thanp. These private keys are kept secret. - Alice computes
A = g^a mod p, and Bob computesB = g^b mod p. These are the public keys that both parties then exchange openly. - Alice and Bob use the received public keys and their private keys to compute the same shared secret key. Alice computes
s = B^a mod p, while Bob computess = A^b mod p. - Alice and Bob now have the same shared secret key,
g^(ab) mod p, which can be used for symmetric encryption, such as AES, to ensure confidential communication over an insecure channel.
The security of the Diffie-Hellman key exchange is based on the difficulty of the discrete logarithm problem, which is the problem of finding the exponent in modular exponentiation. If an attacker intercepts the exchanged public keys or messages, they would need to solve the discrete logarithm problem, which is computationally infeasible for large prime numbers.
The RSA Algorithm
The RSA (Rivest-Shamir-Adleman) algorithm is named after its creators: Ron Rivest, Adi Shamir, and Leonard Adleman. The RSA algorithm is based on the mathematical properties of prime numbers and involves the use of a public key for encryption and a private key for decryption.
The RSA algorithm generates the private and public as follows:
- Choose two distinct large prime numbers, p and q.
- Compute n = p * q. This number becomes the modulus for the public key and private key.
- Compute the totient function, φ(n) = (p-1) * (q-1).
- Find a number e, where 1 < e < φ(n) and gcd(e, φ(n)) = 1 (This means that e is relatively prime to φ(n)). This becomes the public key exponent (e)
- Compute the private key exponent (d) as the modular multiplicative inverse of e modulo φ(n), i.e., d ≡ e^(-1) mod φ(n).
RSA encrypts data as follows:
- Convert the plaintext message into a numerical value using a suitable scheme (e.g., ASCII).
- Encrypt the numerical value using the public key: c = m^e mod n, where m is the numeric representation of the plaintext message and c is the ciphertext.
RSA decrypts data as follows:
- Decrypt the ciphertext using the private key: m = c^d mod n, where m is the decrypted numerical value and c is the ciphertext.
- Convert the numerical value back into the plaintext message using the same scheme as in the encryption step.
The security of the RSA algorithm relies on the factorization of large composite numbers. It is computationally difficult and time-consuming to factorize a large number into its prime factors, making the algorithm secure against attacks.
Note
___ When the private key is used for encryption, it no longer serves the purpose of encryption, because anyone with the public key has access to the encrypted data. Instead, when a private key is used, it is used as a form of signature to show that the data is from the expected origin.SeedLabs: RSA Encryption and Signature Lab
Deriving the Private Key
This section of the lab involves deriving a private key from the following:
- a public exponent (e): 0D88C3
- a large prime number (p): F7E75FDC469067FFDC4E847C51F452DF
- a large prime number (q): E85CED54AF57E53E092113E62F436F4F
Note
- The prime numbers used for this lab are 128 bits and are not large enough to be secure. However, 128 bits have been selected to simplify the lab.
- In practice, these numbers should be at least 512 bits long.
The numbers involved in the RSA algorithms are typically more than 512 bits long and as such I cannot simply do a * b, but need to use an algorithm to compute their products. This lab makes use of the Big Number library provided by OpenSSL.
Using this library is straightforward. I define each big number as a BIGNUM type:
- A structure created to hold BIGNUM temporary variables used by library functions: BN_CTX *ctx = BN_CTX_new()
- Initialize a BIGNUM variable: BIGNUM *a = BN_new()
And then use the APIs provided by the library for various operations, such as:
- Computing res = a − b: BN_sub(res, a, b)
- Computing res = a + b: BN_add(res, a, b)
- Computing res = a ∗ b: BN_mul(res, a, b, ctx)
- Computing res = a ∗ b mod n: BN_mod_mul(res, a, b, n, ctx)
- Computing res = a^c mod n: BN_mod_exp(res, a, c, n, ctx)
- Computing modular inverse: BN_mod_inverse(b, a, n, ctx)
Deriving the private key can be done by writing a Clang program that will calculate the private key using the OpenSSL BIGNUM library.
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *p = BN_new(); // large prime number
BIGNUM *q = BN_new(); // large prime number
BIGNUM *e = BN_new(); // public exponent
BIGNUM *d = BN_new(); // private key
BIGNUM *n = BN_new(); // modulus
BIGNUM *one = BN_new(); // 1
BIGNUM *res1 = BN_new(); // (p-1)
BIGNUM *res2 = BN_new(); // (q-1)
BIGNUM *totient = BN_new(); // (p-1) * (q-1)
// Initialize p, q, and e
BN_hex2bn(&p, "F7E75FDC469067FFDC4E847C51F452DF");
BN_hex2bn(&q, "E85CED54AF57E53E092113E62F436F4F");
BN_hex2bn(&e, "0D88C3");
BN_hex2bn(&one, "01");
// Compute the modulus, n = p*q
BN_mul(n, p, q, ctx);
// Calculate (p-1)
BN_sub(res1, p, one);
// Calculate (q-1)
BN_sub(res2, q, one);
// Compute the totient function, totient = (p-1) * (q-1)
BN_mul(totient, res1, res2, ctx);
// Calculate the private key, d
BN_mod_inverse(d, e, totient, ctx);
printBN("Private key = ", d);
return 0;
}
gcc rsa_privkey.c -lcrypto -o rsa_privkey
./rsa_privkey
After running the program, I got the private key as “3587A24598E5F2A21DB007D89D18CC50ABA5075BA19A33890FE7C28A9B496AEB”.
Encrypting a Message
This section of the lab involves encrypting a message using the receiver’s public key. The public key will be calculated from the following:
- a public exponent (e): 010001
- a modulus (n): DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5
Note
- The public key is (e, n).
- I need to convert the message to an ASCII string (hex equivalent)
- I also need to convert the hex string to a BIGNUM using the hex-to-bn API: BN_hex2bn()
The secret message to encode is: “This is a super secret message!”
The secret message can be converted to a hex string using the below Python code:
python3 -c 'print(bytes.hex("This is a super secret message!".encode("ascii")))'
“This is a super secret message!” = 54686973206973206120737570657220736563726574206d65737361676521. It is converted to a big number and used to encrypt the message.
I encrypt the message by writing a Clang program to do that. I also verify that our encryption is correct by decrypting the cipher text with the private key the lab author provides.
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *c = BN_new(); // cipher text
BIGNUM *M = BN_new(); // original message
BIGNUM *e = BN_new(); // public exponent
BIGNUM *d = BN_new(); // private key
BIGNUM *n = BN_new(); // modulus
BIGNUM *m = BN_new(); // decrypted message
// Initialize e, n, M, and d
BN_hex2bn(&e, "010001");
BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
BN_hex2bn(&M, "54686973206973206120737570657220736563726574206d65737361676521"); //"This is a super secret message!"
BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
// Compute cipher text, c = M^e mod n
BN_mod_exp(c, M, e, n, ctx);
printBN("Encrypted message = ", c);
// Compute the deciphered text, m = c^d mod n
BN_mod_exp(m, c, d, n, ctx);
printBN("Original Message = ", M);
printBN("Decrypted Message = ", m);
return 0;
}
gcc rsa_enc.c -lcrypto -o rsa_enc
./rsa_enc
After running the program, I got the following result:
Encrypted message = DB9D180A2D11752D60A6200F1DFF22A8413E37F8D569F138C4FEFDDBFAF116ED
Original Message = 54686973206973206120737570657220736563726574206D65737361676521
Decrypted Message = 54686973206973206120737570657220736563726574206D65737361676521
Decrypting a Message
This section of the lab involves decrypting a secret message. The public/private keys used in this task are the same as the ones used in the encryption lab.
The values I would use in our program include:
- the public exponent (e): 010001
- the modulus (n): DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5
- the encrypted message (C): 8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F
- the private key (d): 74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D
I decrypt the message by writing a Clang program to do that.
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *C = BN_new(); // encrypted message
BIGNUM *e = BN_new(); // public exponent
BIGNUM *d = BN_new(); // private key
BIGNUM *n = BN_new(); // modulus
BIGNUM *m = BN_new(); // decrypted message
// Initialize e, n, C, and d
BN_hex2bn(&e, "010001");
BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
BN_hex2bn(&C, "8C0F971DF2F3672B28811407E2DABBE1DA0FEBBBDFC7DCB67396567EA1E2493F");
BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
// Compute the deciphered text, m = C^d mod n
BN_mod_exp(m, C, d, n, ctx);
printBN("Decrypted Message = ", m);
return 0;
}
gcc rsa_dec.c -lcrypto -o rsa_dec
./rsa_dec
After running the program, I got the following result:
Decrypted Message = 50617373776F72642069732064656573
I still need to convert the hex output to its readable string equivalent. I do this using the below python code:
python3 -c 'print(bytes.fromhex("50617373776F72642069732064656573").decode("ascii"))'
Running the above code converts the hex string into “Password is dees”
Signing a Message
This section of the lab involves signing a message using the private key of the correspondent. The public/private keys used in this task are the same as the ones used in the encryption lab.
I would directly sign the message, instead of signing its hash value.
The values I would use in our program include:
- the public exponent (e): 010001
- the modulus (n): DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5
- the private key (d): 74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D
The message to sign is: “I owe you $2000.” The message can be converted to a hex string using the below Python code:
python3 -c 'print(bytes.hex("I owe you $2000.".encode("ascii")))'
“I owe you $2000.” = 49206f776520796f752024323030302e
An alternate message that is a slight variation of the original message will also be signed: “I owe you $3000.” The alternate message can be converted to a hex string using the below Python code:
python3 -c 'print(bytes.hex("I oI you $3000.".encode("ascii")))'
“I owe you $3000.” = 49206f776520796f752024333030302e
The below Clang program signs both messages:
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *c = BN_new(); // digital signature
BIGNUM *M = BN_new(); // message to sign
BIGNUM *m = BN_new(); // alt message to sign
BIGNUM *d = BN_new(); // private key
BIGNUM *n = BN_new(); // modulus
// Initialize n, m, and d
BN_hex2bn(&n, "DCBFFE3E51F62E09CE7032E2677A78946A849DC4CDDE3A4D0CB81629242FB1A5");
BN_hex2bn(&M, "49206f776520796f752024323030302e"); // "I owe you $2000."
BN_hex2bn(&m, "49206f776520796f752024333030302e"); // "I owe you $3000."
BN_hex2bn(&d, "74D806F9F3A62BAE331FFE3F0A68AFE35B3D2E4794148AACBC26AA381CD7D30D");
// Compute the digital signature, c = M^d mod n
BN_mod_exp(c, M, d, n, ctx);
printBN("Digital signature for \"I oI you $2000.\" = ", c);
BN_mod_exp(c, m, d, n, ctx);
printBN("Digital signature for \"I oI you $3000.\" = ", c);
return 0;
}
gcc rsa_sign.c -lcrypto -o rsa_sign
./rsa_sign
After running the program, I got the following result:
Digital signature for "I owe you $2000." = 55A4E7F17F04CCFE2766E1EB32ADDBA890BBE92A6FBE2D785ED6E73CCB35E4CB
Digital signature for "I owe you $3000." = BCC20FB7568E5D48E434C387C06A6025E90D29D848AF9C3EBAC0135D99305822
The following can be observed:
- The variation in the original message and the alternative message seems rather insignificant from the output of their hex code.
- However, when both messages are signed, there is a significant variation in the digital signature of both messages.
- This means that even the most insignificant change in a message will cause obvious changes in a digital signature.
Verifying a Signature
This section of the lab involves verifying the signature of a message using the public key of the correspondent. The public/private keys used in this task are the same as the ones used in the encryption lab.
Bob receives a message M = “Launch a missile.” from Alice, with her signature S. I need to verify whether the signature is indeed Alice’s or not.
The following values are used:
- the public exponent (e): 010001
- the modulus (n): AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115
- the digital signature (S): 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F
- the message (M): “Launch a missile.”
The message with a digital signature to verify is: “Launch a missile.” The message can be converted to a hex string using the below Python code:
python3 -c 'print(bytes.hex("Launch a missile.".encode("ascii")))'
“Launch a missile.” = 4c61756e63682061206d697373696c652e
I can verify the digital signature received with the message to find out if it was indeed Alice who sent the message using the below clang code:
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
char* isValid(BIGNUM *a, BIGNUM *b);
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *S = BN_new(); // digital signature
BIGNUM *e = BN_new(); // public exponent
BIGNUM *m = BN_new(); // computed message
BIGNUM *n = BN_new(); // modulus
BIGNUM *M = BN_new(); // message to verify
// Initialize e, n, S, and M
BN_hex2bn(&e, "010001");
BN_hex2bn(&n, "AE1CD4DC432798D933779FBD46C6E1247F0CF1233595113AA51B450F18116115");
BN_hex2bn(&S, "643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F");
BN_hex2bn(&M, "4c61756e63682061206d697373696c652e");
// Compute the deciphered text, m = C^d mod n
BN_mod_exp(m, S, e, n, ctx);
printBN("Computed Message = ", m);
printBN("Received Message = ", M);
printf("%s", isValid(m, M));
return 0;
}
char* isValid(BIGNUM *a, BIGNUM *b)
{
if (BN_cmp(a, b) == 0){
return "The message is from Alice!\n";
} else {
return "The message is not from Alice!\n";
}
}
gcc rsa_vrfy.c -lcrypto -o rsa_vrfy
./rsa_vrfy
After running the program, I got the following result:
Computed Message = 4C61756E63682061206D697373696C652E
Received Message = 4C61756E63682061206D697373696C652E
The message is from Alice!
I can be sure that the message actually came from Alice. Suppose that Alice’s signature above is corrupted, such that the last byte of the signature changes from 2F to 3F (there is only one bit of change), I can check to see if the verification will pass.
Alice signature: 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6802F Corrupted signature: 643D6F34902D9C7EC90CB0B2BCA36C47FA37165C0005CAB026C0542CBDB6803F
When I substitute Alice’s signature with the corrupted signature in the Clang program, compile it, and run it, I get the below results:
Computed Message = 91471927C80DF1E42C154FB4638CE8BC726D3D66C83A4EB6B7BE0203B41AC294
Received Message = 4C61756E63682061206D697373696C652E
The message is not from Alice!
Manually Verifying an X.509 Certificate
This section of the lab involves manually verifying the signature on an X.509 certificate downloaded from a web server.
Download a certificate from a real Ib server.
I have downloaded a certificate from www.netflix.com with the following command:
openssl s_client -connect www.netflix.com:443 -showcerts </dev/null
The result of the command contains two certificates, www.netflix.com certificate and an intermediate CA’s certificate (the issuer).
Certificate chain
0 s:C = US, ST = California, L = Los Gatos, O = "Netflix, Inc.", CN = www.netflix.com
i:C = US, O = DigiCert Inc, CN = DigiCert TLS RSA SHA256 2020 CA1
-----BEGIN CERTIFICATE-----
MIIH2DCCBsCgAwIBAgIQD3yGw6wTDOsMS0741fUczTANBgkqhkiG9w0BAQsFADBP
MQswCQYDVQQGEwJVUzEVMBMGA1UEChMMRGlnaUNlcnQgSW5jMSkwJwYDVQQDEyBE
aWdpQ2VydCBUTFMgUlNBIFNIQTI1NiAyMDIwIENBMTAeFw0yMjEyMTQwMDAwMDBa
Fw0yNDAxMTQyMzU5NTlaMGgxCzAJBgNVBAYTAlVTMRMIQYDVQQIEwpDYWxpZm9y
bmlhMRIIAYDVQQHEwlMb3MgR2F0b3MxFjAUBgNVBAoTDU5ldGZsaXgsIEluYy4x
GDAWBgNVBAMTD3d3dy5uZXRmbGl4LmNvbTCCASIwDQYJKoZIhvcNAQEBBQADggEP
ADCCAQoCggEBAL+R3l6GTMQfCdM2/rfmjR5XT6nT+MEm0XgGagJ7RSaIxAm/sZP5
H3uUANxomm+yRVJ9Tol9m5A7fUJzZFlOga6i87iWqpDt4cdm3EzWpuzxryvs1RRK
pJm4pejMdHhtImtmM+uMDDcJGa7H2+N7kalghN3XA2a4RaWCaIxzim+U9hiaXDr/
U+PUE0Z277Jsp+4cNouOl1MdQ2onmmZqZRqpZkT66YUq4RS0cqFFQykDZ7BXF95z
dEmvAY9NQGyd4V4leG0+2JLP8efkHOjck3wPICrP/qiz6Sm35IaEfnzo4YGFo+G9
qHuby5L2f4M8mLK6nZlAF1YLiiA7brD3J5sCAIAAaOCBJUwggSRMB8GA1UdIwQY
MBaAFLdrouqoqoSMeeq02g+YssWVdrn0MB0GA1UdDgQWBBSZG3N517R1xKSJxvgQ
bwJiXp5WtDCCAT4GA1UdEQSCATUwggExghNhY2NvdW50Lm5ldGZsaXguY29tgg5j
YS5uZXRmbGl4LmNvbYIKbmV0ZmxpeC5jYYILbmV0ZmxpeC5jb22CEnNpZ251cC5u
ZXRmbGl4LmNvbYIOd3d3Lm5ldGZsaXguY2GCEHd3dzEubmV0ZmxpeC5jb22CEHd3
dzIubmV0ZmxpeC5jb22CEHd3dzMubmV0ZmxpeC5jb22CGWRldmVsb3Atc3RhZ2Uu
bmV0ZmxpeC5jb22CGXJlbGVhc2Utc3RhZ2UubmV0ZmxpeC5jb22CD3d3dy5uZXRm
bGl4LmNvbYIOdHYubmV0ZmxpeC5jb22CH2VtYmVkLmRldmVsb3Atc3RhZ2UubmV0
ZmxpeC5jb22CH2VtYmVkLnJlbGVhc2Utc3RhZ2UubmV0ZmxpeC5jb20wDgYDVR0P
AQH/BAQDAgWgMB0GA1UdJQQWMBQGCCsGAQUFBwMBBggrBgEFBQcDAjCBjwYDVR0f
BIGHMIGEMECgPqA8hjpodHRwOi8vY3JsMy5kaWdpY2VydC5jb20vRGlnaUNlcnRU
TFNSU0FTSEEyNTYyMDIwQ0ExLTIuY3JsMECgPqA8hjpodHRwOi8vY3JsNC5kaWdp
Y2VydC5jb20vRGlnaUNlcnRUTFNSU0FTSEEyNTYyMDIwQ0ExLTIuY3JsMD4GA1Ud
IAQ3MDUwMwYGZ4EMAQICMCkwJwYIKwYBBQUHAgEWG2h0dHA6Ly93d3cuZGlnaWNl
cnQuY29tL0NQUzB9BggrBgEFBQcBAQRxMG8wJAYIKwYBBQUHMAGGGGh0dHA6Ly9v
Y3NwLmRpZ2ljZXJ0LmNvbTBHBggrBgEFBQcwAoY7aHR0cDovL2NhY2VydHMuZGln
aWNlcnQuY29tL0RpZ2lDZXJ0VExTUlNBU0hBMjU2MjAyMENBMS5jcnQwDAYDVR0T
AQH/BAIwADCCAX0GCisGAQQB1nkCBAIEggFtBIIBaQFnAHYAdv+IPwq2+5VRwmHM
9Ye6NLSkzbsp3GhCCp/mZ0xaOnQAAAGFEctRGQAABAMARzBFAiBdxbj/wqFVldN8
hW9Zy1UCLkBQdoUaqxHkT5CHLOsDqAIhAJM5SesAUhEbg3VapX3wd/1Si7J4zzZv
+PTnLCsPRpdYAHUAc9meiRtMlnigIH1HneayxhzQUV5xGSqMa4AQesF3crUAAAGF
EctRQAAABAMARjBEAiB0AsnycGIybrc+o3qVVxfyfTN8mJ6LU/dDd72czaXuxQIg
BJqGhW2oNnLva5eJ4xy0zjg91BhE2BhPCevGIIlHBrsAdgBIsONr2qZHNA/lagL6
nTDrHFIBy1bdLIHZu7+rOdiEcwAAAYURy1D/AAAEAwBHMEUCIQDfDi7m/8IuKpnj
XwvatZimC7zAdRK8dkd0ZSLb8GgSMAIgMfyfUvuroxtchcc53GKtGv62iMWs89zt
fdGxvg5EC/YwDQYJKoZIhvcNAQELBQADggEBAJk3/iAeYveoxDJSVqs3IWx/pcI0
8uauI8VMOO7kUHFsZ0eEJr17CC0IjJPTUQx2/sQtRQHpCgMH9BqNeaF+6oFVMwbb
6IpJqOWSQk+zE5HwDO52lvBALVd8tJgXgFFrTe5GlZHt08k7f0POJXx8lTeGk4gr
gEXrUI1Zt9/Cc4W0QX0wbdw4IMevFCfO7W3HvUKmiDtiMHQoBQJijx6/LZ8qSmQa
JitfWyD1Ag4Dqdq1TCPXyXVJ8KNxMOTmY7JjVdzwq8zZYplsjzMHeXO0gwtKdoO8
+mBICKRAzR91EH8plEBG4S7nyBFQBys2EQHlE4IplZOBz78OropPRq+XXqM=
-----END CERTIFICATE-----
1 s:C = US, O = DigiCert Inc, CN = DigiCert TLS RSA SHA256 2020 CA1
i:C = US, O = DigiCert Inc, OU = www.digicert.com, CN = DigiCert Global Root CA
-----BEGIN CERTIFICATE-----
MIIE6jCCA9KgAwIBAgIQCjUI1VwpKwF9+K1lwA/35DANBgkqhkiG9w0BAQsFADBh
MQswCQYDVQQGEwJVUzEVMBMGA1UEChMMRGlnaUNlcnQgSW5jMRkwFwYDVQQLExB3
d3cuZGlnaWNlcnQuY29tMSAwHgYDVQQDExdEaWdpQ2VydCBHbG9iYWwgUm9vdCBD
QTAeFw0yMDA5MjQwMDAwMDBaFw0zMDA5MjMyMzU5NTlaME8xCzAJBgNVBAYTAlVT
MRUIwYDVQQKEwxEaWdpQ2VydCBJbmMxKTAnBgNVBAMTIERpZ2lDZXJ0IFRMUyBS
U0EgU0hBMjU2IDIwMjAgQ0ExMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKC
AQEAwUuzZUdwvN1PWNvsnO3DZuUfMRNUrUpmRh8sCuxkB+Uu3Ny5CiDt3+PE0J6a
qXodgojlEVbbHp9YwlHnLDQNLtKS4VbL8Xlfs7uHyiUDe5pSQWYQYE9XE0nw6Ddn
g9/n00tnTCJRpt8OmRDtV1F0JuJ9x8piLhMbfyOIJVNvwTRYAIuE//i+p1hJInuW
raKImxW8oHzf6VGo1bDtN+I2tIJLYrVJmuzHZ9bjPvXj1hJeRPG/cUJ9WIQDgLGB
Afr5yjK7tI4nhyfFK3TUqNaX3sNk+crOU6JWvHgXjkkDKa77SU+kFbnO8lwZV21r
eacroicgE7XQPUDTITAHk+qZ9QIDAQABo4IBrjCCAaowHQYDVR0OBBYEFLdrouqo
qoSMeeq02g+YssWVdrn0MB8GA1UdIwQYMBaAFAPeUDVW0Uy7ZvCj4hsbw5eyPdFV
MA4GA1UdDIB/wQEAwIBhjAdBgNVHSUEFjAUBggrBgEFBQcDAQYIKwYBBQUHAwIw
EgYDVR0TAQH/BAgwBgEB/wIBADB2BggrBgEFBQcBAQRqMGgwJAYIKwYBBQUHMAGG
GGh0dHA6Ly9vY3NwLmRpZ2ljZXJ0LmNvbTBABggrBgEFBQcwAoY0aHR0cDovL2Nh
Y2VydHMuZGlnaWNlcnQuY29tL0RpZ2lDZXJ0R2xvYmFsUm9vdENBLmNydDB7BgNV
HR8EdDByMDegNaAzhjFodHRwOi8vY3JsMy5kaWdpY2VydC5jb20vRGlnaUNlcnRH
bG9iYWxSb290Q0EuY3JsMDegNaAzhjFodHRwOi8vY3JsNC5kaWdpY2VydC5jb20v
RGlnaUNlcnRHbG9iYWxSb290Q0EuY3JsMDAGA1UdIAQpMCcwBwYFZ4EMAQEwCAYG
Z4EMAQIBMAgGBmeBDAECAjAIBgZngQwBAgMwDQYJKoZIhvcNAQELBQADggEBAHer
t3onPa679n/gWlbJhKrKW3EX3SJH/E6f7tDBpATho+vFScH90cnfjK+URSxGKqNj
OSD5nkoklEHIqdninFQFBstcHL4AGw+oWv8Zu2XHFq8hVt1hBcnpj5h232sb0HIM
ULkwKXq/YFkQZhM6LawVEWwtIwwCPgU7/uWhnOKK24fXSuhe50gG66sSmvKvhMNb
g0qZgYOrAKHKCjxMoiWJKiKnpPMzTFuMLhoClw+dj20tlQj7T9rxkTgl4ZxuYRiH
as6xuwAwapu3r9rxxZf+ingkquqTgLozZXq8oXfpf2kUCwA/d5KxTVtzhwoT0JzI
8ks5T1KESaZMkE4f97Q=
-----END CERTIFICATE-----
---
Server certificate
subject=C = US, ST = California, L = Los Gatos, O = "Netflix, Inc.", CN = www.netflix.com
issuer=C = US, O = DigiCert Inc, CN = DigiCert TLS RSA SHA256 2020 CA1
I went on to copy the certificates and save them in files named c0.pem and c1.pem respectively.
Extract the public key (e, n) from the issuer’s certificate.
I can extract the value of n using the “-modulus” option when viewing an X.509 certificate using OpenSSL.
openssl x509 -in c1.pem -noout -modulus
There is no specific command to extract e, but I can print out all the fields and can easily find the value of e.
openssl x509 -in c1.pem -text -noout | grep -i exponent
Extract the signature from the server’s certificate.
There is no specific command to extract e, but I can print out all the fields, easily find the value of the signature, and then copy and paste the signature block into a file, called temp.
openssl x509 -in c0.pem -text -noout
I need to remove the spaces and colons from the data to get a hex string that I can use in our program. I do this by using the “tr” utility to remove colons and spaces from the signature file and writing its contents to a file called signature.
cat temp | tr -d '[:space:]:' > signature
Below is the result of cat signature after the above operation:
Extract the body of the server’s certificate.
A CA generates the signature for a server certificate by first computing the hash of the certificate and then signing the hash. To verify the signature, I also need to generate the hash from a certificate. Since the hash is generated before the signature is computed, I need to exclude the signature block of a certificate when computing the hash.
X.509 certificates always have the same starting offset of 4, but the end depends on the content length of a certificate. I use the -strparse option of openssl asn1parse command to get the field from offset 4 (this outputs the body of the certificate, excluding the signature block) and save it to a file called c0_body.bin.
openssl asn1parse -i -in c0.pem -strparse 4 -out c0_body.bin -noout
Now that I have the body of the certificate, I calculate its hash using the following command:
sha256sum c0_body.bin
Verify the signature.
Now, I have all the information, including the CA’s public key, the CA’s signature, and the body of the server’s certificate. I can run my program I ran in the “verify a signature” task to verify whether the CA’s signature is valid or not.
The following values are used:
- the public exponent (e): 010001
- the modulus (n): C14BB3654770BCDD4F58DBEC9CEDC366E51F311354AD4A66461F2C0AEC6407E52EDCDCB90A20EDDFE3C4D09E9AA97A1D8288E51156DB1E9F58C251E72C340D2ED292E156CBF1795FB3BB87CA25037B9A52416610604F571349F0E8376783DFE7D34B674C2251A6DF0E9910ED57517426E27DC7CA622E131B7F238825536FC13458008B84FFF8BEA75849227B96ADA2889B15BCA07CDFE951A8D5B0ED37E236B4824B62B5499AECC767D6E33EF5E3D6125E44F1BF71427D58840380B18101FAF9CA32BBB48E278727C52B74D4A8D697DEC364F9CACE53A256BC78178E490329AEFB494FA415B9CEF25C19576D6B79A72BA2272013B5D03D40D321300793EA99F5
-
the CA’s digital signature (S): 9937fe201e62f7a8c4325256ab37216c7fa5c234f2e6ae23c54c38eee450716c67478426bd7b082d088c93d3510c76fec42d4501e90a0307f41a8d79a17eea81553306dbe88a49a8e592424fb31391f00cee7696f0402d577cb4981780516b4dee469591edd3c93b7f43ce257c7c95378693882b8045eb508d59b7dfc27385b4417d306ddc3820c7af1427ceed6dc7bd42a6883b623074280502628f1ebf2d9f2a4a641a262b5f5b20f5020e03a9dab54c23d7c97549f0a37130e4e663b26355dcf0abccd962996c8f33077973b4830b4a7683bcfa604808a440cd1f75107f29944046e12ee7c81150072b361101e5138229959381cfbf0eae8a4f46af975ea3
- the message (M) = 83bbfb0242940cf20acf2f8d871f083091e508c7279a227f46ca51f35297aa1d
I can verify the CA’s digital signature using the below clang code:
#include <stdio.h>
#include <openssl/bn.h>
#define NBITS 256
char* isValid(BIGNUM *a, BIGNUM *b);
void printBN(char *msg, BIGNUM * a)
{
/* Use BN_bn2hex(a) for hex string
* Use BN_bn2dec(a) for decimal string */
char * number_str = BN_bn2hex(a);
printf("%s %s\n", msg, number_str);
OPENSSL_free(number_str);
}
int main ()
{
BN_CTX *ctx = BN_CTX_new();
BIGNUM *S = BN_new(); // digital signature
BIGNUM *e = BN_new(); // public exponent
BIGNUM *m = BN_new(); // computed message
BIGNUM *n = BN_new(); // modulus
BIGNUM *M = BN_new(); // message to verify
// Initialize e, n, S, and M
BN_hex2bn(&e, "010001");
BN_hex2bn(&n, "C14BB3654770BCDD4F58DBEC9CEDC366E51F311354AD4A66461F2C0AEC6407E52EDCDCB90A20EDDFE3C4D09E9AA97A1D8288E51156DB1E9F58C251E72C340D2ED292E156CBF1795FB3BB87CA25037B9A52416610604F571349F0E8376783DFE7D34B674C2251A6DF0E9910ED57517426E27DC7CA622E131B7F238825536FC13458008B84FFF8BEA75849227B96ADA2889B15BCA07CDFE951A8D5B0ED37E236B4824B62B5499AECC767D6E33EF5E3D6125E44F1BF71427D58840380B18101FAF9CA32BBB48E278727C52B74D4A8D697DEC364F9CACE53A256BC78178E490329AEFB494FA415B9CEF25C19576D6B79A72BA2272013B5D03D40D321300793EA99F5");
BN_hex2bn(&S, "9937fe201e62f7a8c4325256ab37216c7fa5c234f2e6ae23c54c38eee450716c67478426bd7b082d088c93d3510c76fec42d4501e90a0307f41a8d79a17eea81553306dbe88a49a8e592424fb31391f00cee7696f0402d577cb4981780516b4dee469591edd3c93b7f43ce257c7c95378693882b8045eb508d59b7dfc27385b4417d306ddc3820c7af1427ceed6dc7bd42a6883b623074280502628f1ebf2d9f2a4a641a262b5f5b20f5020e03a9dab54c23d7c97549f0a37130e4e663b26355dcf0abccd962996c8f33077973b4830b4a7683bcfa604808a440cd1f75107f29944046e12ee7c81150072b361101e5138229959381cfbf0eae8a4f46af975ea3");
BN_hex2bn(&M, "83bbfb0242940cf20acf2f8d871f083091e508c7279a227f46ca51f35297aa1d");
// Compute the deciphered text, m = C^d mod n
BN_mod_exp(m, S, e, n, ctx);
printBN("Computed Message = ", m);
printBN("Received Message = ", M);
return 0;
}
gcc cert_vrfy.c -lcrypto -o cert_vrfy
./cert_vrfy
After running the program, I got the following result:
The message when hashed with sha256 has a fixed size of 64 characters. So to check if the certificate is valid, I will write a Python program that will compare the sha256 hash of the server’s certificate body against the last 64 characters of the computed message.
#!/usr/bin/env python3
# Intro
print("\nThe message when hashed with sha256 has a fixed size of 64 characters. So to check if the certificate is valid, I will compare the sha256 hash of the server's certificate body against the last 64 characters of the computed message.\n")
# Values
message = "83BBFB0242940CF20ACF2F8D871F083091E508C7279A227F46CA51F35297AA1D"
computed_message = "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003031300D06096086480165030402010500042083BBFB0242940CF20ACF2F8D871F083091E508C7279A227F46CA51F35297AA1D"
# Results
print("Computed message using CA's public key:")
print(computed_message)
print()
print("Last 64 characters of computed message:")
print(computed_message[-64:])
print()
print("sha256 value of server's certificate body:")
print(message)
print()
# Verify
if message == computed_message[-64:]:
print("The certificate is valid!\n")
else:
print("The certificate is not valid!\n")
After running the program, I obtain the below result:
Thanks for reading.