How to analyse traces of a hardware AES implementation?

Answer to the 1st and 5th question :

For the CHES 2016 (Cryptographic Hardware and Embedded Systems), a video has been made to explain how to perform a CPA. There is a wiki associated to the video and the code of the attack is available on it.

Answer to the 2nd question :

For a CPA, you don't need to use a filter : increase the number of measure (number of AES that you perform) should be enough to find the key.
Furthemore, you only need to see the round that you attack to find the key.

Answer to the 3rd question :

You can find the answer on the  topic of crypto stack exchange named "What is the difference between perfoming Correlation Power Analysis (CPA) in the first AES round and doing it in the last round?".

Answer to the 4th question :

The Hamming weight model is a basic power model which is based on the assumption that the amount of power consumed is proportional to the number of bits that are logic '1' during an operation. Typically, if you initialize a variable to the value of Sbox[x ^ y], the consumption used will be correlated to the number of bytes set to 1 in this value. For more information about it, see the .pdf available online : "Differential Power Analysis attacks on AES"
from Kevin Meritt.


Are ECDSA keys and RSA keys interchangeable?

From the source code:

function createKeySigner(bits) {
 return function sign(thing, privateKey) {
    if (!bufferOrString(privateKey) && !(typeof privateKey === 'object'))
      throw typeError(MSG_INVALID_SIGNER_KEY);
    thing = normalizeInput(thing);
    // Even though we are specifying "RSA" here, this works with ECDSA
    // keys as well.
    var signer = crypto.createSign('RSA-SHA' + bits);
    var sig = (signer.update(thing), signer.sign(privateKey, 'base64'));
    return base64url.fromBase64(sig);
  }
}

See in particular the comment. What happens here is that even though you specified "RSA with SHA-512" as signature algorithm (the 'RS512' parameter, in that library's weird terminology), the code perfectly knows that the private key is for ECDSA, not RSA (look at the contents of the private key file, it starts with "BEGIN EC PRIVATE KEY"), and so it "helpfully" uses ECDSA instead of RSA, transparently.

No mystery here then, just some Node.js code doing Node.js stuff (i.e. doing what it can instead of what you asked for, and hoping for the best -- a rather dubious methodology for all things related to security, in particular cryptography).


The answer to this question follows directly from the answers to Should we MAC-then-encrypt or encrypt-then-MAC? and the comment thread here.  In short: Your scheme is computationally secure (IND-CCA2 and INT-CTXT) assuming that HMAC is a computationally secure privacy-preserving MAC; but your scheme is wildly impractical, as fgrieu explains, so it is not very interesting from a practical perspective.  In addition, this is far from the best possible construction.

If you want advice on what construction to use, I suggest you ask a new question specifying your requirements and let folks suggest a construction.  In practice standard schemes for authenticated encryption should suffice for almost all real-world situations.


Question regarding of the ECC test vector format

so (X,Y)=(m dot G), G is the base point defined by NIST or BP curve as “standard”. Q1: Is such understanding correct?

Yes, that sounds likely to be right.

  Q2: Does that mean we need convert them to hex--and by doing that I can get exactly 32byte test vector?

What format your C test code handles is, well, up to your C test code.  What they represent is an integer, however you choose to store it, in the scalar ring of the curve.

  and some other curve like BP-521, does that mean the key bit lenth is 521b?

What BP-521 refers to, I don't know, but if it's anything like E-521 or NIST P-521, it likely refers to the size in bits of the coordinate field modulus, i.e. the field in which the coordinates $x$ and $y$ live in: the Mersenne prime $2^{521} - 1$ is convenient as a modulus for arithmetic because $2^{521} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod{2^{521} - 1}$, so a reduction step only takes a shift-and-add.

Hasse's theorem implies that the size $\ell$ of the scalar ring and the size $q$ of the coordinate field can't be much different, $|\ell - (q + 1)| \leq 2\sqrt q$, so the scalar ring modulus $\ell$ is also going to be near $q = 2^{521} - 1$ in this case but may be off by about $2^{261}$.


You have correctly identified why the stupid ‘do you even RSA, bro‽’ cryptosystem is trivially vulnerable to forgery and/or decryption by an adversary if you naively use the same key for naive encryption and naive signature—although it doesn't apply in a single instance: you use your private key to sign a ‘message’, and your friend's public key to encrypt it.  But if someone can get you to sign a ‘message’ which is actually an encrypted message to you, they have just got you to decrypt the message for them.

This is why nobody in their right mind who takes the time to listen to cryptographers actually uses this stupid cryptosystem.  Unfortunately, many textbook authors document this stupid cryptosystem and call it ‘RSA’ and leave it at that.  This is why some people use the insufficiently derisive term ‘textbook RSA’.

What you should do instead is use independent keys for RSA-based signature and encryption, and use them in sensible RSA-based cryptosystems.

The post I linked to summarizes some alternative modern RSA-based cryptosystems.  In another answer, I summarized in simple terms a modern RSA-based signature scheme called RSA-FDH.

These may even be safe to use with the same key, as long as you choose independent hash functions for the signature scheme and for the signature scheme—however, I'm not aware of a security reduction to the RSA problem for the use of the same key in any pair of sensible RSA-based encryption scheme and signature scheme.  So I recommend using independent keys, just to be on the safe side.

Or don't use RSA at all, because securely composing signature and encryption into authenticated-encryption is hard (archived), and additionally leaks verifiability to third parties, which may or may not be what you want.  Instead, consider using a NaCl crypto_box_curve25519xsalsa20poly1305.


What tests can I do to ensure my random number generator is working correctly?

Checking statistical randomness is a semi-good test. What I mean by that is that if a given PRNG does not look good statistically, then it is utterly proven to be pure junk. On the other hand, good statistical randomness does not tell you much with regards to cryptographic security. Cryptographic security is about whether the PRNG output could be predicted by a sentient attacker who knows the in and outs of your algorithm (but not its internal state). Statistical randomness is about whether the PRNG output could be predicted by a trained monkey.

"Diehard tests" used to be popular for testing non-cryptographic PRNG. During the AES competition (a dozen years ago), NIST ran them on all AES candidates, and found nothing, and the general opinion among cryptographers was that it was mostly a waste of time.

A Linear Feedback Shift Register has handsome results with Diehard -- and using it for cryptography is immediate failure.


You are over-thinking about cryptography. It's not supposed to be that complex.
I started with the idea "let make 1 chip have multiple id".
And I come up with something relatively simple than what you mentioned so far. (I'm not sure if this usable in your situation or not. It's just based on the info you described.)

Prepare: I will make every chip have unique id and a counter like you mentioned.
Setup: When a chip is registered to the server I will make the server generate keyed hash using unique id as key and counter as message but instead of generate just 1 hash from the current value of counter let say I generate 5,000 consecutive hash start from the current value of counter and store generated hashes in the database.
Identify(chip): Instead of directly send the unique id to the server just send keyed hash with the same algorithm as hashes generated on the server then increase the counter in the chip.
Identify(server): The server can determine the chip id just by querying the database with received hash. (This operation should be very fast since hash value can be indexed.) From this querying the server should know the counter value inside the chip too not just the unique id. The server can now delete current and older hash from the database. If hashes in the database for a chip fall below (say) 2,000 the server will generate consecutive hash to fill 5,000 hash pool.
That's the overview. It's seem like I missed 64-bit communication chunk constrain. (Thanks to Ricky Demer for pointing it out.)
To address that issue: the hash used should no longer than 64-bit.
Just allow hash collision happen in the database we can simply don't use hash as the primary key.
When the chip send collision hash just ignore that and wait for the next sample. If the missing sample is significant in some way we can assume that next hash will have the same chip as the owner hence we can pin point which chip send the previous hash. (If it still undecidable just wait for next one.)
Or we can also assumed that the chip that just appear with the collision hash is not the one who send the hash.

This idea is derived from what you mentioned about the counter that leak chip identity in some way but now we use it on the server.
And that's it I will do it this way if no one point out any flaw in this approach (which I myself cant see).


How To prove Any Change to $v=a\cdot y+b$ maks $y=(a)^{−1}\cdot (v−b)$ Uni. random value

Well, there is not much to prove.

  The server can do any change to $v$.

So actually, this means the server with throw away your $v$ and just choose a new random number. Or alternatively, he chooses $w$ uniformaly random and sets $v'=v+w$, which is now also uniformly random.

When you get back that value, you have your (for you known/fixed) values $a,b$ and do your calculation $y' = a^{-1}(v'-b)$. With he existence of $a^{-1}$ (i.e. $a\neq0$), this is also uniformly distributed for fixed values $a,b$.


What defining the digest as part of the API does is allow the device to be a completely self-contained cryptographic system. This system can then be tested as a unit -- if you did, say, hashes on the client side, you would have to ensure that the hash implementation was secure for each and every new implementation. By putting everything in one module, you can test and secure that module independently of everything else on the system -- you know your PKCS #11 device has a proper implementation, and don't have to bother re-implementing it yourself. That gives you a lot more flexibility as well, as everything you need is in that device (so you don't have to reimplement digesting every time you have a new system, as it's in the device).

FIPS actually requires a similar thing -- all cryptography has to be within a FIPS-certified device, because that outsources all the needed compliance steps to the FIPS device (you only have to check that device for compliance, and can then use it anywhere without worrying about the cryptographic implementation in the rest of the system).


In search of platform independent 128-bit hash function

If the space of inputs is predetermined before you deploy your system, you can create a perfect hash that is very fast to evaluate and guarantees unique hash values, such as with gperf or nbperf.

If the space of inputs is chosen by a non-adaptive adversary—i.e., an adversary picks a set of keys and then feeds them all to your system at once without picking some keys based on how the system reacted to others—then you can pick some (almost-)universal hash family such as Poly1305 with a secret key you choose uniformly at random: for any pair of inputs, the probability over all possible keys that the inputs collide is $O(1/m)$, where $m$ is the number of possible hash values.

If the space of inputs is chosen by an adaptive adversary and Siphash is too slow, you will need to describe your performance budget in more detail:

How many keys do you have?
What is the distribution of key lengths?
How many cycles per byte can you afford?
How many cycles per key can you afford?
How many bytes can you afford to transmit/store?
What is the cost of a collision?  Of $n$ collisions?

(Transmitting 8 bytes on a network is not free!  Exercise for the reader: How many nanoseconds and joules does it take to compute Siphash on a 16-byte input on your laptop's CPU, and how many nanoseconds and joules does it take your  laptop's ethernet phy to transmit 8 bytes?)


Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

This is an interesting question. In fact, cryptographers have been using this exact protocol on many occasions, and there are two important reasons to prefer Schnorr over this protocol in most situations.

The soundness of the protocol is not based on the Diffie-Hellman problem.

