I have this uni project that I have to implement in code:

"App for Secure delivery of the gray images, encryption-decryption with AES in OFB mode + secret key delivery using Merkle–Hellman knapsack + DSA signature"

I am struggling with structure of the program and how to combine these algorithms together.

What I did so far:

I implemented AES algorithm using OFB mode with private key(Which will be determined later) and IV (initial vector for OFB mode).

Then to implement Merkle-Hellman key exchange, I simulated communication between Alice and Bob.

Firstly, they both establish first connection by generating pair of public,private key for their own. They send their own public keys to each others and come to the result of shared secret key. We use that shared secret key for the symmetric encryption algorithm AES. Where they can encrypt and decrypt images based on shared secret key that Bob and Alice have access to.

My questions:

Now for DSA, I don't how or where this part can come in my project?

Another question, I already have shared secret key between bob and alice for encryption and decryption of AES, why do I need DSA to verify their authenticity?


2 Answers 2


Beware that "key delivery using Merkle-Hellman knapsack" has very little to do with Diffie-Hellman Key Exchange (DHKE, often abbreviated DH as in the question's title) which seems to be the basis of what has been implemented for "secret key delivery".

Key delivery using Merkle-Hellman knapsack would draw a random secret key, and encrypt it per the Merkle–Hellman knapsack cryptosystem.

Now for DSA, I don't how or where this part can come in my project?

DSA is an early digital signature scheme with appendix, specified in FIPS-186 editions 1 to 4. With parameters L = 3072 (perhaps 2048), N = 256, and SHA-256 or SHA3-256 as the hash, it's considered secure.

In the question's system, the sender would be the signer and would hold a private key, with the corresponding public key known by the receiver. The corresponding key pair would have nothing to do with the Merkle-Hellman key pair used for encryption. And even if DHKE is used as the basis of key delivery, it's advisable that a different key pair is used by a participant when they sign and when they decrypt.

There are two main ways to integrate a signature scheme with appendix in the question's system: encrypt-then-sign, or sign-then-encrypt. When it's OK to disclose in clear the identifier $\mathrm{ID}$ of the public key of the sender, encrypt-then-sign has the advantage that it can satisfy the partisans of the dogma that it's best to not start decrypting a message that has not been authenticated. In such system, the sender could:

  • draw a random AES secret key $K$
  • encrypt that secret key per Merkle-Hellman knapsack with the public key of the designated receiver, forming $C_0$ (which I assume of fixed size)
  • draw a random $\mathrm{IV}$ (which I assume of fixed size)
  • encrypt the message $M$ per AES-OFB with $\mathrm{IV}$ and $K$, forming $C_1$
  • compute a DSA signature $S$ of $C_0\mathbin\|\mathrm{IV}\mathbin\|C_1$ using the sender's private key (that step involves computing the SHA-256 hash of the signed data $C_0\mathbin\|\mathrm{IV}\mathbin\|C_1$)
  • form the final cryptogram, like $\mathrm{ID}\mathbin\|C_0\mathbin\|\mathrm{IV}\mathbin\|C_1\mathbin\|S$

The structure of the cryptogram is such that the sender can encrypt and sign while producing the message: it's easy to make it an online algorithm. Also the receiver can determine the sender's public key from $\mathrm{ID}$ at start of the message, hash $C_0\mathbin\|\mathrm{IV}\mathbin\|C_1$ as it's received, verify the signature $S$, and then only start decryption, abiding to the aforementioned dogma. However this requires storing the message. Alternatively, decryption can also be an online algorithm, but then obviously it's critical to not act on the decrypted message until the signature is verified (e.g. if the message consists of changes in a database, the changes much not be committed until said verification). And less obviously, it's also important that an adversary can't obtain side channel information about the decrypted but unauthenticated message (like an error code, or processing time).

If it's wanted to encrypt $\mathrm{ID}$, then in an encrypt-then-sign scenario decryption must in practice start before signature verification (in order to get $\mathrm{ID}$ and know what public key is used), removing some of the rationale for encrypt-then-sign. In that case, arguably, sign-then-encrypt is best: signature applies to the message only, with the advantage that the signature can be kept and remains verifiable after decryption, possibly by a different subsystem of the receiver. Note that for such sign-then-encrypt it's critical that the signature is encrypted (otherwise, a guess of the message can be verified from the signature, e.g. it can be checked if the image is the standard Lena test image).

Note: $\mathrm{IV}$ can be removed from the cryptogram and set to all-zero on encryption and decryption if the secret key $K$ is comfortably large, e.g. 192 or 256 bit. That's inadvisable for shorter $K$ even though they are not re-used, because a public constant $\mathrm{IV}$ facilitates key search when many known plaintext/ciphertext pairs are known.

Note: since this is image encryption, it might be desired to compress the image. If so, that must be before encryption, but may leak information about the image, e.g. allow to recognize Lena from Peppers.

Addition: Regardless of the cryptosystem used for public key encryption (which is part of the assignment), the public key of the receiver must reach the sender with integrity. That's a standard assumption, including for the Merkle-Hellman public key. We can similarly assume that the sender's DSA public key reaches the receiver with integrity. In practice, integrity can be insured in several ways: digital certificate issued by a trusted authority, transfer by a trusted mean, checking a hash of the public key over some trusted channel. That does not seems to be part of the assignment.

  • $\begingroup$ I figured later that diffie and merkle are different. especially that merkle is asymmetric without shared secret key. How can I use merkle-hellman for key exchange? I know it's not practical but it's asked to do so in my project. What I thought about is we generate public and private key for Bob, and Alice obtains Bob's public key. we generate random shared secret key, Alice encrypts it with Bob's public. send it to the Bob, then Bob decrypt with his private key. Is that the ideal way? $\endgroup$ Mar 6 at 20:07
  • $\begingroup$ The answer indicates how to use Merkle-Hellman for "secret key delivery" from the onset. It does not describe Merkle-Hellman (and I'm not familiar with it). See addition for how "Alice obtains Bob's public key" and vice versa. $\endgroup$
    – fgrieu
    Mar 6 at 21:11

It'll prevent replay attacks as DSA relies on a number used once and a private key, meaning that each message has a completely different signature. The DSA can then be verified with the public key by the reciever.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.