Under the Hood of HTTPS
A Practical Guide to RSA Encryption and Digital Signatures
The RSA algorithm is a public key, asymmetric encryption algorithm, developed for the needs for better security when transferring critical data over the internet. Before HTTPS was adopted all internet traffic was visible with trivial means such as packet capturing, this led to the development of public and private key encryption algorithms that allowed for the safe sharing of information in an open space. By signing a piece of information with a public key, only the holder of the private key can view that information.
Public key encryption algorithms aren’t unbreakable however, the security of these algorithms comes from the fact that with large enough keys deriving the private key from the public key would take an inordinate amount of time. This public key cryptography system is most widely used in the RSA encryption algorithm. RSA uses prime numbers as public and private keys and a complex formula for encrypting and decrypting data signed with these keys. RSA’s usage has become ubiquitous over the development of the internet. HTTP became the standard way for users to visit websites, however, all traffic through the HTTP protocol was unencrypted and any malicious actor could view any activity from any user. This led to the advancement of HTTPS for secure communication over the internet. HTTPS is HTTP routed through the TLS/SSL protocol encrypted using the RSA algorithm. Understanding how RSA works is vital in today’s internet age. This report of the RSA public key encryption lab explores the underlying functionality of the RSA algorithm.
Task1: Deriving the Private Key
The heart of the RSA algorithm is the Private Key. The private key is the sole security mechanism of public-private key encryption. The public key is represented by (e,n) and the private key is represented by (d,n). N is the multiplication of P and Q N=(P-1)*(Q-1), and by the property of the integer factorization P and Q remain unobtainable after the computation of N the public key.
The private key of the RSA algorithm is derived from two prime number’s P and Q along with an exponent E. The formula for computing the private key is:
D=e^-1mod(n)Using these 3 keys, it is trivial to create a function to generate the private key.
Task 2: Encrypting a Message
As computing the private key is fairly trivial, so is encrypting a message with another public key. The public key is simply the modulus of P and Q, and combining the public key with the exponent E a message can be encrypted that only the holders of the original P and Q prime numbers can decrypt. The encryption algorithm is:
C=M^E(mod N)C is the generated cyphertext, M is the original message, E is the chosen exponent, and N is the public key. Encrypting text into cipher text using RSA ensures only the holder of the private key can now view the message’s content. This allows for websites to securely transfer critical data such as credit card information for online shopping, social security numbers for filing taxes online, and personal data such as home addresses and telephone numbers.
This example uses the opposite of the modular inverse, the modular exponent, to encrypt the hex values of the message "A top secret!" using a public key.
Task 3: Decrypting a Message
Decrypting a message using RSA is the same as the encryption function, however, instead of raising the original message by E the exponent, the cypher text message is raised to D or the private key using the function:
M=C^Dmod(N)Where M is the original message, C is the cypher text and N is the public key. This example uses this formula to decode a cypher text string receiving the original message “Password is dees”.
Task 4: Signing a Message One of the key aspects of cryptography isn’t just obfuscating information through encryption, it is also trust. Trust in cryptography comes from the knowledge that information received was from the correct sender, and that information sent is from the correct receiver. Public key encryption allows for information verification through a process called signing. By encrypting a piece of data with 2 separate keys, the sender and the receiver can be verified and no other party with access to both of the keys can view the message.
By using this behavior of RSA we can sign a message and even though the data changes by a single byte we can observe that the generated signature is completely different.!
Task 5: Verifying a Signature
Being able to create a signature is only one half of ensuring information verification. Being able to accurately verify the signature is valid is also just as important. Similarly to a hash function if any information is changed in a signature it is no longer the same signature and the process of verifying that signature will expose it as invalid. This example showcases signature verification using RSA, and by changing a single byte in the signature we can show the signature is no longer verified.
Task 6: Manually Verifying a X.509 Certificate
This task shows a real-world example of signature verification. Whenever a user visits a website signature verification happens automatically, this is usually denoted with a lock symbol next to the URL bar to show the signature has been verified. RSA is implemented in the real-world using certificates from known verified sources called Certificate Authorities. These Certificate Authorities give certificates to end users to verify they are visiting the correct website.
Beginning with a real world X.509 certificate, which is just a standard way of transferring certificates, in this example from “www.google.com” extracted from the website.
Then using tools like OpenSSL one can read these certificates in human readable format and extract the necessary modulus N and the exponent E,
Then by extracting the signature from the servers certificate you can verify the hash of the certificate to verify its authenticity.
By extracting these pieces of data you can use the same verification function from task 5 to verify the signature.