This is probably the most important point to address. What does it mean for this protocol to be sound? Informally, soundness can deal with two types of statements: you might want to prove membership in a language, or (this is stronger) you might want to prove knowledge of a witness. An example of the first statement could be "I claim that $(g,h,u,v)$ is a DDH-tuple", while an example of the second statement can be "I know the discrete logarithm of $y$ in base $g$".

Let's go back to your protocol now: you should be easily convinced that it cannot be expressed as a statement related to membership to some language: this would be a trivial statement (think "$y$ does have a discrete log in base $g$": if $g$ is a generator, this is always trivially true). What you truly care about is showing that the prover does know the discrete log of $y$ in base $g$. Formally, I know a witness is defined in cryptography as the witness can be efficiently learned from me, or more precisely: there exists a polynomial-time extractor that, given the code of the prover, can extract a valid witness from the code.

Now, how would you do that with your protocol? With Schnorr's protocol, it's fairly easy: given the code of the prover, run it to get the first flow $g^r$, then put a breakpoint, fork it, and run it twice on two different challenges $e,e'$ from the verifier. You get back two answers $d,d'$ which satisfy (with non-negligible probability) the verification equation: $y^e\cdot g^r = g^d$ and $y^{e'}\cdot g^r = g^{d'}$. From the two equations, you easily get $g^{(d-d')\cdot (e-e')^{-1}} = y$ (assuming you have a prime order group), hence you've just extracted the witness $x = (d-d')\cdot (e-e')^{-1}$.

I would suggest that you spend a minute or two convincing yourself that there is no clear way to do the same thing with your protocol. Given the code of the prover, it is not clear at all how one would extract $x$.

But now, this is unsatisfying, right? Intuitively, it seems clear that the only way for the prover to answer correctly the challenge of the verifier in your protocol is by knowing $x$. This seems obvious, but we cannot prove it. This issue has been acknowledge long ago in the crypto community - it was first identified by Damgård in this paper, published in 1991. The best cryptographers could do was to formalize this belief in the form of an assumption, which is called the Knowledge-of-Exponent Assumption (KEA). This assumption states exactly that our intuition must be right: "for any polytime algorithm A that successfully replies (with good probability) with $y^k$ given as input $g^k$, there exists a polytime extractor that, given the code of A, outputs $x$ such that $g^x = y$."

Assumptions of this style are now widely used in cryptography - for example, very similar assumptions are at the core of SNARGs and SNARKs, which have gained a widespread attention due to their efficiency and their use in anonymous cryptocurrencies. Still, they are weird assumptions. For one thing, they are not even falsifiable: to break the factorization assumption, just give me a polytime algorithm that factors number, and I can easily check that it works. But for KEA, it's not even clear how one could verify that you have broken the assumption - this cannot just be an efficient algorithm, it has to be somehow an algorithm, together with a convincing argument that no extractor can exist for this algorithm.

Getting back to your protocol, then: it is believed to be sound, but only under the KEA assumption (tautologically). This is a weird and not well understood assumption. It does not even come close to being comparable to the Diffie-Hellman assumption, it's just a strange object in itself. In comparison, note that the soundness of Schnorr's protocol is just unconditional. Not based on a weird assumption, but also not even based on an assumption at all.

The protocol is only HVZK, not ZK, and it is not clear how to make it ZK

Before moving on with this point, a quick digression: a simple modification of your protocol can be used to prove that a tuple is a DDH tuple (meaning: fix generators $(g,h)$, and now the prover wants to demonstrate that some pair $(u,v)$ is of the form $(g^x,h^x)$). Proving DDH relations is widely used in crypto. But unlike your protocol, we can now be happy with a membership proof: in most situations, it suffices to show that the witness $x$ exist (it's a non-trivial relation), no need to show that the prover knows it. So, suppose you modify your protocol as follows:

Verifier: send $g^{k_1}\cdot h^{k_2} = w$

Prover: answer with $z = w^x$

Verifier: check that $u^{k_1}\cdot v^{k_2} = z$

Then, interestingly, the previous issue disappears entirely: although it would still require KEA to prove that the prover must know $x$, it does not require any assumption at all to prove that $x$ exists, and this suffices to show that $(u,v)$ is a DDH tuple! In other words: in appropriate settings, for a slightly different language, a variant of your protocol does actually not have any problem with soundness anymore. So, why do we still not use it often?

This has to do with zero-knowledge. As you correctly pointed out, your protocol (and the variant above) satisfies honest-verifier zero-knowledge (as does Schnorr's protocol), meaning that it is zero-knowledge as long as the verifier is honest.

Sure, but why do we even care about HVZK? In practice, we are not really happy with something being secure only when the opponent is honest, right? The answer is that what we truly care about is indeed full-fledged ZK, but HVZK is often a good first step: we know very general and very efficient transformations that can convert a large class of HVZK protocols into full-fledged ZK protocol. Hence, we can just build HVZK protocols, prove that they satisfy this property, and they can be compiled into real ZK protocols when needed.

What is this large class of HVZK protocols that we can transform efficiently into ZK protocols? They are the so-called public coin protocols: all protocols in which all the randomness used by the verifier is fully revealed to the prover. Take one minute to convince yourself that this property is satisfied by Schnorr's protocol (and by essentially any HVZK protocol in the literature, up to a few exceptions), but not by your protocol. This means that even though your protocol is HVZK, this does not suffice to make it ZK through general techniques!

Of course, there are known methods that can transform your protocol into a ZK protocol, introducing additional rounds and complexity. But then, they end up loosing any clear advantage over Schnorr's protocol in terms of efficiency... So we usually simply stick to Schnorr and its variants :)


Could someone reuse client certificates?

If you use public key crypto in the correct way, then every user has it's own private key and corresponding public key (included in the certificate) and the keys of users are not related. Consequently, compromising the private key of one user does not affect any of the other users. So in the case of compromise of the private key of one user the remaining users are safe.

There are examples where you would run into problems, e.g., if using common modulus for RSA - but if the user's private keys are generated correctly, i.e., independently with independent and good randomness - as it should be done in practice - then there will be no problem. It is, however, known that bad randomness is partially used in practice, e.g., resulting in RSA moduli that share at least a prime factor. You can find more information for example here or another example here.

Clearly, if you use public key crypto in the wrong way and give a private key to several users, then you will have this problem or if you use bad randomness you may also run into these problems. But you should not do that!!


Blind signatures are online by definition. They involve at least two independent parties that interact during the signature generation process. A protocol is "online" if a successful execution of the protocol requires an exchange of messages between two or more independent parties. Consequently, no application of blind signatures, including a digital cash system, can be completely offline.

Furthermore, any transaction within a digital cash system has to be, to some extent, completed "online". "Digital cash" refers to a system that allows you to complete a transaction by exchanging nothing more than information and in which, somehow, your credits are stored digitally on your device. Your digital cash can't be spent without access to the digital information only you possess.

This means, firstly, that each potential owner of credits in a digital cash system has to appear as a black box to any other potential owner of credits within the same system. The only requirement is that each potential credit owner is able to play out the protocol steps involved in a transaction. There is no way for one party to digitally verify that another party is using specific hardware or software that guarantees that the other party is not tampering with audit trails of transactions that have never been committed to any other party.

With logical necessity: If you want to pay someone some amount, you have to communicate this somehow to someone, or else there will be no transaction. You cannot commit to a transaction if you keep all records of the transaction to yourself, because in such case you could simply delete those records at a later time, and there would be no way for anyone to know that the transaction had ever taken place.


This seems a strange question to ask. Is it for an assignment or are you trying to select the best mode for a particular application? Regardless:

ECB does not use an IV.
CTR has a nonce value, which could be considered an IV. A bit error there will produce an entirely different key stream for every block.
CBC and CFB will corrupt the first plaintext block, but thereafter it is OK.
In the case of OFB, I believe the entire plaintext will be corrupted because the entire stream of data is determined by the IV (plus the key, of course).


I'm a computer programmer and need my own encryption to encrypt things like my passwords.

This does not imply that you need to write your own encryption algorithm. Being a programmer does not make you a cryptographer, cryptography is a skill unto itself that takes lots of experience and practice.

Plenty of experienced cryptographers have gone through the trouble of designing and analyzing algorithms for people in your situation, precisely so that you don't have to write your encryption algorithm.

More importantly

It's inappropriate to encrypt passwords. Standard good practice dictates the use of a slow, memory-hard password hashing function such as scrypt or argon2 (or pbkdf2 at the very least).

"Unbreakable encryption"

  is it possible to write an encryption that is 100% uncrackable, as long as I keep certain parts private?

The One Time Pad in theory provides information-theoretic security, which means that no amount of computational advantage or sophisticated algorithm can help an adversary who has a ciphertext learn more about the plaintext than they already know.

Using the One Time Pad in practice is clunky and prone to failure (and here's another Q/A supporting that conclusion if that was not sufficient). It is difficult to fulfill the assumptions that the proof rests upon, and so it is not used very often in practice despite the theoretical guarantees.

In practice, algorithms such as AES and Salsa20 will remain unbroken when implemented and used correctly.

While solid encryption algorithms do exist, encrypting passwords is a poor idea.

If you want to succeed

If you care about fulfilling your security goals, then it is a good idea to stick to battle-hardened algorithms and pre-existing software libraries that implement them. Libsodium is a solid recommendation.

Do not create your own implementation (except as a learning experience) - your information and/or your users information is at stake, and there exists a non-negligible probability of failure.


What is the difference between key size and block size (for AES)?

The key size is simply the amount of bits in the key. With AES, like most modern block ciphers, the key size directly relates to the strength of the key / algorithm. The higher the stronger. Since all bits are used, there are $2^{\mathit{klen}}$ possible keys, taking $2^{\frac{\mathit{klen}}{2}}$ operations to brute force on average.
For AES the internal key schedule and the number of rounds are different for each key size. Due to the difference in key schedule there are related key attacks on AES-256 but not on AES-128 or AES-192. The number of rounds is 10, 12 or 14 for the 128, 192 and 256 bit key size respectively. The overall algorithm behind the AES cipher remains the same.

The block size is simply the amount of bits or bytes that can be transformed by the block cipher. It is the input and output size of the keyed block cipher. This transformation is called a keyed permutation as each plaintext has a corresponding ciphertext (and vice versa) for a specific key. For AES the block size is 128 bits or 16 bytes. So a plaintext from the set of $2^{128}$ possible plaintext is permuted to a single ciphertext from the set of $2^{128}$ possible ciphertext.
It is also a pseudo-random permutation or PRP as there is no link between the plaintext and the ciphertext. To be more precise the ciphertext block is indistinguishable from random as long as the key is unknown to any observer. Of course it is only pseudo random as the same plaintext will always permute to the same ciphertext, as long as the key doesn't change.

The number of permutations of a block cipher (i.e. all the possible ways that plaintext blocks can be mapped 1:1 to the ciphertext blocks) rises much faster per bit of the block size than the amount of keys per bit specifying the key size. With a block size of 128 bits the key size can grow to unreasonable sizes without having to worry about duplicate permutations.

Notes

the key size and block size are not directly related to each other - it is possible to create a block cipher for any key size and block size;
AES is a subset of Rijndael, which is the winner of the AES contest by NIST. Rijndael allows key and block sizes of 128, 160, 192, 224, and 256 bits (32 bit increments);
a block cipher is not a generic cipher, a mode of operation is required to use the block cipher to protect confidentiality;
although the block size is not directly related to the security of the block cipher itself, it does affect the security of the mode of operation that the block cipher is used in;
the related key attacks on AES-256 are only of influence if a large number of related keys are generated, for instance when AES is used to create a secure hash function - the use of AES-256 remains secure when used for a particular mode of operation to obtain confidentiality or within a MAC to obtain message authentication and integrity;
AES-256 can be used to provide protection against analysis of the block cipher with a (fully functional, large state) quantum computer - AES-128 provided plenty of protection against the currently known attacks without QC;
AES-192 doesn't make too much sense as it is not as fast as AES-128 while not providing the very large key size of AES-256 to provide the highest security strength or full protection against QC;
AES-192 is tricky to use because the key size is not a multiple of the block size, this makes it hard to use AES-192 in protocols where keys need to be encrypted or when the output of the cipher needs to be used as key.


What happens when a root CA loses its private key?

What happens when such a device is lost (fire, electronic fault,
  stolen, etc)?

Assuming the HSM is stolen: The CA will likely inform the police so they can hunt the thief down, then they will ensure that the thief has actually only stolen a brick (that is, they can't do anything useful with the HSM) and finally they will just continue business as usual and maybe inform the CA/B mailing list about this incident.

Assuming the HSM is no longer available to other reasons: The CA will ensure that the key material inside the HSM is no longer retrievable and then give it into the trash.

In either case: The CA will likely acquire a new HSM (or a new set of HSMs) and restore the key material from the other HSMs they have and import it into the new HSM(s). That's the big difference between HSMs and smart cards: With smart cards you usually can't get the key out at all. With HSMs you can get encrypted copies out of the HSM that can be read and used by other HSMs of the same type, given that they have been initialized in the same way. Also decent CAs will have their root keys at at least 2 different physical locations, exactly to deal with this type of scenario.


Homomorphic encryption for vector addition

A very simple way to do something like this is by using the following construction:

$$E^*(\langle x,y,z \rangle) = \langle E(x), E(y), E(z) \rangle,$$

where $E$ is an additively homomorphic cryptosystem.  (To avoid attacks, use three different public keys to encrypt the three components.)  Now $E^*$ has your desired homomorphic property.

I don't understand what the hyperlinear business is, so I've ignored that part.

The problem with this construction is that the three components are separable.  For instance, given $E^*(\langle x,y,z \rangle)$, it is possible to recover $E^*(\langle x,0,0 \rangle)$.  Or, given $E^*(\langle x_1,y_1,z_1 \rangle)$ and $E^*(\langle x_2,y_2,z_2 \rangle)$, it is possible to compute (say) $E^*(\langle x_1+x_2,y_1,z_1 \rangle)$.  These are values that it might not be possible to derive with just $\oplus$.

So, can we do better?  That's what I'll answer next.

Can we do better?

The answer is probably, it depends.  There are a bunch of situations where it is simply not possible to do better -- it's not possible to achieve what you want.  To identify whether it will be possible to achieve what you want, we need to dig a bit deeper into the specific details of exactly what you want, in greater precision.

Suppose we want an encryption scheme

$$E^*: \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z} \to R$$

that is additively homomorphic on $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z}$.  In other words,

$$E^*(\langle x_1,y_1,z_1 \rangle)\oplus E^*(\langle x_2,y_2,z_2 \rangle) = E^*(\langle x_1+x_2,y_1+y_2,z_1+z_2 \rangle),$$

and $\oplus$ is the only method we have for combining ciphertexts.

If $p,q,r$ are three different numbers that are pairwise relatively prime, it is definitely not possible to do what you want.  Here's why.  Given $E^*(\langle x,y,z \rangle)$ and an integer $n$, it is always possible to efficiently compute $E^*(\langle nx,ny,nz \rangle)$ using just $\oplus$ (use repeated doubling).  Set $n_1=r \times (r^{-1} \bmod q)$.  Then given $E^*(\langle x,y,z \rangle)$, we can compute $E^*(\langle n_1 x,y,0 \rangle)$ via the formula

$$E^*(\langle n_1 x,n_1 y,n_1 z \rangle) = E^*(\langle n_1 x,y,0 \rangle),$$

using that we know how to get the left-hand side of the formula above from $E^*(\langle x,y,z \rangle)$ and $n_1$.  Next, set $n_2 = q \times (q^{-1} \bmod p) \times (n_1 \bmod p)$.  Now given $E^*(\langle n_1 x,y,0 \rangle)$, we can compute $E^*(\langle  x,0,0 \rangle)$ using the formula

$$E^*(\langle n_2 n_1 x,n_2 y,0 \rangle) = E^*(\langle x,0,0 \rangle).$$

So in this case, given $E^*(\langle x,y,z \rangle)$, we were able to compute $E^*(\langle x,0,0 \rangle)$ using just the operation $\oplus$.  This shows that if $p,q,r$ are mutually co-prime, then it's guaranteed that the three components will be separable, no matter what we do.  So, in this case you might as well use the very simple construction shown at the top of my answer.

What if $p=q=r$?  This looks like one case where it might be possible to achieve your desired property.  However, we have to be a bit careful.  If we know ciphertexts $E^*(\langle x_1,y_2,z_3 \rangle),\dots,E^*(\langle x_k,y_k,z_k \rangle)$ where the linear span of these three vectors is all of $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}$, then we can separate the three components and we're back to something that is no better than my very simple construction at the top of the answer.

In conclusion, it's only going to be possible to achieve what you want if you pick $p,q,r$ very carefully and if you severely limit what ciphertexts are available to the eavesdropper.  Moreover, the specific construction might depend on your specific choice of $p,q,r$.  Did you have a strategy to deal with these challenges?  You might want to edit your question to tell us about what values of $p,q,r$ you had in mind and how they'll be chosen and how they're related (mutually different, mutually co-prime, all the same, whatever).


First, you should always use HMAC with the secret data as the key and the (possibly) public data as the message. The proof of its security relies on that. So rather than concatenating the static key to the message, you might want to consider concatenating it to the secret key.

Second, the extra hash doesn't add any security. Anyone who knows the secret key would be able to calculate it just as easily as the HMAC alone. It is only a small layer of obfuscation – you are relying on the attacker not trying it.

So, denoting the "secret key" $k_1$ and the "shared key" $k_2$, there are at least three options:

$H_{k_2}(H_{k_1}(m))$, where you use the secret key first, then the shared.
$H_{k_1}(H_{k_2}(m))$, where you do the opposite.
$H_{k_1||k_2}(m)$, where the keys are concatenated.

The first two differ in the order you use the keys. The reason this matters is that an attacker knowing the inner key could use a collision search to attack the whole MAC. If the inner HMAC collides, the outer one does as well. This only matters if the HMAC hash lacks collision resistance, but collision resistance is not normally required so it is theoretically weaker than necessary even with something like SHA-256.

The last is the most frugal, since you only need one HMAC call. It should be secure even against an attacker who knows one of the keys. It is the one I would recommend.

The nonce idea does not add security, unless you can check its uniqueness, in which case you would avoid replay attacks. With random nonces you would need to store them all to check they are unique, or you could have App2 generate it and send it for App1 to use, adding latency. With an incrementing counter only the previous value needs to be stored (but you need to handle lost messages somehow).

In a replay attack an authenticated message without context information can be copied and sent by an attacker at a later time. Whether you need the nonce to avoid it depends on what information your messages contain and whether sending one of them again would amount to an attack.

If you do use a nonce, it should probably be concatenated with the message rather than the key, since a nonce is public information.


Recover plaintext in passive attack of RSA of coprime public key

Hint: if $c_A$ is not invertible, what does that say about $gcd(c_A, n)$?  How can you exploit that to obtain $m$ in another way?


You can use a 16-bit truncation of MD5 or SHA-1 or SHA-256 or SHAKE128 as a checksum, but it's not a good checksum.
Why not?  Let's model them by a uniform random function of $t$ bits, which is a reasonable model in this scenario.  In this case, $\Pr[H(x) = h] = 1/2^t$ for any message $x$ and hash $h$, and every $H(x)$ is independent for each distinct $x$.  Thus, the probability of failing to detect an error $e$ in a message $x$ is $\Pr[H(x + e) = H(x)] = 1/2^t$ for any message $x$ and any error $e$.  This is the best error detection you can hope for from a hash function designed like a random oracle (or close to it, length extensions notwithstanding).
If you choose a good 16-bit CRC (preprint, paywall-free; web site), then you can be guaranteed:

any error of odd parity will be detected, provided the generator polynomial has $x + 1$ as a factor;
any burst error of up to 16 bits will be detected, except an error of the generator polynomial itself, provided the generator polynomial does not have $x$ as a factor (i.e., has a nonzero constant term);
many errors of up to a certain Hamming weights in data words of up to a certain size will be detected.

Cryptographic hash functions designed for random oracle use like MD5, SHA-1, SHA-256, SHAKE128, etc., guarantee none of these.  They're also often much more expensive to compute than error-detecting codes like checksums, because you're paying an extremely high cost for collision resistance which is of no concern for error detection.

What are the consequences of simply taking a "substring" of a checksum? I assume, perhaps naively, that it would just increase the likelihood of a collision.

Collisions are not relevant here.  The only thing that is relevant is the probability of error detection.  Any substring of MD5 or SHA-1 or SHA-256 or SHAKE128 is as good as any other.

Is there any reason to prefer taking the last x bits instead of the first x bits, or vice versa?

No.  If this led to an appreciably different probability of error detection, then that would be a noteworthy result about the hash function.

When truncating a checksum like this, does SHA actually perform any better than MD5? Keeping in mind I am concerned with errors, not attackers.

No.  They're both bad choices for detecting independent random bit errors.


Can an RSA public key be generated without ever knowing the factors?

Unless you relax the restriction to allow for multi-party key generation where, if all the generating parties collude, the key can be recovered, no.

You can create something that operates like an RSA modulus. This was first proposed for use in cryptographic accumulators by Sander in "Efficient Accumulators without Trapdoor Extended Abstract".  The idea is to create a number that has at least two large prime factors that are unknown to anyone. It's known as an RSA unfactorable object (RSA UFO) and as far as I know, it's security for use in encryption or signing hasn't been thoroughly examined.

Those issues aside, the problem is the solution is by no means practical. For something with the security of a 1024 bit RSA modulus/key, you would need a 40,000 bit RSA UFO.


We can obtain "absolutely perfect CONFIDENTIALITY" using the one-time pad. Is there such a thing as "absolutely perfect INTEGRITY"?

Yes, there is the one-time MAC.  This is a scheme which ensures that an adversary (even one with infinite computational resources) has a negligible chance of altering the message or forging a fake message without detection.

Edit to add: Mikero's comment and the other answer demonstrate that we need to be clear about what we mean by "perfect" integrity.  "Perfection" is a rather nebulous term, so  I will provide a rigorous definition as I understand it, and contrast it with a similar definition for "perfect" confidentiality.  Hopefully, even if you disagree with my definitions you will be able to see why I think one-time MAC can provide "perfect" integrity (as I define it).

Perfect integrity and perfect confidentiality can both be defined in terms of games.  Let's do the confidentiality game first:

Confidentiality Game:

You have a Challenger, an Adversary, and an encryption scheme (e.g. a block cipher using a Mode of Operation, or a stream cipher, or the OTP).  The Challenger and Adversary agree upon a length limit $\ell$, which is the total length of all messages that will be encrypted by the Challenger during the game.  The Challenger selects a key from the defined key-space of the encryption scheme uniformly at random (e.g. for AES-128 it would select a 128 bit string from all such strings, and for a OTP it would select a string of length $\ell$ from all such strings).

There are two phases to the game - first a query phase, and then a challenge phase.  In the query phase, the Adversary can submit chosen plaintext queries to the Challenger, who encrypts them using the scheme and the selected key, and presents the resulting ciphertexts to the Adversary.

During the challenge phase, the Adversary selects two messages that are of equal length, $m_0$ and $m_1$, and submits them to the Challenger.  Note that the total length of all the queries added to the length of $m_0$ must not exceed $\ell$.  The Challenger selects a single bit $b$ uniformly at random, encrypts $m_b$, and presents the resulting ciphertext to the Adversary.  The Adversary outputs a single bit $a$ which is its guess as to the value of $b$.  If $a=b$ then the Adversary wins the game, otherwise it loses.

An encryption scheme provides $\ell$-wise perfect confidentiality if and only if there is no Adversary (not even a computationally unbounded Adversary) who can win this game with probability greater than 0.5.  Note that a one-time pad provides perfect confidentiality in this sense.

Integrity Game:

You have a Challenger, an Adversary, and a MAC scheme.  The Challenger and Adversary agree upon a total number of messages $n$ that the Challenger will authenticate during the game, as well as $\ell$ the total length of those messages, and a tag length $\tau$ (e.g. they can agree that the MAC tags will all be 64 bits long).  The Challenger selects a key from the defined key-space of the MAC scheme uniformly at random.

As before, there is a query phase and a challenge phase.  During the query phase, the Adversary can submit up to $n-1$ messages to be authenticated to the Challenger, who generates the corresponding MAC tags for those messages and presents them to the Adversary.  During the challenge phase, the Adversary outputs a message $M$ (which cannot be the same as any message submitted during the query phase) and a tag $T$.  The total length of the queries and $M$ cannot exceed $\ell$.  The Challenger generates the MAC for $M$, and if that MAC is identical to $T$ then the Adversary wins the game, otherwise it loses.

A MAC scheme provides $(n,\ell,\tau)$-wise perfect integrity if and only if there is no Adversary (not even a computationally unbounded Adversary) who can win this game with probability greater than $1/2^{\tau}$.  Note that a one-time MAC provides perfect integrity in this sense.


Why does applying 56-bit DES twice only give 57 bits of security?

Decrypt the ciphertext with every possible key and store the result: $2^{56}$ decryptions. Now encrypt the (known) plaintext of the ciphertext with every possible key: $2^{56}$ encryptions. Now you have to check every entry, which is in both lists and try it with another plaintext-ciphertext pair. If you can successfully decrypt that, you are very likely to have found the correct key. All in all $2^{56} + 2^{56} = 2^{57}$ DES operations (encryptions and decryptions), much less than $2^{112}$. You need some work to search inside the list and check every possible key, but for DES this is not really much work.

All this is called Meet-in-the-middle attack.


what are the advatanges and disavantages of the digital signature algorithms for JWT?

My answer is not original, as I am simply summing up information from different questions already solved in this site. Nevertheless, I thought it could be interesting to collect everything in one answer.

The first thing you have to know is to differentiate between a digital signature and a message authentication code (MAC). In this case, HMAC is a MAC and the rest (RSA and ECDSA) are digital signatures.

This answer to a previous question gives you an excellent overview of the different characteristics of both categories. As you can see, the main difference between HMAC and conventional digital signatures are:

HMAC uses symmetric keys (so both parties have to share a common secret), while Digital Signatures use asymmetric keys (i.e., public key crypto, so the prover uses a secret key, and the verifier uses an associated public key). This also has implications regarding performance, since symmetric crypto is usually much faster.
Digital Signatures provide non-repudiation of origin, while HMAC don't.

That is the first differential factor between them. Now, we could focus on the difference among digital signatures schemes:

RSASSA-PKCS1-V1_5 Digital Signatures with with SHA-2
Elliptic Curve Digital Signatures (ECDSA) with SHA-2
RSASSA-PSS Digital Signatures with SHA-2

In this case, the main differences are not about functionality, but about the underlying mathematical primitives, namely RSA vs Elliptic Curves. This also has been covered before. To sum up, the implications are mainly centered on performance, size of keys, implementations, etc.

Finally, this other answer covers the difference between RSASSA-PSS and RSASSA-PKCS1-V1_5. To sum up, the difference is mainly of theoretical interest, concerning the proof of security.


Simple compression functions an sponge functions for educational purposes

Many of the designs in the NIST SHA-3 competition came with toy variants for study.  For example:

The winner of the competition, Keccak, has parameters for:

word size—the SHA-3 standard is 64-bit, but it is formally defined for 1-bit, 2-bit, 4-bit, 8-bit, 16-bit, and 32-bit words too, for study or for smaller variants like Ketje and Keyak; and
number of rounds—the SHA-3 standard is 24 rounds, but that is overkill, so KangarooTwelve uses 12 while still providing comfortable collision resistance, and Kravatte uses 6 without aiming for collision resistance.

The popular BLAKE2 was derived from BLAKE, one of the SHA-3 finalists, which uses HAIFA, which is similar to Merkle–Damgård and Davies–Meyer but with improvements, came with several toy versions: BLOKE, FLAKE, BLAZE, and BRAKE, each with simplifications on the real BLAKE.  All admit reduced-round variants too, of course.

You could, of course, take any block cipher you like, and apply it with Davies–Meyer, or any of various block cipher constructions, and study the result.  One easy target for cryptanalysis might use AES-256 in one of those forms, so that you could apply the Biryukov–Khovratovich related-key attacks.


We can choose a generator which is a primitive root. We can check that 1,7,11,12 are not primitive roots for p=19. So they cannot be chosen as a generator.Given any number we can check if it is a primitive root or not.
(https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number).


Understanding the elliptic curve equation by example

As fgrieu already mentioned, you forgot that the $y$ term in the elliptic curve equation is squared, so for $x= 1$ you have $y^2 = 1^3 + 1 + 1 = 3 \text{ mod } 23$. In order to solve the congruence $y^2 = n \text{ mod } p$ (where $p$ is a prime) you can use the following algorithm (Tonelli-Shanks):

Factor the powers of $2$ out of $p-1$, so in your case write $p-1 = 22 = Q2^S = 11 * 2^1$
Pick a value $z$ that is not a quadratic residue modulo $p$ i.e. there exists no $x$ such that $z = x^2 \text{ mod } p$. I picked $7$ at random and verified it's not a quadratic residue via Euler's criterion ($7^{\frac{23-1}{2}} = 22 = -1 \text{ mod } 23$)
Set the following values (all calculations done modulo $p$): $$M \gets S(=1)$$ $$c \gets z^Q(7^{11}=22)$$ $$t \gets n^Q(3^{11}=1)$$ $$R \gets n^{\frac{Q+1}{2}}(3^{\frac{11+1}{2}}=16)$$
This step involves looping until $t = 1$, which in our case is already true going into this step, so we have $y = R = 16$ as one of our solutions. The other solution can be found by computing $p - R = 23 - 16 = 7$.

Hence we have the two solutions $y = 16, y = 7$ when $x = 1$, yielding the points $(1, 16), (1, 7)$ as expected.


Yes, that's right. This is also why the key size can be much larger than the block size. The idea of a (well-distributed) key is that it pseudo-randomly chooses a function from X to Y.

So for instance AES can have a block size of 128 and a key size of 256 (and it has) because there are "only" $2^{256}$ keys while there are $2^{128}!$ possible functions / permutations. This is more explicitly explained here.


Computing Logarithm using homomorphic encryption

This answer is a bit messy, but it should work...

If we have access to a fully homomorphic encryption scheme $E(x)$ then we know that $E(x) + E(y) = E(x+y)$ and $E(x) \cdot E(y) = E(x \cdot y)$.

In addition we know that there exists an efficient Boolean circuit, $BC$, such that $BC(x_1,x_2,...,x_n) = y_1, y_2,...y_n$ where $x_i$ and $y_i$ are the bits of the binary string $x$ and $y$ respectively both of length $n$ and that $x = b^y$ for some base $b$.  Thus this is the circuit for $\log_b(x) = y$.

Now instead of being given $E(x)$ we can just as easily be given $E(x_1), E(x_2), ..., E(x_n)$.  When you want to encode a $0$ you map it to a random even number, $b$, then you encrypt that number, $E(b)$.  Likewise for $1$, except you map it to an even number.  Now all we do is evaluate the circuit and when we encounter an xor gate we do $E(I_1 \oplus I_2) = E(I_1) + E(I_2)$ and likewise for and gates $E(I_1 \wedge I_2) = E(I_1) \cdot E(I_2)$ where $I_1$ and $I_2$ are the inputs to the gate.  For all other gates convert them into $and$ and $xor$ gates.  At the end we will be left with $E(y_1), E(y_2),...,E(y_n)$ which is an encryption of the $\log_b(x)$.

One interesting benefit is that $x$ and $y$ could be represented in any way, not just a n-bit integer.  You would just need to use the correct circuit for the representation.  For example if $n = 64$ you could let $x_1,x_2,...,x_n$ be the IEEE 754 double-precision binary floating-point format representation of $x$ and with the correct circuit $y_1, y_2,...y_n$ would be a double-precision floating-point so you can do more precise calculations if you wanted.

See What does "circuits" mean in Cryptography? for more details on the Boolean circuit only using addition and multiplication.

Edit:

Since the question originally asked how to get from $E(x)$ to $E(log(x))$ and my answer only works if you have the bits and returns bits, I asked another question Fully Homomorphic Encryption: Going from an integer to bits to try to help.

They suggested using a Bit Extraction Circuit to go from $E(x)$ to $E(x_1), E(x_2), ..., E(x_n)$.  Then compute the above.  Now you have $E(y_1), E(y_2),...,E(y_n)$ which you can easily put back together by computing (assuming $y_1$ is the least significant bit) $E(log(x)) = E(y_1) + 2\cdot E(y_2) + 2^2\cdot E(y_3)+\dots+2^{n-1}\cdot E(y_n)$


Dynamic accumulator with only non-membership witness

This is not a correct dynamic accumulator scheme.

Your scheme assumes that the following holds: if $a,b$ are primes and  $0< a,b < p$, then $$(a,b)=1 \implies (ab\mod p,a)\neq1. $$ If this is true, then your scheme is correct, however this is not the case.

Toy example: $p=11,a=5,b=7$. Since $ab \mod 11=35 \mod 11=2,$ therefore $A=2$. Now, it is clear that security does not hold, since one could prove false non-membership statements. The reason for that is: $(a,A)=1=(b,A)$. Meaning one can prove that $a$ and $b$ are not accumulated however they were indeed added to the accumulator. For instance $(2,1)$ is a a non-membership witness for $5$, when $A=2$, since $5*2+2*1 \mod 11 = 1$.


Good practice to separate RSA key pairs used for encryption and digital signatures

I can answer this as follows:

If Alice would decrypt a random "ciphertext" for Bob and then return the decrypted message then Alice would have created a signature. Bob simply sends the required input to create a signature by performing modular exponentiation with the private exponent (or CRT parameters, of course). This would however only work for plain/textbook RSA decryption, which is not something you should use in practice.
Key management reasons:

a. You may always want to decrypt your stored ciphertext, but you may not always want to generate signatures with that particular private key.

b. You may not want to make your private key available for the other operations if you only require to perform decryption or signature generation.

c. Flexibility. Maybe you want to put one key pair on a smart card and keep the other in memory. Maybe you don't want to install the signature key on a device that just needs to perform decryption. Protect one with a PIN or password and use the other in an automated environment.


A true random number generator (TRNG) usually consists of two components: an “unpredictable” source with high entropy, and a randomness extractor — a function which, when applied to the source, produces a result that is statistically close to the uniform distribution. When the output of a TRNG is used for cryptographic needs, it is prudent to assume that an adversary may have some (limited?) influence on the distribution of the high-entropy source.

Thus it takes a bit of work to obtain randomness and there are many pitfalls.

If it's done well, the statistical randomness of the extractor’s output can be proven, and is not based on any unproven assumptions, such as the security of cryptographic hash functions. On the other hand output rates may be slow, and ensuring outside physical influences are thwarted may not be always possible. Obviously thermal noise in a circuit may be influenced by other factors.


Using a hash of data instead of the full raw data for authenticated data in AES-GCM

If I understood you correctly, you will hash everything you need to authenticate and include that in the AAD. This will be secure, as long as the hash is a secure collision resistant hash function. However, I don't understand what you gain. You can compute on all of this data in the AAD but only send what is necessary for reconstructing it. In this way, you don't have to store/send anything more than needed. In addition, the GCM authenticator is actually much faster than SHA256/SHA512, so it will also be more efficient.


Elliptic curve with prime subgroup equal to field size

It seems that curves like that do not exist.

Hasse's bound states that $|N-(p+1)| \le 2\sqrt p$, where $N=\#E$. Writing the order of the group as $N = ph$, you get:

$|ph-(p+1)| \le 2\sqrt p \rightarrow$

$|p(h-1)-1)| \le 2\sqrt p \rightarrow$

$|\sqrt p(h-1)-\frac{1}{\sqrt p}| \le 2$

The only way this inequality is true for $p > 5$ is if $h = 1$, i.e., $\#E=p$.


Section 4 of [P16] is perhaps the key section to read. I quote it below:

We stress that all these insecure instantiations—excepting [EHL14], for which the following conclusions still apply—are for the “non-dual” version of Ring-LWE with spherical Gaussian errors relative to $R$ (in the canonical embedding). By contrast, the definition of Ring-LWE from [LPR10], and the instantiations having worst-case hardness, involve spherical errors relative to the dual ideal $R^\vee$ (see Section 2.3.2).  When the insecure and hard instantiations are transformed to be directly comparable, the resulting error distributions turn out to have very different widths and shapes. We return to this point in Section 5, where we show that the hard instantiations are immune to the attacks from Section 3

In fact, this can be understood to be the key difference between Ring-LWE and Poly-LWE --- whether LWE samples:
$$(a(x), a(x)s(x) + e(x))\in\begin{cases}R_q\times R_q^\vee & \text{RLWE}\\ R_q\times R_q & \text{PolyLWE}\end{cases}$$
Note that these are almost equivalent. In particular, at the end of section 2 of [P16] there is a heading called Equivalence of dual and non-dual forms where it is shown that they are equivalent up to the resulting choice of error distribution. And for power-of-two cyclotomics, it is known that this change is multiplication by a small constant, i.e. by a transformation that simply scales the covariance matrix of the underlying error distribution. In general the distributions are related by a certain linear transformation, but it need not be this simple.
[P16] points out that this means that the attacks on weak instances of PolyLWE are implicitly attacks on RLWE, and that the attacks are induced by not accounting for the aforementioned change in the underlying error distribution (which does vary depending on the underlying choice of ring).
This means on the RLWE side of things, the error was too small, so the worst-case to average-case reduction was not valid (and therefore the PolyLWE attacks do not imply IdealSVP algorithms, as you might have otherwise expected).


Probability distribution function in Regev Cryptosystem

Neither of the alternatives in your question is completely correct.
The distribution $\Psi_{\beta}$ is as defined by equation (7) in Section 2 of your reference:
$$\Psi_{\beta}(r) = \sum_{k = -\infty}^{\infty} \frac{1}{\beta}\,\exp\left(-\pi \left(\frac{r - k}{\beta}\right)^2\right),$$

for $r \in [0, 1)$. So $\beta$ is not the standard deviation of a normal distribution (instead, the standard deviation is $\beta / \sqrt{2\pi})$. Note that $\Psi_{\beta}$ is not a normal distribution though, but a "periodization" of normal distribution.

Also keep in mind that $\bar \Psi_\beta$ is a discretized version of $\Psi_\beta$, i.e. the distribution that you get after multiplying by $p$ and rounding to the nearest integer mod $p$. This is why the introduction mentions that $\bar\Psi_{\alpha}$ has (roughly) the shape of a normal distribution with standard deviation $p \alpha$.


Why encrypting with private and public keys produce the same result?

No, you wouldn't always get that - in fact it's very unlikely behavior (eg the wikipedia worked example).

If encrypting with the public and private exponents was always the same you'd be able to decrypt someone else's message $c$ by calculating $c^e=c^d=m$.

It is important to realize that (after running the RSA setup algorithm) there is algebraically no reason you couldn't swap $e$ and $d$, since $d=e^{-1}$ and thus $e=d^{-1}$ (all modulo $\varphi(N)$). However, it is unlikely that $m^d$ and $m^e$ would be equal.

In the question you link to, using the "wrong" exponent is done to cheat: it demonstrates a potential flaw in the encryption scheme. In the forgability game, we say the adversary 'wins' if they manage to create a pair $(m,s)$ such that $s$ is a valid signature for $m$, without asking the legitimate signer to calculate a signature of $m$.

So, consider what a valid message signature pair actually is (in textbook RSA signing): The pair $(m,s)$ is valid if $m=s^e\pmod N$. Now, since the public key is $(e,N)$, the adversary can cheat a bit. Instead of picking the message that he wants signed, he instead picks the signature. Having picked $s$, he now calculates $m:=s^e \pmod N$. This leaves him with the pair $(m,s)$, which by construction must be valid.

Notice that he doesn't have a clue what the message $m$ actually says, but we do know that $s$ is a valid signature for it. This is why real-world RSA signing uses a secure padding scheme: a message $m$ created in the way I describe above is very unlikely to have valid padding.


Padding schemes reversal and space efficiency

The more space efficient but cannot always be reverted, for instance if one inputs $m = 1$.
The second space efficient but can always be reverted, this appears in Wikipedia entry as bit padding.
and 4. They consume the same space (which is greater than 1. and 2.) but also, they're always reversable.


What are the chances that AES-256 encryption is cracked?

He told me there are only two encryptions that he knows of that cannot be broken, and AES is not one of them

This tells me you asked your professor the wrong question.  You asked a cyber security expert if an algorithm could be cracked, to which the answer is always yes, with the exception of a handful of inconvenient algorithms, such as One Time Use Pads used in exactly the correct way.  Even in those cases, there's exploits to worry about.

AES-256 is an algorithm.  It can be broken.  If you look at the history of cryptography, every algorithm gets broken eventually.  That's why we make new algorithms.  The question is how long it takes to figure out the math to break it.

The real question to ask is "what is your threat model?"  What sort of attack are you trying to prevent?  Are you creating a digital lock on a diary to keep it safe from your sister's prying eyes, or are you Edward Snowden, on the run from several three letter agencies with billions of dollars of funding?

AES-256 is currently labeled as sufficient to use in the US government for the transmission of TOP SECRET/SCI information.  That's pretty much the highest classification level they could clear it for, so the US government is pretty darn confident that nobody can break AES-256 on the timescales required to protect our nation's greatest secrets.

(Well, almost.  What it really says is that they are confident that nobody outside of the US government can break AES-256.  What you believe that that says about whether the US government, themselves, can break it depends on your threat model... and whether you engage in discussions of whether heavy-duty tin foil  makes better hats or not)


This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper Limits on the provable consequences of one-way permutations by Impagliazzo and Rudich.


The article is surely wrong.

Nowadays, the sole purpose of client-side private key in SSH is to sign messages (as their algorithms are typically ECDSA EdDSA, etc), the server doesn't encrypt the challenge, it almost certainly verifies it with the public key(s) in the authorized_keys file


How to generate different hash values for same files/messages?

You should use a cryptographic salt.
This is a single use number generated for each hash. The salt should be prepended to the file to be hashed before hashing. The salt and hash value can then be stored together. Now if you want to compare a file against a given hash you prepend the salt, hash and check against the stored value.
Provided that the salt values are unique, you should not get repeated values (subject to the birthday bound).


Chosen Plaintext attack on AES in ECB mode

Suppose we have a block cipher that takes a 16 byte plaintext and produces a 16 byte ciphertext (that is to say $\mathcal{Enc}: \{0,1\}^{128} \rightarrow \{0, 1\}^{128}$). We use this block cipher to encrypt two blocks worth of unknown data, call them $m1$ and $m2$. Additionally we are allowed to prepend some data to these two blocks, let's call it $m0$ (we control this data).

Note that in this scheme nothing prevents us from choosing an $m0$ that is 16 bytes long. This means we effectively have an encryption oracle for a full block, since the first block returned in this case would be $\mathcal{Enc}(m0)$ if ECB mode is being used. This means we can get the encryption of arbitrary blocks of data, which will come in handy.

You correctly state that we can set $m0$ equal to 15 known bytes, and if we have an encryption oracle we can brute force the last byte:

 Block 1          Block 2  Block 3
|AAAAAAAAAAAAAAA?|?......?|?......?|
 |----known----||--m1---|

We just have to send all 256 possible guesses for Block 1 to the encryption oracle and see which one matches the output. Let's say we get a match on the byte encoding "w". We then repeat the process with a one byte shorter $m0$ to get the next byte in the same fashion:

 Block 1          Block 2  Block 3
|AAAAAAAAAAAAAAw?|?......?|?......?|
 |----known----|

We can repeat this process for each byte until we have the whole first block $m1$, which let's say is "we attack at daw". Unfortunately at this point we can't reduce $m0$ by any more bytes since $m0$ would be 0 bytes and we would simply get:

 M1               M2
|we attack at daw|?......?|
 |----known-----|

But we since we now know all of $m1$ we can use the sort of attack we used to recover the first byte of $m1$ to recover the first byte of $m2$. Suppose we again choose $m0$ to be of length 15 bytes:

 Block 1          Block 2          Block 3
|AAAAAAAAAAAAAAAw|e attack at daw?|?......?|
 |------------known-------------|

There's only one unknown byte in Block 2 so all we have to do is again submit all 256 guesses to the encryption oracle, except this time for Block 2 instead of Block 1! This process can be repeated to decrypt an arbitrary amount of ciphertext that is ECB encrypted as long as we can prepend data to the plaintext and have access to an encryption oracle.


They are de facto conventions that somewhere may not being followed. I think the one you mention has started with the P1363, but not sure if there is something previous.

It is the first thing one have to check in any document: which is the naming convention followed there. Perhaps also is useful to see from there some of them comes. The Weierstrass Normal Form (or WNF) can be saw as:

$y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}$

