Asymmetric Encryption
Asymmetric encryption, also known as public key cryptography, uses 2 mathematically related keys to encrypt and decrypt data. You create 2 keys; one public key and one private key. When you encrypt something with your public key, you can only decrypt it with your private key. Until yesterday I thought it was also true the other way around. I thought if I encrypted with private key, I could decrypt with public key. Turns out real world RSA and ECC do not work like that.
I designed a system that was based on the idea of encrypting with private key and decrypting with the public key. When I tried to come up with dummy implementation to see if it works, I realized that you cannot encrypt with the private key. And I think there are a lot of people who thinks RSA works this way. Just an example from StackOverflow:
This answers has 155 upvotes and starts like this: In RSA crypto, when you generate a key pair, it’s completely arbitrary which one you choose to be the public key, and which is the private key. If you encrypt with one, you can decrypt with the other — it works in both directions.
I decided to read more about RSA and ECs. Here is a summary of what I learned. It is mostly for my own future reference but maybe useful for others too.
RSA — Keys / Encryption / Decryption
- RSA is actually 2 different algorithms. One for asymmetric encryption, and one for digital signatures.
- RSA keys, the private key and the public key have the same mathematical properties so it is possible to use them interchangeably in the algorithms. When RSA is used without padding it is called Text-Book RSA. In text-book RSA keys are actually interchangeable. You can encrypt with private key and decrypt with the public key. However this is insecure for reasons and most modern libraries do not support this mode.
- Text-book RSA is deterministic. This means encrypting the same message twice produces the same ciphertext.
- To make RSA safer, practical RSA implementations typically embed some form of structured, randomized padding into the plain-text before encrypting it.
- In cryptography, padding is adding data to the beginning, middle, or end of a message prior to encryption. If you append random data to your plain-text, each encryption would generate a different cipher.
- There are 2 common padding implementations for RSA. OAEP and PKCS#1 v1.5. People on internet unanimously agree that OAEP is safer than PKCS.
- RSA public and private keys are similar but they don’t have the same security properties. The public key is usually (not always) easily guessable from the private key.
- Excerpt from iOS documentation: “… it’s typically easier to store only the private key and then generate the public key from it when needed.”
- As of 2021 recommended key length for RSA is 2048 or larger.
- RSA is somewhat slow and and can only encrypt data to a maximum amount equal to your key size (2048 bits = 256 bytes), minus any padding and header data (11 bytes for PKCS#1 v1.5 padding).
- AES is fast and can encrypt a lot of data. So when you need to encrypt and transmit large chunks of data you can generate an AES key, encrypt your data with it, encrypt your aes key with recepient’s public key and send both to other side. Recipient can decrypt the AES key with her own private key, and then decrypt the actual data using the AES key.
RSA — Signatures
- This is how RSA signature algorithm work:
- You create a hash of your data. You have to hash because RSA cannot sign large messages just like it cannot encrypt large data.
- You sign the hash using RSA private key to generate signature. (Signature is not encryption. “Encrypt with the private key” is not a valid cryptographic operation.)
- You send the original data and the signed hash to the recipient.
- The recipient calculates the hash from the actual data, verifies the signature using public key and compares two hashes.
- RSA signature algorithm provides integrity. It also provides authenticity indirectly because you and only you should have access to your private key.
RSA Android Code Samples
Android Documentation:
Elliptic Curve Cryptography (ECC) — Keys / Encryption / Decryption
- ECC is an alternative to RSA. It implements all major capabilities of the asymmetric crypto-systems: encryption, signatures and key exchange.
- ECC uses smaller keys than RSA for the same level of security works faster.
- ECC public keys can be derived from ECC private keys.
- This is what an elliptic curve looks like in the wild:
- To use ECC you first need a curve. There is no problem in having many people sharing the same curve, it does not make them share private keys or anything like that.
- Creating a new curve is very complex and expensive, due to point counting and all that. So a few standard curves have been defined; the most well known and supported are those from FIPS 186–3, published by NIST.
- There are 5 popular curves: P-192, P-224, P-256, P-384 and P-521.
- A public key in ECC is a point on the curve. If you decide to use the P-256 curve, then, by definition, your public key will be a point on that curve, represented as two values in the 256-bit field. We may say that P-256 is a “256-bit curve”.
- To use EC keys for encryption, you need to either use ECDH plus a key derivation function (KDF) to compute a shared symmetric key which you can use for your data, or to use ECIES which does that internally.
Great summary from Practical Cryptography For Developers:
- Assume we have a ECC private-public key pair. We want to encrypt and decrypt data using these keys. By definition, asymmetric encryption works as follows: if we encrypt data by a private key, we will be able to decrypt the ciphertext later by the corresponding public key:
- The above process can be directly applied for the RSA cryptosystem, but not for the ECC. The elliptic curve cryptography (ECC) does not directly provide encryption method. Instead, we can design a hybrid encryption scheme by using the ECDH (Elliptic Curve Diffie–Hellman) key exchange scheme to derive a shared secret key for symmetric data encryption and decryption.
- ECC encryption scheme:
- ECC decryption scheme:
- Elliptic Curve Integrated Encryption Scheme (ECIES) standard combines ECC-based asymmetric cryptography with symmetric ciphers to provide data encryption by EC private key and decryption by the corresponding EC public key.
- As of Android 10 AndroidKeyStore does not currently support encryption or decryption with EC keys, only with RSA keys. You can use ECC for signatures but not encryption.
- If you have to implement ECC in Android, you can check this pure Java implementation: Ephemeral elliptic curve Diffie-Hellman key agreement in Java.
- Apple’s secure enclave stores only 256-bit elliptic curve private keys. These keys can only be used for creating and verifying cryptographic signatures, or for elliptic curve Diffie-Hellman key exchange (and by extension, symmetric encryption).
ECC Android Code Samples
ECC iOS Code Samples
I am not familiar with Swift, just barely got these to compile!
Apple documentation: Generating new crypto keys
Apple Documentation: Getting an existing key from Keychain
Apple Documentation: Using Keys for Encryption
Apple recommends using eciesEncryptionCofactorX963SHA256AESGCM for symmetric encryption. This algorithm can be used for ECIES encryption or decryption. It does not limit the size of the message to be encrypted or decrypted. Encryption is done using AES-GCM. AES Key size
is 128bit for EC keys <=256bit and 256bit for bigger EC keys.
Apple Documentation: Signing and Verifying
References:
https://cryptobook.nakov.com/asymmetric-key-ciphers/elliptic-curve-cryptography-ecc
https://cryptobook.nakov.com/asymmetric-key-ciphers/ecc-encryption-decryption