And usually uses it reduced form when is defined over $\mathbb{F}_{p}$ as:

$ y^{2} = x^{3} + ax + b $

On characteristic 2 ($\mathbb{F}_{2^m}$), I think is more usual the form:

$ y^{2} + xy = x^{3} + ax^{2} + b $

Different names for the same parameters and even mixing them. Not forgetting that there are many more curve representations, one each you can find even different conventions.

Then points naming can change from one document to another, where is usual to see $G$ as the generator (also represented as $<G>$), but cannot be assumed because you can see a $P$ or $Q$ or $R$.

I think coherence is important and where ever it's used, the convention must be described at the beginning and followed to the end. This convention you mention, perhaps is the more spread.


Hashing a counter to prevent distinguishers in CTR mode

I'm reading the question as generating a keystream per: $S_i\gets E_K(F(\mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $\mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.

That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $i\ne j$ and $F(\mathrm{IV},i)=F(\mathrm{IV},j)$, can be found by an adversary from the public $\mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.


The LWE assumption tells you that $(\mathbf{a},\mathbf{a}\mathbf{s}+e)$ looks random for a hidden random vector $\mathbf{s}$, a random vector $\mathbf{a}$ and small error $e$.

Invoking the LWE assumption k times, you get that $(\mathbf{a},\mathbf{a}\mathbf{s}_1+e_1,\mathbf{a}\mathbf{s}_2+e_2,\ldots,\mathbf{a}\mathbf{s}_k+e_k)$ is indistinguishable from $(\mathbf{a},b_1,b_2,\ldots,b_k)$ where the $b_i$'s are random values.

So $(\mathbf{a},\mathbf{S}\mathbf{a}+\mathbf{e})$ is indistinguishable from $(\mathbf{a},\mathbf{b})$, and if an adversary has advantage $\varepsilon$ in distinguishing those 2 distributions, there is an adversary that has advantage $\frac{1}{k}\varepsilon$ in distinguishing LWE samples from uniform, where $k$ is the dimension of the vector $\mathbf{e}$.


Is it insecure using addition instead of multiplication in Elgamal encryption?

In the generic sense of an abstract group, this is a problem since addition may not be defined. However, when working modulo a prime $p$, addition is certainly defined. However, it is not secure. In order to see why, note that we must work in a prime subgroup of $p$ in order for ElGamal to be secure. Thus, we typically choose $p=2q+1$ where $q$ is also a prime, and then we work in the subgroup of order $q$ of quadratic residues. When you add, you may get out of the subgroup.

A description of an attack when addition is used A Simple Attack on ElGamal Public Key Encryption by Dan Boneh (the paper deals with something else, but also considers addition as motivation).


Cryptanalysis of MD4 (Wang et al) -- how did the authors come up with the collision differential?

I've found the following tweet:

  [...] all the papers I've read say that she found the right difference patterns by "intuition"

(https://twitter.com/ghostly_gray/status/906009834755055617)

I'll happily accept another, more specific answer!


Do other one-time signature schemes exist?

HORS (Hash to Obtain Random Subset) is a simple few-time signature scheme with smaller signatures than BiBa.

Let $f$ be a one-way function and $H$ be a hash function that outputs a random size $k$ subset of $\{1,2,...,t\}$, where $k$ and $t$ are parameters that affect security with $k < t$.

The signing key is a random tuple $(s_1,...,s_t)$, and the public key is $(f(s_1),...,f(s_t))$. Now
to sign a message $m$, compute the set $S = H(m)$ and output $\{s_i : i \in S\}$. To verify, apply $f$ to each element of the signature and check this matches with the public key.

Each signature reveals $k$ elements of the secret key, so depending on the choice of $k$ and $t$, a few messages can be signed before security is compromised.

This was used as a building block in SPHINCS, which is a stateless hash-based signature scheme that allows unlimited messages to be signed (but is much more complex).


Understanding the Pohlig-Hellman algorithm

Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\alpha^{p_i(p-1)/p_i}(=1)\}$. Since $y^{(p-1)/p_i}\in G_i$, there exists a unique value $b_0\in \mathbb{Z}_{p_i}$ such that $y^{(p-1)/p_i}=\gamma_i^{b_{0}}$. To compute $b_0$, you can for instance apply the baby-step giant-step algorithm.


Can you recognize a low private exponent from a public key?

When generating keys, $d$ and $e$ are each others modular inverse:

$d \times e \equiv 1 \pmod{ \lambda(n)}$
$d \times e = 1 + k \times \lambda (n)$

Unless $d = e = 1$, this means that $d \times e$ is at least $\lambda(n)$, otherwise it would not "wrap around" to become $1$. So $k$ is at least $1$:

$d \times e \ge 1 + \lambda(n)$

This means that at least one of $d$ and $e$ is at least $\sqrt{1 + \lambda(n)}$, otherwise they wouldn't multiple to be greater.

$d \ge \sqrt{\lambda(n)}$, or $e \ge \sqrt{\lambda(n)}$

If we set $e = 65537$, it must be $d$ that is large. It is not possible to have a key with a low private exponent that also has a low public exponent. A key with a low private exponent has to have a public exponent that is at least $\sqrt{\lambda(n)}$.


True/False if a user is a customer without revealing the actual customer

A 1-out-of-n Oblivious Transfer protocol would fit as a solution to your problem.

Oblivious Transfer can be viewed as an improved Private information retrieval protocol, because it allows that only exactly 1 item is retrieved from the database, without sharing any additional info about the database. In addition the "sharer" of the database ($B$) doesn't learn about which item ($A$) was retrieved.

If $A$ is not a customer of $B$ then $B$ should only return information in a way to make it clear to you that $A$ indeed is not a customer and not any information  more should be disclosed by $B$.

Tung Chou and Claudio Orlandi have designed a relatively easy to understand 1-out-of-n OT-protocol, appropriately named The Simplest Protocol for Oblivious Transfer. The math used for this protocol is almost the same that is also used for Diffie-Hellman key exchange.

If you really want a computationally efficient protocol, then the OT-protocol designed by
Moni Naor and Benny Pinkas (Computationally Secure Oblivious Transfer) is more appropriate.


Any unique identifier would do the trick, including using a hash of the key (assuming you are using a good hash function). Personally I would not use a hash of the key though as it makes an offline attack theoretically possible. If the ID has nothing to do with the key, however, and an attacker steals the ID, there is no advantage gained by the adversary. A simple counter would do the trick. If you indeed need the ID to be globally unique though, simply having everyone generate a random 128 bit number would also work.


Simple example to describe Bilinear mapping

A toy example would be this simple map with $\mathbb{G} = \mathbb{Z}/5$ to $\mathbb{G}_T = \mathbb{Z}^*/11$, as follows:

$$e(x,y) = 3^{xy} \bmod 11$$

It's easy to verify that both equations hold (except that $e(0,0) = 1$; that's actually a necessary consequence of the first equation, and so I'll consider that an acceptable exception).

Of course, even if you scale this up to non-toy sizes, this particular style of bilinear mapping isn't cryptographically interesting; however it does answer your question.


Can a proof be constructed to show there is no distinguisher?

There are a number of distinguishers that it it would be easy to prove are not present in a hash function.

For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property (which should be fairly easy to find).

For more interesting distinguishers, the problem becomes much harder (on a side note, is the distinguisher really interesting if I can prove it doesn't hold for a particular hash function?).

My gut feeling is that yes, one could come up with an "interesting" distinguisher and then show that it doesn't hold for the hash function, but I can not offer more than a gut feeling.


Value of S and r in Fiat-Shamir Protocol

It's the same situation as for RSA encryption. If you accidentally pick a bad $s$, i.e. one that's not coprime to $N$ then the protocol fails. How likely is this to happen? If you hit a bad $s$, then you can find the factors of $N$, hence you can break the protocol - put another way, finding a bad $s$, whether deliberately or by accident is no easier than factoring $N$ and breaking the whole thing anyway. And the whole reason that you're doing a protocol in an RSA group in the first place is because you believe that your $N$ is big enough that it's infeasible to factor.

As for whether the boundaries $1$ and $N-1$ are included, this really doesn't matter either - if your $N$ is large enough then the chance of accidentally hitting the boundary when you sample uniformly from $[1,N-1]$ is $2/N$ which is tiny.


Yes, both textbook and practical RSA can reversibly encrypt $p$.

Textbook RSA can encrypt and decrypt any plaintext in $[0,N)$ as long as $N$ is squarefree (which is hypothetized or at least overwhelmingly likely); and that's including $p$. In a nutshell: Fermat's little theorem implies that $M^{e\,d}-M\equiv 0\pmod p$ for any $M$ and any prime $p$ dividing $N$. It follows that $M^{e\,d}-M\equiv 0\pmod N$ if $N$ is squarefree. Correct decryption for any $M\in[0,N)$ if $N$ is squarefree follows. See more detailed proof there.

However, encrypting $p$ is a particularly terrible use case of textbook RSA, because revealing the ciphertext allows factoring $N$ by computing $\gcd(\operatorname{Enc}(p),N)$ ; that's $p$, as explained there.

Practical RSA has no problem encrypting $p$ for many common parameters: the RSAES-OAEP encryption scheme in PKCS#1 can encipher octet strings of up to $\lceil (\log_{2}N)/8\rceil-2h-2$ octets, where $h$ is the width fo the hash in octets, and that's enough for $p$ when $N$ is larger than $4h+4$ octets and has factors of equal size, which is typically the case. RSAES_PKCS1_V1-5 has a slightly different capacity. When $p$ does not fit (e.g. 2048-bit RSAES-OAEP with SHA-512 has a capacity of 126 octets, which is typicality 2 octets short for $p$), the plaintext can be split into several cryptograms, or there's hybrid encryption.


Are the definitions of IND-CCA secure and of IND-CCA secure under standard model identical?

A cryptosystem is not "based on an assumption" ; it is based on some mathematical structure (e.g. prime order elliptic curves, or prime order fields). Informally, a cryptosystem is said IND-CCA secure (which means: it satisfies the indistinguishability security notion, against adversaries which are given access to a decryption oracle) under some assumption A if given access to an adversary that breaks the IND-CCA security of the scheme, one can construct an algorithm breaking A.

But you cannot say that "A is the problem on which the cryptosystem is based": for a given cryptosystem, different security notions can be based on different assumptions. For example, take the case of ElGamal: it is IND-CPA secure under the DDH assumption, and (a slight variant of) it was also proven IND-CCA1 secure (CCA1 indicates that the adversary can make decryption queries only before receiving the challenge ciphertext - this is also known as security against lunchtime attacks), but only under a very different and less standard assumption (see this paper for example, or some of the related papers it mentions in the intro).

So when a cryptosystem is said to be IND-CCA secure, it does not tell anything about the assumption on which it is based.

The term "in the standard model" relates to a completely different things (it does not say anything either on the particular computational assumption to which a security notion for the scheme can be reduced): it is common in crypto, when dealing with a hard problem, to consider simplified "worlds" in which the players could have access to some ideal primitive, and then to instantiate this primitive "in practice" with something which seems a good candidate for this ideal primitive, based on our current understanding of it.

The most common example is that of the random oracle model: we assume that the players are in a world in which they have access to an oracle which acts as a truly random function, and then we prove that some cryptosystem is secure (e.g. IND-CCA secure) under some computational assumption in this simplified world. This does however not prove that in the real world, the cryptosystem would be secure; using SHA-256, for example, as a random oracle seems to work in practice, but SHA-256 is not a random oracle.

Saying that something is secure in the standard model is just a way to say that no such idealized world is considered: the proof is "in the real world" and does not assume any idealized primitive.


How were the number of rounds for different key sizes of AES selected?

There are two reasons:

More rounds means more security against cryptanalysis, simply, since there is more confusion and diffusion.
For a secure block cipher, there should be no attack faster than exhaustive key search (i.e. brute force). As exhaustive key search takes a lot longer for a larger key size, a theoretical attacker can afford more work to "break" the larger cipher. Thus we also increase the round number a bit to increase the security level of our cipher accordingly.
For a larger key size (as well as a larger block size), we need more rounds so that every key bit affects every ciphertext bit in a similar way, i.e. without measurable differences which would allow any cryptanalysis.

The 10 rounds for AES-128 seem to be about the lower level of what is (approximately) 128-bit-secure, and 10 rounds for a AES-256-like-cipher would have way below 256 bits of security.


RSA: Fermat's Little Theorem and the multiplicative inverse relationship between mod n and mod phi(n)

You are misunderstanding Fermat's Little Theorem (or rather, its more general form as Euler's Theorem) which does not state that a multiplicative inverse modulo $\varphi(n)$ is the same modulo $n$. What the theorem says is that if you have an integer $a$ coprime* to $n$, then the following is true:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

In other words, the order of the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$. In other words, the relationship above induces a cyclic order on the powers of $a$ modulo $n$, meaning if you keep multiplying $a$ with itself you will eventually get $1$ (not necessarily after exactly $\varphi(n)$ exponentiations, but Lagrange's theorem says that if $k$ is the smallest nonzero $k$ such that $a^k \equiv 1 \pmod{n}$ then $k$ must divide $\varphi(n)$. Perhaps more intuitively, it (informally) means that powers of an integer modulo $n$ behave as if they were taken modulo $\varphi(n)$. Note this says nothing about multiplicative inverses being the same.

So what does this mean? It means that when you raise a plaintext $M$ to the power $e$, you get:

$$M^e \equiv C \pmod{n}$$

So how exactly do you decrypt this? One possibility is to take the $e$th root modulo $n$, but this is expensive and problematic. Fortunately, there is another way. Since we know from above that:

$$M^{\varphi(n)} \equiv 1 \pmod{n}$$

It follows that, for any integer $k$:

$$M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

So we just need to find an integer* $d$ such that $ed = k \varphi(n) + 1$, that is, $ed \equiv 1 \pmod{\varphi(n)}$. Then:

$$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

And this is why it works. You are choosing $e$ and $d$ multiplicative inverses of one another modulo $\varphi(n)$ precisely so that their product is congruent to $1$ modulo $\varphi(n)$, and Euler's theorem does the rest. If you are observant you will notice the rule $(M^e)^d = M^{ed}$ really is what makes RSA work as a public key scheme by separating $e$ and $d$, and this is exploited in Diffie-Hellman and some other public key schemes as well.

This doesn't however work if you had chosen $ed \equiv 1 \pmod{n}$, because $kn + 1$ doesn't actually mean anything modulo $\varphi(n)$. There is no structure to be exploited here, and you will just get an arbitrary number that won't help you decrypt $C$. In the same way, multiplicative inverses modulo $n$ do not "carry over" modulo $\varphi(n)$. There is a relationship between integers modulo $n$ and integers modulo $\varphi(n)$, but it is not that simple (I just described that relationship above), and you have to work with that relationship to make your algorithm work.

So the answer to your question is really "because this is how arithmetic works out modulo $n$" :)

* in fact RSA "works" even when the plaintext is a multiple of $p$ or $q$, but never mind that now.

* in practice, $\varphi(n)$ is sufficient but not necessary, and we use $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ (the Carmichael function) which is basically $\varphi(n)$ with any prime factors shared between $p - 1$ and $q - 1$ left out - this means we still have all the nice properties that we require for RSA, but with the numbers involved as small as possible (but still secure, of course - knowledge of either $\varphi(n)$ or $\lambda(n)$ is polynomial-time reducible to factoring $n$, so knowing one is equivalent to knowing the other).


Capacity of Advanced Encryption Standard in terms of File Encryption

If you mean how much data can safely be encrypted by AES with a single key (and IV), AES is designed to encrypt up to $2^{64}$ blocks of data before becoming susceptible to certain statistical attacks (in particular distinguishing the encrypted file from truly random data), because of its 128-bit block size. 8GB (= $2^{36}$ bits = $2^{29}$ blocks) is quite below this limit, you are fine.

That said, AES-OFB alone is not enough, as it is a streaming mode the plaintext can be altered rather trivially assuming it is partially known beforehand. You will want something like a HMAC on top to ensure the file does not get corrupted by an attacker at some point (note that this does not mean a block mode like CBC does not need one - it does, but plaintext cannot be altered in such predictable ways)


It seems like an authentication protocol. In the first message, $S$ identifies herself. In the 2nd message $D$ proves knowledge of her private key (otherwise she could not return $N_s$. In the third message, $S$ proves knowledge of her private key.

You asked in a comment about replay attacks. There are two possibilities, the attacker is impersonating $S$ or $D$.

For $S$, the attacker might replay a captured 1st message. $D$ would see it, decrypt, return $N_S$ with a randomly generated $N_D$. The attacker could not possibly know what $N_D$ is and could not send the last message.

For impersonating $D$, $S$ would send the first message, but the attacker couldn't decrypt it and therefore could not send the 2nd message.

So, it seems the protocol is secure against replay attacks.


Different kind of PGP keys or IDs, how to interpret them?

Exchanging full RSA keys can be very inconvenient, as they consist of very long numbers. In the OpenPGP ASCII-armored version, my public key (without any user IDs and certifications!) already is very long stream:

mQQNBFDaK/sBIADm2gjnw7aPoNIoCy7gj85btwZU+zGkvtGonznlLrXELdU6zR3u
VHNCn9vAl6OoU32r+suFvGdX+7MjiPbGKwJFOvICpAVh6bV55+hdqJbS02cpPmJH
1BrrUAmm6ZVEybGd+II1pTI6Mt/SAI1E/59VIBdC/1AwsxQtCTFeyaLqTdyd1FhQ
chkjcvdRHLb4cEqldAGqBL7SbiSNOP3p+vX8iwRN6PQ/erAGseawHnunuNIna+tA
t4te/MkI2uxT0KjsfF/NWHCB2aXt++egP8jGSaHRsVOlfHRVA3hHcUDlnW9DZRvG
QabHFcZvfcXAlNIRYKUzDIHEwpavAmHeGNhc2GNmDcDRF56741grVLNQT58vxK5o
dBLlC8ANckvE5ymdIKVPm+t5q10kFOAATcnmDV0oBt+15vzI3f+88yCoY904UWdY
LwTbNMiszIB4ngNfzdLWeXPOCDs4CYa9BBKb1VkVtWn6NTE7m0/urrAP3Mb9qTwz
AlBVHvDPo6BG2yVqoCVzDBNOjb7czO3cns2M8sThizD2gvdKUV5Bq7THp6MFAzP0
Wbad3JLVIn65BNzVKJYhC7rGAU2QjlRbXq+P08NsewNbFC/E3fct249PM5xVl4lW
vcsqBo1o+iuHuzb7tvveht1N79n3V+pPISLj8QCb9rEI09MJ93IQbn5yuyPCgXe6
/OiNyiv3QxY/x3zImLiiuSurbw1E0ILyX/qm+36XVSpewduXk2yen8x+eMmLWRfS
ZhyPXHFbO8am7niF1AuZjnIfhETsiyqAGmYmb9d7nL6GwCrvA7QCHrRl/EDd4r2a
Un2q6QYXQ78Wj6Ys1/jH49GkFUhBKl0PfLKtKPiPwL71wb6sD6nA30Ix6hMGreZk
B1697KPVLCP4v87xyrMJFNgXC2FBKML3PlokOyrZzbXLRM78yHmoBl13Tu3UZkFK
O1TV7cFzQScHMd+yBGN/AmVUF8Br2bExtuIvQqoQbj6gPIEk5xGWvGzSbR9LcAng
VRUHDlOy3dUd8QuhJANPk6knHZR0OT0C5c2Wzvcznr5ros5PQ8XZFCOJTaNLfc7u
9TGe/FVG3d7RMyB/9ILhS5ef3VarGzuyiYwwsC3P+w/3lHt+PhzVQRfeq0WrB+RK
3bfweIm30k1g8xJuQ0mg2JmmICYL/uihWVREZNOZZPboFBV8dZec+hif1tfuqchV
qVsy3cMuhg/K/EJafVbA3o59Z9IYIC3XN7NGoYYXuzbLgaDtVxGdcWTg8D4a1FaD
cEkeAR/Mm9FxVDK01itXatol/ZB0oBCrYS0DLdYQ/YWrAfoqR7Av7uY+hQiwvIo3
+lVlQGsr7rlhv/oNrf2P2M5aKPOdp2vPIEqpABEBAAE=
=pzM1

For this reason, the public key gets hashed into the key's fingerprint. From RFC 4880, 12.2 Key IDs and Fingerprints:

  A V4 fingerprint is the 160-bit SHA-1 hash of the octet 0x99,
     followed by the two-octet packet length, followed by the entire
     Public-Key packet starting with the version field.  The Key ID is the
     low-order 64 bits of the fingerprint.

Long and short key IDs are the last 16 respectively 8 digits. Again with my own public key as an example:

fingerprint: 0D69 E11F 12BD BA07 7B37  26AB 4E1F 799A A4FF 2279
long id:                                    4E1F 799A A4FF 2279
short id:                                             A4FF 2279

As the fingerprint and key IDs are derived from the public key through hashing, you cannot "convert them back" to the public key. So while they cannot be used immediately for cryptographic operations and must query a key server using them as search token, you can exchange them more easily, for example on business cards. Be aware that short key IDs are insecure and should not be used.


Several issues:

(Typo now fixed) $g$ and $G$ where visually different, I do not see a reason why.
(Fixed by now using secret value where there was secret key) When enciphering, one does not need a secret key; the deciphering party is assumed to know the private key matching the public key, and keep it secret. The $k$ is the random secret nonce (number used once) drawn for encryption, not a "secret key". That's confirmed by $g^k\not\equiv y\pmod p$.
$y^k\cdot m\bmod p$ would be part of the ciphertext; something else is needed for successful decryption. Argument: $y^k\bmod p$ is essentially random for one not knowing $k$, thus so is $y^k\cdot m\bmod p$ for any particular $m$ coprime to $p$, thus $y^k\cdot m\bmod p$ can't allow recovering $m$ for one with no clue about $k$ (or something related).
Yes, that other component of the ciphertext is $g^k\bmod p$.
(My bad).
All $m$ with $1\le m<p$ are counted as having the same size. The ciphertext comprises two integers in $\Bbb Z_p^*$ while the plaintext is one, thus the ciphertext is twice as large as the plaintext. Cryptographers count the maximum size of message and cryptogram, rather than their actual size. As an aside they use bits or octets, rather than decimal digits, but the later is OK in the context of this exercise.
Non-negative integers strictly less than integer $p$ can all be expressed with $\lceil\log_b p\rceil$ digits in base $b$, where the notation $\lceil y\rceil$ is for $y$ rounded up to integer, and $\log_b(x)=\log(x)/\log(b)$; the base $b$ is $2$, $256$ or $10$ for bits, octets, or decimal digits.
We have $p-1=2\cdot59\cdot79$ when usually, in ElGamal, it is chosen $p$ prime with $(p-1)/2$ also prime, since that improves security against the Pohlig-Hellman discrete logarithm method. But since $p$ is way too small for security anyway, that' not a big deal. Or perhaps the next step is showing that attack at work to break the encryption; e.g. by recovering the private key from $y$, or recovering $k$ from $g^k\bmod p$.


Is the random oracle commitment scheme secure against PPT active adversaries?

There is no active attack an adversary could do, so the random oracle commitment is secure in (both the passive and) the active adversary model.


If you just want to provide a generic improvement I'd just target password hashing. If you think that directly running passwords through a cryptographic hash is history then I can show you plenty of StackOverflow questions where it is still being performed.

For a generic attack you don't need a new problem; just focus on your improvement and let your solution be interesting on its own merit.


Reason why “XOR” is a linear operation, but ordinary “addition” isn’t?

They are both linear, but in different algebraic Groups.  Which is to say, xor is linear in any finite field of characteristic 2, while 'ordinary' addition is linear in the infinite field of the Real numbers.  Addition modulo $n$ (which is more cryptologically significant than addition over the Reals) is also a linear operation, but in the ring of integers $\mathbb{Z}_n$.

A linear function is simply one that can be accurately described by an algebraic equation (in some particular algebra or another) where none of the terms are of degree greater than 1.

So the xor of two variables can be accurately described by a linear algebraic equation in a finite field of characteristic 2.  But there is no linear equation in the algebra of $\mathbb{Z}_n$ (for $n > 2$) that can accurately describe the xor of two variables.  Conversely, the addition modulo $n$ ($n > 2$) of two variables can be accurately described by a linear equation in $\mathbb{Z}_n$, but not by a linear equation in any finite field of characteristic 2.

If none of that made any sense to you, that's OK.  You just need to read up about Abstract Algebra, and Fields, Rings and Groups.  It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.


How can I calculate the SHA-256 "midstate"?

SHA-256 uses an internal compression function $f$ which takes two inputs, of size 512 and 256 bits respectively, and outputs 256 bits. Hashing works like this:

Input message $M$ is first padded by appending between 129 and 640 bits (inclusive), resulting into a padded message $M'$ whose length (in bits) is a multiple of 512.
$M'$ is split into $n$ 512-bit blocks $M_1$, $M_2$,... $M_n$ (each block has length 64 bytes).
Set $X_0$ (a 256-bit value) to a conventional initial value (which is specified in the SHA-256 standard, section 5.3.3).
Process each block in due sequence, by computing $X_i = f(M_i, X_{i-1})$ for all $i$ from $1$ to $n$.
The hash value is $X_n$.

The $X_i$ values can be seen as the successive contents of a state variable $X$ (indeed, when you have computed $X_i$, you can discard $X_{i-1}$ since that value will not be used thereafter).

Your "midstate" is $X_1$: that's the contents of the "state" after having processed the first block. Since all your 128-byte messages begin with the exact same 64-byte header, all the hash computations formally begin by processing the same block $M_1$, with the same $X_0$ (the conventional initial value), resulting in the same $X_1 = f(M_1, X_0)$. You would like to "restart" each computation from that value $X_1$ directly, to avoid recomputing it again and again.

Doing that over an existing library implementing SHA-256 may or may not be easy, depending on what facilities that library offers. For a basic SHA-256 library, there are two possible issues:

The library may refuse to output $X_1$, because it would insist on computing hash values over a padded message only; you want to have the output of $f$ over a given $M_1$ block without padding.
The library may refuse to start a new computation starting with the $X_1$ you provide instead of the conventional initial value $X_0$.

Some libraries offer a bit more. For instance, consider sphlib. With that library, there are two ways to achieve what you seek:

The implementation works over a context structure (of type sph_sha256_context) which represents the current state. You can thus begin a computation by processing the header, and then clone the context to make many hash computations which start from that exact point. It would look like this:

sph_sha256_context sc;

sph_sha256_init(&sc);
sph_sha256(&sc, header, 64);
for (/* all 128-byte messages */) {
        sph_sha256_context sc2;
        unsigned char second_half[64];
        unsigned char out[32];

        /* set second_half[] to the second half of the 128-byte message */
        sc2 = sc;
        sph_sha256(&sc2, second_half, 64);
        sph_sha256_close(&sc2, out);
        /* SHA-256 output is in out[] */
}

sphlib offers an sph_sha256_comp() function which implements exactly the compression function $f$. You can use it to compute SHA-256 "manually", block by block, starting from any state value $X$ you wish. You would have to take care of encoding issues (SHA-256 is big-endian throughout, use sph_dec32be() and sph_enc32be() to do that properly and portably) and padding. If all your messages have length exactly 128 bytes, then padding is always a full 64-byte block, consisting in a byte of value 0x80, followed by 61 bytes of value 0x00, and then two bytes of value 0x04 0x00. Expressed in 16 32-bit words, first word has numerical value 0x80000000, followed by 14 words of value zero, then a final word of value 0x00000400.

For heavy hash crunching (I understand that's the point), your best bet is still probably to extract the inner loop from an opensource implementation, and integrate it directly in your code, so as to avoid any overhead from the library API. You also probably want to avoid heavy encoding/decoding, and work over 32-bit words directly (while SHA-256 takes as input a bit sequence, it soon converts it to a sequence of 32-bit words and works over that). I invite you to do your own SHA-256 implementation, working from the standard: it is not hard, that standard is reasonably clear, and it will grant you enough knowledge on how SHA-256 works to optimize your code (even if you end up reusing parts of some other implementation).


How unsafe is to share parts of a password

If I know your password is k bits long and I know the m bits, then I have to brute force the rest of the k-m bits. That's the standard for any algorithm and independent of whether this is prefix, suffix etc. This means that I have $2^{k-m}$ tests to make.

However, you can even do better, You can say that you have a decayed version of the key, or you have partial key exposure, you have some plaintexts and the according ciphertexts. In this scenario, there are several effective attacks, even for AES, with different approaches, even SAT solvers. Have a look at the following papers:

Halderman, J. Alex, et al. "Lest we remember: cold-boot attacks on encryption keys." Communications of the ACM 52.5 (2009): 91-98.
Kamal, Abdel Alim, and Amr M. Youssef. "Applications of SAT solvers to AES key recovery from decayed key schedule images." Emerging Security Information Systems and Technologies (SECURWARE), 2010 Fourth International Conference on. IEEE, 2010.
Liao, Xiaojuan, et al. "Using MaxSAT to Correct Errors in AES Key Schedule Images." Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on. IEEE, 2013.

Of course there are limitations as you can see from the papers, but depending on how much bits you want to crack, it might be easier to go this way than brute force them.