Yes, (textbook) RSA works for any message $M \in \{0\dots n-1\}$, in the sense that the decryption procedure recovers the original message; that is $\left((M^e\bmod n)^d\bmod n\right)=M$. For this to hold, we need to assume $p\ne q$, a requirement not formally stated in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, but true with overwhelming odds given the method suggested to generate $p$ and $q$, and always true when following the recommendation given that $p$ and $q$ differ in length by a few digits.
An easy proof is to consider $Z=\left(M^e\right )^d-M$; show $Z\equiv 0\pmod p$ and $Z\equiv 0\pmod{q}$, by using Fermat's Little Theorem and the assumed relation between $e,d,p,q$ (see detailed proof below); then, since $p$ and $q$ are distinct and prime, and divide $Z$, their product $n$ divides $Z$; thus $Z\equiv 0\pmod{n}$. Q.E.D., thanks K.G.
Note: in general, $M^e\equiv M\pmod{n}$ does not hold.
Note: if $p=q$, the cryptosystem is totally unsafe. Independently, those rare $M$ that are a non-zero multiple of $p$ are modified by encryption followed by decryption.

Detailed proof (following another question): we want to show that $Z=\left(M^e\right )^d-M$ verifies $Z\equiv0\pmod p$, that is $\left(M^e\right )^d-M\equiv 0\pmod p$, that is $M^{e\cdot d}\equiv M\pmod p$. Since $d$ and $e$ are integers greater than $1$, this holds if $M\equiv0\pmod p$; it remains to prove it only when $M\not\equiv0\pmod p$, which we assume in the following.
The original RSA article constructs $d$ and $e$ with $e\cdot d\equiv1\pmod{\phi(n)}$, where $\phi$ is the Euler totient, also noted $\varphi$; while modern expositions of RSA, including PKCS#1 of RSA Security, often use $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function. We hypothesized that $p$ and $q$ are distinct primes, thus $\phi(n)=(p-1)\cdot(q-1)$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. Thus $p-1$ divides $\phi(n)$ and $\lambda(n)$, and for either construction of $d$ and $e$ it holds that $e\cdot d\equiv1\pmod{(p-1)}$. Since $e$ and $d$ are integers greater than $1$, it therefore exists a positive integer $k$ with $e\cdot d=k\cdot(p-1)+1$.
We can thus write $M^{e\cdot d}$ as $M^{k\cdot(p-1)+1}=\left(M^{p-1}\right)^k\cdot M$. By Fermat's Little Therorem, since $p$ is prime and $M\not\equiv0\pmod p$, it holds that $M^{p-1}\equiv1\pmod p$. It follows that $M^{e\cdot d}\equiv M\pmod p$.

Addition following comment: RSA is sometimes presented in $\Bbb{Z}_n^*$ because:

The early version of Rivest, Shamir, and Adleman's paper did.
As pointed there, that's not a serious practical limitation because so few messages are excluded.
That removes any hypothesis on $n$ and thus makes the proof simpler; by contrast, we need a square-free $n$ in order for RSA to work in $\Bbb{Z}_n$.


Java - What are the additional 8 bytes of output generated by AES/CCM/NoPadding?

The additional 8 bytes are the Message authentication code (MAC), which is called the Message integrity check (MIC) in Bluetooth terminology.

For more info, see here.


What is the public key length of RSA and Ed25519?

Note that this isn't really a cryptography question; it's about how various kinds of data representations work. The data in this case happens to be cryptographic, but the same or similar methods, operations, and issues can occur with any kind of data.

In this link, it says ed25519 has a length of 64 characters
Is this base64 encoded characters?
And does ed25519 limit to only 64 characters?

That webpage is about keys used in SSH, and more specifically in OpenSSH which is the only SSH implementation most people know about even though there are (many) others.
A0. That link says ed25519 publickey is 68 chars, not 64, and is correct; see below.
A1. Yes, OpenSSH stores publickeys in base64, or more exactly as a line containing two or three space-separated fields: a type or algorithm name, a base64 encoded 'blob' which itself can contain multiple subfields, and an optional comment string; with in some cases one more field preceding those (nothing in key.pub files, always a hostname (or hash thereof) in the known_hosts file, optionally a set of special options in the authorized_keys file).
For ed25519 the 'blob' data in binary is (always) 51 bytes: a 4-byte length, a 15-byte string containing (again) the algorithm name, another 4-byte length, and a 32-byte value which is the actual publickey value. 51 bytes is base64-encoded to 68 chars (exactly).
A2: yes, ed25519 keys are fixed length 32 bytes (as kelalak commented), and the added metadata in the 'blob' is also fixed length, so the base64-encoded blob is fixed length. This isn't true of other algorithms used by OpenSSH.
An RSA-3072 key (with e=F4, see below) in OpenSSH format has a blob of 23+384=407 bytes encoded as 544 chars.

I tried to generate a public private key pair here but: ...

That webpage produces (and uses) keys in the formats used by many but not all other programs, including Java, (plus base64 encoding) which are different from those used by OpenSSH. In particular for publickey Java uses the ASN.1 structure SubjectPublicKeyInfo defined in X.509 and more conveniently copied in RFC5280 section 4.1. Thus the encoded key contains ASN.1-level metadata (tag and length octets) and 'application' metadata (the AlgorithmIdentifier structure) in addition to the actual publickey values -- which as also commented contains both the modulus n and the public exponent e as required by the standard format, although that site like many but not all systems makes e a constant value 65537 chosen because it is a Fermat prime: prime is good because it eases generation of p,q with p-1,q-1 coprime e as required, and Fermat primes have minimal Hamming weight making encryption or verification operation cheaper.
515 there is a typo; it actually does 512 bits. Although mathematically RSA works for any number of bits, a nearly universal convention quickly developed of using only powers of 2 or values halfway between such powers: 512, 768, 1024, 1536, 2048, 3072, 4096. (There are some exceptions; for example some smartcard interfaces use message formats with a single-byte length field allowing up to 1016 bits if signed or 2040 bits if unsigned, making that the maximum size RSA they can readily support.)
The 'standard' RSA sizes with e=65537 represented as SubjectPublicKeyInfo in DER and base64 are:

modulus bits
DER bytes
base64 chars

512
30+64=94
128

768
30+96=126
168

1024
34+128=162
216

1536
34+192=226
304

2048
38+256=294
392

3072
38+384=422
564

4096
38+512=546
736

I would like to ask why?

The 'real' info in a RSA-3072 publickey is the modulus n, which is 384 bytes in both representations, but the added metadata varies in format and size, resulting in base64 encodings of different lengths.


Theoretical security of bit rotation for encyption

Let's say the plaintext is English text (or some language that uses the basic latin characters), encoded in Unicode.  That means each byte represents one character, and because of the quirks of Unicode, the basic latin characters and typical punctuation marks all have a zero for the most significant bit.

To attack your scheme, an attacker would look for runs of bytes which all had zeros in the same bit-position.  A run of $x$ bytes all with a zero in the $y$ bit-position would suggest both a length for $n$ (something less than or equal to $x$) and also a rotation amount (the amount required to move the most significant zero bit to position $y$).

Even if the plaintext is not English text, or doesn't use Unicode, in your scheme the ciphertext still trivially leaks the parity of each byte of the plaintext (i.e. how many 1's and 0's are each byte), which is an atrocious amount of information to leak.  For a cipher to be secure, the ciphertext shouldn't leak any information whatsoever about the plaintext, except for its length.


Why is the internal chacha20 permutation vulnerable to attacks if used in a sponge construction?

I would have phrased it as not having evidence supporting it as safe to use.

The ChaCha permutation was not designed to be used in a sponge construction. It could be safe, but we don't have evidence of any weight similar to the weight of evidence we have suggesting that the whole ChaCha20 stream cipher is safe.

I'm not aware of any attack on the ChaCha permutation if used as a sponge, unless capacity bits are initialized to zero. ChaCha's trivial fixed point is from zero to zero. If you can force the sponge's state to that value, then you can insert one or more blocks of all zero bits between two message blocks without changing the sponge's state. (Making collision attacks trivial.)

It is (most likely) non-trivial to get the state (capacity) bits to the zero if they aren't already that value. If the capacity bits are non-zero and the number of capacity bits is sufficiently large and the ChaCha permutation would be indifferentiable from a random permutation if not for the one known fixed point, then there might not be a way to exploit the fixed point in practice.

But, again, that third point isn't something that we can assume is true with the same confidence that we have for assuming that the stream cipher algorithm, ChaCha20, is secure. There is a lack of evidence because not enough effort has been put into studying the permutation in isolation.


How to assess the strength of the avalanche effect for AES?

Does it matter WHICH bit I'm flipping? Is it legit to always flip the MSB f.e. or should it be a random position?

If you see the cipher design as a black box then certainly yes. It could well be that the design would be more secure for certain positions than the other. This would indicate a (local) weakness.

Note that the Hamming distance is just one method of testing (pseudo) randomness.

  The presence of the Avalanche effect implies for an attacker to have a 50/50 chance to predict the input (I) state of one bit for each round. So the benefit of applying several rounds (in my case b/k=128 bit -> 10 rounds) is to reduce the probability for an attacker to predict a bit's original (plain) state to 0,5^10?

No. Each bit has two states. This means that one state is correct and one state is incorrect. If you can "predict" the state with a chance of 0.5 then you're perfectly secure.

Guessing a bit right with a chance lower than 0.5 actually doesn't make sense at all. It means you guess wrong with a high probability. In that case you just have to invert the bit to get a higher result (of $1 - P$ where $P$ is the probability).

The additional rounds are needed to protect against other attacks than simply performing black box testing. AES has been "broken" up to 7, 8 or 9 rounds for 128, 192 and 256 bits respectively.


SHA-256 is a relatively poor way to store passwords but it is considered to be pretty much impossible to "crack". That is, retrieve the original plaintext from the hash.

The reason it is poor to use for passwords, especially without a salt, is due to the fact that it is inexpensive to compute, thus more vulnerable to brute force and rainbow tables etc.

You won't be able to crack the hash you have been provided with.

If your question is about how to securely hash passwords, consider something like PBKDF2 if you still want to use SHA256 underneath.


Bleichenbacher attack, binary search, formula for $s_i$

Okay, I examined this for a while, and I'm pretty sure this is more of an oversight. They probably wanted to take $r\ge2bs_{i-1}-2B=2(bs_{i-1}-B)$. The same correction should go into the code. (Taking $r=2bs_{i-1}-2B$ is indeed too low a value and does not ensure the doubling of $s_i$ at every successive step, so your observation is correct.)


How do you use the Tiger hash function with GPG?

The Tiger hash function is not part of the OpenPGP standard which GnuPG implements. A previous version of that standard (RFC 2440) had reserved an identifier for Tiger, but without actually standardizing it (no OID formally assigned). This was removed during elaboration of the next (current) version of OpenPGP, circa 2003, with apparent consensus, on the basis that having too many options may be detrimental to deployment and interoperability.

Older versions of GnuPG did implement the Tiger hash function, outside of the standard (by definition) but this was removed as well; apparently, the most recent version of GnuPG which still supported Tiger was version 1.2.6 (from 2004). So, to answer your question: right now, and for the foreseeable future, you do not user Tiger with GnuPG.


I finally found the problem: there is an error in the course about the OCB mode presented in Coursera Cryptography 1 (by Pr. Dan Boneh). When I consulted the official specification of the OCB mode (RFC 7253), I found that the value used for the tag construction is the number of blocks m and not 0 as presented in the course (see the figure below), otherwise the scheme becomes insecure (an integrity attack can easily be mounted against the semantic security game!).


Why do people criticize and mistrust the e-voting based block chain?

There's a good reason many democracies reserve mail voting to rare cases where that's the only option: it allows one's vote to be influenced by duress or bribery, because one can prove how one voted. No remote voting technology that I know has solved that issue. Ergo, physically going to a polling station with isoloirs should remain the normal voting procedure for political elections in a democracy. And this comment is right to point that some¹ usages of blockchain in electronic voting can ease vote selling.

A large fraction of voters do not understand cryptography or math, some are not even able to follow a logical argument. Even if a complex system was impossible to fraud, they would not be convinced that it is. Therefore simple systems that people understand are the best ones from the standpoint of having the people trust the outcome, which is critical to why we vote: decide who leads without a civil war.

Many electronic voting systems in use (including, in physical polling stations) fail to give a convincing argument to a rational and knowledgeable person that a vote gets counted as cast. People who know something about e-security are the hardest ones to convince because they see how an insider can rig the machine/system. I can't criticize the "e-voting system based on hyperledger fabric blockchain" of the question from that standpoint since it is not described, but ask yourself: how could an insider rig the result? And would it be that easy to make a fraud that can't be detected in a traditional voting system, where voters put a paper bulletin in an envelope at a polling station, publicly insert the envelope in a transparent box, these get locally and publicly opened and bulletins counted at the end of the day, and results of each polling station nationwide are made public, so that anyone can check this public record for accuracy when it comes to the polling station where s/he was a witness, and redo the addition towards the national outcome?

¹ Blockchain-based solutions that aim at securing the collection of results of different voting places, or prevent double voting by an individual, do not necessarily facilitate vote selling.


Given C is a code of length n. Containing M code-words with a distance d

The distance of the code word is the minimum number of bit flips that transforms one codeword into another. It's just the minimum of all possible hamming distances between the codes.

Also you can define the weight of a codeword to be the distance from the zero vector.

For your code it looks like $d = 2$.


Extending the size of input for SHA-2 function

$2^{64-1}$ bits that make 2.30584301 exabytes *. If you are not restricted to SHA256, then use SHA512 that allows files to have size at most $2^{128}-1$, or use SHA3 that has no limit.
The NIST must use a limit due to the artifact of the MD construction. SHA256 is standardized in 2001 along with SHA512. They have internal block size 512 and 1024 respectively, in order to reduce the change of internal collisions, double the output size double the internal size double the file limit!
If you want to extend the limit of SHA256, then you are out of standards. SHA512 is already beyond all.

Would it still be considered safe to have a SHA2 function that chunks the input data into (2^64 - 1) - hash size bits and use the hash of the previous chunk as a salt for the next chunk?

Yes, you can extend with this $h_1 = \operatorname{SHA256}(m_1))$ and $h_2 = \operatorname{SHA256}(h_1||m_2)...$
But safe is a vague term, safe against what? Hash calculation is free, SHA256 has a length extension attack that you may need protection. In theory, I'll not talk about the numbers, you will get more chance of internal collisions, that can theoretically reduce the second pre-image resistance, or read here
Another alternative is the Merkle Tree.

Are there other options to extend the size of the input of those hash functions to arbitrary length?

Use SHA3-256, or better use SHAKE128-256 or and SHAKE128-512

*What is Exabyte: An exabyte is $1000^6$ bytes.
This is a bit unrealistic to hash since;

OpenSSL hash time is approx 450 Mb per second for SHA256. Hashing 1 Exabyte will take 70466 years on my setup.

NSA's Utah data center is supposed to have 12 exabytes

Online storage and service companies like Google, Amazon, Microsoft, and Facebook are estimated to have at least 1,200 petabytes of storage, 1.2 Exabytes.


Are picture files "random enough" to be usable as a one-time pad?

No.  This is not safe.  The one-time pad requires that the pad be generated by a true-random process, where each bit of the pad is chosen uniformly at random (0 or 1 with equal probability), independent of all other bits.

Any deviation from that, and what you haven't is no longer the one-time pad cryptosystem -- it is some kludgy thing.  In particular, once you deviate from that requirement even a little bit (and you're talking about a huge deviation), you are skating on thin ice and there will probably be security problems with your scheme.

If you're gonna use the one-time pad, you gotta use it exactly as it is defined, with a truly-random pad.  There are no shortcuts, no halfway stuff.  Messing around with this sort of thing is exactly what enabled the US to cryptanalyze Soviet use of a "one-time pad" in the VENONA project.

But in practice, you probably don't want to use the one-time pad anyway.  The key management issues are enough that it is rarely a good choice in practice.


Does the XML signature standard support Ed25519?

As of 2018-03-12, no.

(Whatever is the latest version may change.)

The XML signature standard looks like a committee of bureaucrats got in a room with a 1990s-era textbook on cryptography and invented a way to shoehorn it into XML syntax by stuffing it into a blender with the X.509 standard and a collection of O'Reilly XML books.  This is not a standard for using—this is a fine standard for laying down and avoiding.


Is it possible to correct the exponent of an RSA public key if it has been altered?

Yes, it is possible to change the public encryption exponent of an RSA key.

Indeed, this requires no special computation.  An RSA public key consists of two numbers: the modulus $n$, which is a product of two large (secret) primes $p$ and $q$, and the encryption exponent $e$, which is usually a small fixed prime (most often, 3 or 65,537 = 216+1).  If you want, you can simply pick (almost) any other exponent instead of $e$ and encrypt with it.

(You'll have to somehow let the owner of the key know which exponent you used to encrypt the message, but that's easy enough to solve: since the encryption exponent is public information, you can simply send it alongside the message.)

Of course, in order to decrypt the message, the recipient needs to know the corresponding decryption exponent $d$.  If they kept the original primes $p$ and $q$ used to calculate the modulus (which most RSA private key formats do store, if only because knowing them allows the use of more efficient decryption algorithms), then they can easily calculate the correct decryption exponent $d^*$ for any valid encryption exponent $e^*$ simply by taking the modular inverse of $e^*$ modulo $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$, just like they calculated the original decryption exponent when they generated the RSA key pair.  Indeed, even if the recipient only knows the modulus $n$ and the original public and private exponents $e$ and $d$, they can use the fact that $ed \equiv 1 \pmod{\lambda(n)}$ to factor the modulus and then proceed as above.

All that said, not quite every encryption exponent is valid.  Obviously, the choice $e = 1$ would be totally insecure, since the encrypted message would just be identical to the decrypted one.  Slightly less obviously, in order for the modular inverse to exist (and thus for the message to be uniquely decryptable), the encryption exponent must be coprime to both $p-1$ and $q-1$.  This could be a problem if someone other than the owner of the private key wanted to change the exponent, since both $p$ and $q$ have to be kept secret for the RSA key to be secure.  A fairly safe choice, in this situation, would be to pick $e$ to be a random large prime less than the modulus; the odds of such a prime being a factor of either $p-1$ or $q-1$ is vanishingly small.  Indeed, even smaller primes could be fairly safely chosen, provided that they're not too small; using $e = 2$ would obviously be a bad idea (since $p-1$ and $q-1$ are always even), but anything over, say, 1,000 should be reasonably safe.

In particular, if you happened to know that $p$ and $q$ were both safe primes (so that $(p-1)/2$ and $(q-1)/2$ are both also prime), and differed by no more than a factor of, say, four (as they should, if the RSA key is generated in the usual way), then any prime strictly greater than 2 and less than $\sqrt{n}/4$ should be safe to use as the public exponent.


Abstract algebra basically comprises Groups, Rings, Fields, Vector Spaces, Modules, and many other algebraic structures. It is not only useful in Cryptography but in Channel Coding, in the branch of Chemistry and Physics too.
It is a tool like Groups where you can do arithmetic and algebraic operation under a closed set. One can compare two algebraic structures and find similarities between them and use these properties further.

Now your question about AES and Galois Field. if you do arithmetic operation on the matrix of AES, say multiplying two bytes $\texttt{0xEF}$ and $\texttt{0xDC}$, without finite field your many arithmetic operations go beyond 1 byte of length. Finite field make sure that it will remain within the closed set by reducing to modulo.

for example; if you take the finite field created by the prime number 11 ($\mathbf{Z}^*_{11}$) the set only contains $\{1,2,\ldots,10\}$ elements. All operations are done within this set.  Then only you can substitute bytes find inverses when you decrypt AES encrypted ciphertext.
if you don't use them, strictly speaking without irreducible polynomial (like in AES it is $x^8+x^4+x^3+x+1$) or prime number, where it makes sure that all length of all operations ends up in byte and hence easy to find their unique inverses while decryption.


It is called circular security. It is problematic because it is not captured by the usual security definitions. I.e., even if an encryption scheme is proven secure by some regular definition, it is usually not a given to be circular secure.

To see why consider, for example, the usual definition of semantic security for a public-key encryption scheme $\Pi = (Gen, Enc, Dec)$: We say that $\Pi$ is semantically secure if all adversaries $A$ has at most negligible advantage (in security parameter $\lambda$) in the following security game:

We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$ (here $pk$ is the public key and $sk$ the secret decryption key).
$A$ outputs messages $m_0$ and $m_1$.
We sample $b \leftarrow \{0,1\}$ (a random bit), and send $c \leftarrow Enc(pk,m_b)$ to $A$.
$A$ outputs a bit $b'$ and wins if $b = b'$.

The problem here is that this only talks about security for some messages $m_0$ and $m_1$ that $A$ can pick. However, since $A$ does not know $sk$ there is negligible probability that she will pick $sk$ as a message (in fact if $A$ could pick $sk$ with non negligible probability the scheme would not be secure!). So using this definition we cannot say much about the circular security of the scheme.


VeraCrypt hashes can be broken by Police with the appropriate cash input. Hashcat can break VeraCrypt hashes.

Breaking a hash algorithm and brute-forcing a hash input are 2 completely different attacks. Veracrypt uses PBKDF2 with half a million iterations for volume containers, which is an appropriate amount. The weak point which allows recovery of a Veracrypt volume is the strength of the password

  How to protect against it?

Use better passwords and keyfiles, and use a bigger iteration count (PIM)

  Will longer mouse movements help?

No, that has little to do with the password hash strength

  And hashes are really so dangerous?

No, poor choices of passwords and bad opsec are dangerous, it is easier to install hidden cameras and observe keyboard input, or to use torture


Good link: Crypto++ for pentium 4

                            Milliseconds/Operation     Megacycles/Operation
    RSA 1024 Encryptio       0.09                         0.27
    RSA 1024 Decryption      2.28                         6.68

CPU frequency of the test platform is 2.93e+009 Hz.
I think the performance depends on the language, library and CPU architecture.


Formal verification of elliptic curves. Depence on the equation form

For instance, say I do the verification for Weiertrass form and then I "convert" the results to Edwards form. Would this be still side-channel attacks resistant?

Well, if you have a Weierstrass form and an Edwards form of the same curve, they're actually the same group, with an easily computable isomorphism between the two, and so any group property (including things such as the difficulty of the discrete log problem) would be preserved.

However, you specifically asked about side channel resistance; that's not a group property.  Instead, it is a property of the implementation (as a side channel attack listens into internals of the implementation as it computes).  If you have two different implementations of the same curve (for example, a Weierstrass implementation and an Edwards form implementation), then proving that one of your implementations is resistant to a specific side channel attack says nothing about whether your other implementation is.


Is there a standard for public key encrypting and signing short messages?

Would there be a minimum ciphertext size that is related to the public key size?

It depends on the algorithms used. An RSA signature, without any bells and whistles, is equal to the key length in size (i.e. 2048 bits for 2048-bit RSA). Likewise raw RSA encryption adds the same. So if you just use both, you add twice the key length, or 512 bytes for a 2048-bit key size.

Elliptic curves allow much more compact signatures and encryption. An 256-bit ECDSA signature is usually 512 bits. With NaCL, using Curve25519 and hybrid encryption, you can get authenticated encryption using only 40 bytes of extra space. That's what I would likely use with small messages.

If even elliptic curve algorithms add too much, you could use symmetric algorithms, with an occasional session key exchanged using the public key system. If many messages are exchanged using, say, AES GCM your per message overhead is about nonce size + authentication tag size (e.g. 192 bits total). Even less if you can use some existing counter as the nonce.


With some assumptions I think you can do this with a simple protocol.

We will break i into two parts: attempt an allocation which may succeed with reasonable liklyhood. And verify it. If verification fails try again.

The first step we can do by each party randomly selecting for himself if he is the chosen one with probability 1/n.

Verification we do with secure multiparty summation. Sum the bits of all parties and if it is 1 verification succeeds. and any other value it fails.
First we need to establish 2 way secure channels(e.g using DH key exchange). A simple summation would be for one party to pick a random R add it to his bit and pass along, where each party adds it's bit and passses along until finally the first party removes R and reveals. This can be broken by a collosion of 2. Alternativly, each party secret shares it's bit by distributing to all parties a random share which sum up to their bit. Then sum up all shares from all parties to reveal total sum.

This however allows a member to force himself to be selected or not.

To deal with this problem we can have everyone commit to a random value $X_i$ and then together they pick a random $R$. Each player will use their secret combined with the shared random ${X_i} + R$ as a random seed. This allows at the end of the game to verify everyone picked random numbers fairly.
Picking a shared random $R$ can be done by each party picking a random $R_i$ and publishing a commitment to it and then all parties reveal. take the sum or the xor of all as $R$.

Success probability of the first phase is $(1-1/n)^{n-1}$ which approaches 1/e . So we are likely to success after only a handful of iterations.


The maths is fairly straightforward.

Replace $m^e$ with $a + bn$, where $a = m^e \bmod n$, and $b$ is an integer (equal to $\lfloor m^e / n \rfloor$).

The binomial expansion of $(m^e)^d$ can then be substituted with the expansion of $(a + bn)^d$ as follows:

$$(a + bn)^d = a^d + c_1a^{d-1}.bn + c_2a^{d-2}.b^2n^2 + \cdots + b^dn^d$$

where $c_1$, $c_2$ etc. are binomial coefficients.

Apart from the first term $a^d$, every term in this expansion is a multiple of $n$ and is therefore equal to zero (mod $n$).

Hence, $(m^e)^d \bmod n \equiv a^d \bmod n \equiv (m^e \bmod n)^d \bmod n$


How much less secure is an algorithm that gives feedback that the password is one character off?

Let's assume that there are $95$ possible characters for a password. Thus, there are $95^n$ possible $n$ character passwords. You would like for brute force to take on the order of that many guesses to get right, $O(95^n)$.

In your case, given the additional information, once you know you have all characters right except one, it takes only an additional $95$ calls to get the exact password. So, attacking this would take $95^{n-1}+95=O(95^{n-1})$ work.

So, basically it decreases the security by one character.


XOR cipher with three different ciphertexts and repeated key, key length known. How do I find the plaintexts?

You're using bytewise xor, and three plaintexts $x,y,z$ with a small alphabet (A-Z, which I assume means ASCII values 0x41-0x5a). Then knowing $a \oplus x$, at a certain index, we know all possible values of $a$, at that same index, namely $\{0x41 \oplus (a \oplus x),\ldots, 0x5a \oplus (a \oplus x)\}$. But we have 2 more constraints from $a \oplus y$ and $a \oplus z$ at that index. The intersection of these three sets is the set of options for $a$ at that index. This already reduces the options at each index, probably.

Then you have to use probable plaintext, say 'THE' (if you have English text). You can try 'THE' at all positions as part of text $x$, compute $a$ on these corresponding places, and then compute $y$ and $z$ as well. Check whether the results look like (parts of) English words, and try to extend words in those other texts. Also try 'THE' in texts $y$ and $z$ in all positions. You can immediately abort all attempts where $a$ is not in the sets we computed above. Google "reading in depth". With three texts this should give pretty fast results. All of this is easily automated.

Doing statistics only on 21 characters will not get all the way, I think. You do need some idea of the language for the plaintext, etc.


Bolt labs uses Garbled circuits (from emp-toolkit) for channel management between the merchant and the customer. More on their blog post
In general, I don't think Garbled circuits is one of the most efficient MPC protocol out there for most tasks. So you're not likely to find many practical applications.


A PPT simulator is really just a PPT algorithm. So if you know what a PPT algorithm is then you know what a PPT simulator is as well.

The term simulator is used in many contexts in cryptography, but typically they are PPT algorithms that are supposed to produce output according to some distribution simulating the output distributions of one or more parties in some protocol.


Security of cloud computational protocols in UC Framework?

I think it is still possible to use UC in this case.

Recall the setup for the UC framework. We have an ideal world and a real world. There are parties $P_1,\dots,P_n$ in each world and an environment $\mathcal{Z}$ in each. In the real world we have the adversary $\mathcal{A}$ while in the ideal world, we have an ideal functionality $\mathcal{F}$ and a simulator $\mathcal{S}$. In the real world, the parties run some protocol $\pi$ while $\mathcal{F}$ should compute the same functionality as $\pi$ in the ideal world and be secure by definition (basically it is a trusted 3rd party). See the graphic below (taken from Martin Geisler's PhD thesis)

So, in your case, you have 3 parties. $P_1=\text{Alice},P_2=\text{Bob},P_3=\text{Sally}$. I'm not going to mess with specifying the protocol $\pi$. In the ideal world we can have a very simple setup. $P_1$ and $P_2$ submit their inputs (in plaintext over a private channel) to $\mathcal{F}$ and $P_3$ issues commands to $\mathcal{F}$ with what to do with those inputs (e.g., "compute the sum", etc).

In the real world $\mathcal{A}$ is basically $P_3$, so we assume that anything $P_3$ knows, $\mathcal{A}$ also knows. That information is then leaked to $\mathcal{Z}$. Then in the ideal world, you'll have to construct $\mathcal{S}$ in such a way that $\mathcal{Z}$ cannot distinguish between the two worlds. How exactly you do this will depend greatly on $\pi$.

As an example, let's say we are just computing the sum of the inputs using Paillier. In $\pi$, $P_1$ and $P_2$ might encrypt their inputs with the Paillier public key (who knows the private key is up to you, but it shouldn't be $P_3$) and send them to $P_3$. Then, if $P_3$ decides to, it will homomorphically sum the values and send the resulting ciphertext back to $P_1$ and $P_2$. To make it general, we'll just let $\mathcal{Z}$ provide $P_1$ and $P_2$ with their inputs and with $P_3$'s choice.

In the ideal world, $P_1$ and $P_2$ pass their inputs (from $\mathcal{Z}$) to $\mathcal{F}$. Then, if $P_3$ tells $\mathcal{F}$ to compute the sum, $\mathcal{F}$ does so. Furthermore, it will leak an encryption (using the paillier public key) of the result to $\mathcal{S}$ who passes that to $\mathcal{Z}$. You can also have $\mathcal{S}$ leak encryptions of the inputs to $\mathcal{Z}$ in a similar manner.

In both worlds, $\mathcal{Z}$ sees encrypted inputs and an encrypted output (if $P_3$ decides to allow the computation). Thus the two worlds are indistinguishable (assuming IND-CPA of the cipher) and the real world is as secure as the ideal world.


Does OpenTSA support PKCS11 to talk to HSMs?

I think that you're asking how to generate a timestamp response as defined in timestamp-protocol: RFC3161, with openssl to generate and sign the response using a PKCS#11 (HSM in your case) as a TSA signer.
I think that there is no native way to use PKCS#11with openssl to do this. (maybe with some plugin like: opensc pkcs11 engine for openssl).
If you take a look on ts command documentation: https://www.openssl.org/docs/apps/ts.html. To generate a timestamp response you can use the follow command:
openssl ts -reply [-config configfile] [-section tsa_section] [-queryfile request.tsq] [-passin password_src] [-signer tsa_cert.pem] [-inkey private.pem] [-chain certs_file.pem] [-policy object_id] [-in response.tsr] [-token_in] [-out response.tsr] [-token_out] [-text] [-engine id]
The TSA signer certificate and private key are specified in the following parameters which specify that both must be in PEM format, so seems that use of PKCS#11 it's not possible.

-signer tsa_cert.pem
The signer certificate of the TSA in PEM format. The TSA signing certificate must have exactly one extended key usage assigned to it: timeStamping. The extended key usage must also be critical, otherwise the certificate is going to be refused. Overrides the signer_cert variable of the config file. (Optional)
-inkey private.pem
The signer private key of the TSA in PEM format. Overrides the signer_key config file option. (Optional)

However as I comment before, it can be possible maybe using opensc pkcs11 engine for openssl, I can't confirm if it works because I'm unfamiliar with it. Take a look on this quickstart guide which may put you on the right direction.
Hope this helps,


Zero-knowledge voting with hidden weights

One approach might be the usage of a homomorphic cryptosystem like the Paillier cryptosystem, while the specific protocol properties depend on your use case.

For more detailed description of Paillier system,
 I refer to https://de.wikipedia.org/wiki/Paillier-Kryptosystem and limit my answer to a possible protocol application to achieve your goal.

Due to the homomorphic properties of the Paillier system, we are able to:

Add different plaintext by multiple their ciphertexts
$Dec_k(Enc_k(m_1,r_1) \cdot Enc_k(m_2, r_2))= m_1+m_2 \mod n$
Multiply an encrypted plaintext by raising the ciphertext to $k$:
$Dec_k(Enc_k(m_1,r_1)^k) = k \cdot m_1 \mod n$

As an example let us assume the following setup:

Common party $C_1$ knows all weights $w_i$ and calculates the result $\lambda=\sum_i v_i w_i$ without knowing the delegates votes
Common party $C_2$ generates the private and public keys for the Paillier encryption.
Each delegate shares an encrypted and authenticated channel with each common party.

In the interests of simplification, I neglect the method, how to achieve this secure channel. You can use a protocol for authenticated key exchange and an and for transport security of your choice to achieve the confidentiality and integrity of the messages.

Now we can define the protocol as follows:

$C_2$ generates one key pair for this election and sends the public key to all delegates.

$ C_2\xrightarrow{k_{pub}}Delegate_i$

$D_i$ Encrypts its vote with the public key and send it to $C_1$. Since $C_1$ does not know the secret key, it gains no knowledge over the delegates vote.

$ D_i\xrightarrow{\overline{v_i}=Enc_{k_{pub}}(v_i)}C_1$

$C_1$ can weight each vote by raise the encrypted vote to the power of $w_i$ and calculate the election result $\lambda$:

3.1 $Enc_{k_{pub}}(w_i \cdot v_i) ={\overline{v_i}}^{w_i}$ (2. homomorphic property mentioned above)

3.2 $\overline{\lambda}=\prod_{i} {\overline{v_i}}^{w_i} = \prod_i Enc_{k_{pub}}(w_i \cdot v_i) = Enc_{k_{pub}}(\sum_i w_i \cdot v_i)$ (1. homomorphic property mentioned above)

$C_1$ send the result to $C_2$

$ C_1\xrightarrow{\overline{\lambda}}C_2$

$C_2$ can decrypt it and publish the election result:

$\lambda = Dec_{k_{priv}}(\overline{\lambda})$

This approach is a common application of shared knowledge: The common party $C_1$ knows the weights and can compute the result without knowing the votes, while all other parties have no knowledge over the weights. There are, of course, many other ways to achieve your goal, e.g. encrypt the weights and raise them by the delegates vote, but I hope, the concept has become clear.


Constructing private matrix for Algebraic Eraser

You copied the equation wrong! I just checked your link.

The matrix $M_0$ is chosen from the set of $n\times n$ invertible matrices over $GF(q)$ (a group under multiplicatin) by some "proprietary" method.

A private key polynomial
$$\sum_{i=0}^{N-1} \alpha_i x^i,$$
over $GF(q)$ is specified and $M_A$ is this polynomial evaluated at the matrix $M_0:$

$$M_A = \sum_{i=0}^{N-1} \alpha_i  M_0^i$$


Why doesn't this operation reveal the voter's message?

I figured it out, it's quite simple actually.

The $d$ values (and $r$ values) are all exponents and chosen from $\mathbb{Z}_q$. Thus all calculations on them directly take place in $\mathbb{Z}_q$. Applying mod $q$ (not mod $p$) to all of my calculations on $d$ and $r$ fixed any problems with calculations.


OAEP security with variable length hash function

Beware that if $n < m$, then $\operatorname{SHAKE256-}\!n(x)$ is a prefix of $\operatorname{SHAKE256-}\!m(x)$, so the two functions are not really independent random oracles as the usual OAEP theorems posit.

If you set $G(x) = \operatorname{SHAKE256}(0 \mathbin\| x)$ and $H(s) = \operatorname{SHAKE256}(1 \mathbin\| s)$, that should be adequate to (conjecturally) satisfy the hypotheses of the theorems without requiring additional analysis to study the possibility of collisions between the inputs to $G$ and $H$.

Alternatively, if the inputs to $G$ and $H$ are guaranteed to have distinct lengths in your application, then $G(x) = \operatorname{SHAKE256}(x)$ and $H(s) = \operatorname{SHAKE256}(s)$ should work too.  But it won't hurt, and might be safer to avoid mistakes, if you always use a unique prefix, whether it be a 0 bit vs. a 1 bit, or the string G oracle vs. H oracle, etc.


Elgamal Encryption: Why does Bob get to reuse his keypair while Alice has to generate a new one for every message?

So why does Bob get to use the same keypair while Alice has to generate a new keypair every time?

Because ElGamal is insecure if Alice picks the same keypair repeatedly.
ElGamal is a public key encryption system; Bob has a long term public key, which he generates once, and hence Bob has to select once private key $b$ and a long term public key $B = G^b$ (note: I don't have the Paar book, hence I don't know what notation he uses).
In contrast, Alice encrypts a message $M$ using Bob's public key $B$; what she does is select a random value $r$ and produce the pair $G^r$ and $M \cdot B^r$.
This is fine; however suppose Alice encrypts a second message $M'$ also to Bob and uses the same random value $r$; this second ciphertext would be $G^r$ and $M' \cdot B^r$.
Why is this bad?  Well, someone seeing both ciphertexts can reconstruct $(M \cdot B^r) (M' \cdot B^r)^{-1} = M \cdot M'^{-1}$. This is more information than we want someone listening in to obtain; in particular, if they happen to know one of the messages (say, $M'$), they can recover the other ($M$).
If Alice selects a fresh random value each time, this does not happen.


PRGs get an input (seed) and generates a larger output value than the input.

Indeed. The standard definition of a PRG makes it a deterministic polynomial-time algorithm with input a seed in $\{0,1\}^n$ and output in $\{0,1\}^{\ell(n)}$ with $\forall n, \ell(n)>n$; and an other characteristic (pseudorandomness).

is it possible that some outputs will never be generated?

It's not only possible, it's certain, for all $n$. To prove this, we only need to count the possible inputs: there are $2^n$; and the number of outputs: there are $2^{\ell(n)}$. The condition $\ell(n)>n\ge 0$ implies $2^{\ell(n)}>2^n$. And since the algorithm is deterministic, there can't be more possible outputs than possible inputs.

Is it guaranteed that all possible random numbers can be produced?

Also yes, but in another sense.
If we truncate the output into $\lfloor\ell(n)/k\rfloor$ bitstring of $k$ bits, then it becomes possible that each one of the $2^k$ potential output bitstrings of $k$ bits is reached for some input when $n$ grows high enough. In fact, pseudorandomness implies that holds¹. Every possible output of any fixed size $k$ bit is reached¹ for large‑enough $n$ and when we consider all the $2^n$ possible inputs.
Now we only need to choose $k$ such that all the random numbers thought are in $[0,2^k)$, and then all possible random numbers thought are¹ produced.

¹ except perhaps for vanishingly few $n$


Showing that security of a elgamal invariant is insecure

You have just to look at the signing/verification relation.

Just write it as $$m\cdot s \equiv r\cdot \alpha + k \bmod (p-1)$$

And the verification relation should be $$g^{s\cdot m}\stackrel{?}{\equiv} y^r\cdot r \bmod p$$
where $y=g^\alpha$ is the public key and you eavesdrop a signature $(r,s)$ for $m$.

Observe that you can take any multiplicative decomposition of the left hand side of the verification relation that yields the value $$m\cdot s \bmod (p-1)$$  to compute a signature for an arbitrary message $m'$ (I let the details to you, this should be easy to figure out). Let $r$ be identical to the eavesdropped signature and just adjust your new $s'$ to the chosen $m'$ and
you will have a valid signature $(r,s')$ for any message $m'$ of your choice.


How do I convert an elliptic key signature r and s value into a signature byte array?

You can choose between two signature formats. One is the most common one and has been defined by the ANS(I) X9.62 standard in ASN.1:

ECDSA-Sig-Value ::= SEQUENCE {
  r  INTEGER,
  s  INTEGER
}

which is then encoded using DER TLV encoding.

For ASN.1 / DER the INTEGER values are encoded as are variable sized, signed two-complement, big endian encoded values. For instance number 255 is encoded as 00 FF (00 is required so it is not interpreted as a negative value) and 256 is encoded as 01 00.

Bouncy Castle has an ASN.1 / DER encoding / decoding facilities build in. Probably easiest is to find out where they encode their own $r$ and $s$ values to generate the usual ECDSA signature.

The other often used method is to simply concatenate the $r$ and $s$ values. In that case the signature is:

$$\operatorname{I2OSP}(r, l) \mathbin\| \operatorname{I2OSP}(s, l)$$

where $l$ is the number of octets required to encode the field size of the group. Or, put differently, $l = \big\lceil \mathrm{keysize} / 8 \big\rceil$. I2OSP has been defined, for instance, in the RSA standards and explained here. The outcome is two statically sized, unsigned, big endian numbers simply concatenated together.

This scheme is often used for smart cards, embedded computers or other schemes that require a minimum size of a signature such block chain.


Derive one public key from ECDH when the other and and the shared secret is known

Is it possible for Carol to find Bobs key in $S_{pks}$

This is a decisional Diffie-Hellman problem.
We can summary this problem as: "we're given the values $G, aG, abG$, and a series of values $c_1G, c_2G, ... c_nG$, can we recognize $c_iG = bG$"
We can reword the problem as "assuming $H = aG$, we're given the values $H, (a^{-1})H, bH$, can we recognize $c'_iH = (a^{-1}b)H$"; with this rewording, this is obviously a DDH problem.
Hence, this problem is possible if the DDH problem is tractable; that is, if we're in a pairing-friendly curve, or if the group order has small factors, or the group order is small enough (or you have a large quantum computer handy).  If none of these are true, then it's believed hard.


How bad it is using the same IV twice with AES/GCM?

Even a single AES-GCM nonce reuse can be catastrophic.

A single nonce reuse leaks the xor of plaintexts, so if one plaintext is known the adversary can completely decrypt the other.  This is the same as for a two-time pad.
In messages up to $\ell$ blocks long, after a single nonce reuse the adversary can narrow the authentication key down to $\ell$ possibilities with polynomial root-finding and thereby forge messages with high success probability $1/\ell$.

How?  An $\ell$-block message is a polynomial of degree $\ell$ with zero constant term; the authenticator under secret key $r, s$ is $m \mapsto m(r) + s$, where $r$ is reused between messages and $s$ is derived as a secret function of the nonce.  Find authenticators $a = m(r) + s$ and $a' = m'(r) + s$ for distinct messages under the same nonce, and only the ${\leq}\ell$ possible roots of the degree-$\ell$ polynomial $m(r) - m'(r) + a' - a$ in $r$ are possible values of the authentication key.

Use 96-bit nonces; if you don't—if, instead, you use smaller or larger nonces—it will be as if you chose nonces randomly, and the number of messages you can safely handle drops dramatically.  But you can, of course, pad, say, a 64-bit nonce into 96 bits: what matters is only that the nonces be unique.

If the cost of a >32-bit nonce is prohibitive, you could periodically rekey.  For example, if you first establish a long-term key $k$, you can use $\operatorname{HMAC-SHA256}_k(i)$ as the key during the $i^{\mathit{th}}$ epoch, where each epoch covers four billion messages, and $i$ is encoded into a bit string in some canonical way.


As you are always decrypting the same flash content with the same key, statistical attacks like DPA do not work, as they try to find dependencies between two random variables (one being an intermediate value predicted using parts of the key and the other one being the measured current consumption(s)), where in your case one of them is constant.

The only uses an attacker can get from several measurements (instead of using just one) is to take the average to reduce the noise or to apply an attack that exploits the noise. Otherwise the attacker basically has to use an attack that works with a single power trace.

If an attacker is able to run the identical software on an identical device where (s)he can choose the key and the cipher text, (s)he can use it to run the profiling phase for a template attack, and hope that both devices have very similar power characteristics.

As template attacks calculate likelihoods depending on the observed noise, you can combine the results of several measurements to improve your chances to recover key and data.

From my experience the success probability for a very skilled attacker (using an optimal template attack implementation combined with key enumeration techniques) are relatively low if the AES is implemented in hardware, but pretty good for a software implementation on a leaky device.


Use AES 128 in GCM mode. This will generate a tag during encryption. Send that tag along with the ciphertext to receiver. If the receiver decrypts it with the wrong AES key, the sent tag and receiver computed tag will differ. Alert your user that the AES key is incorrect OR that the encrypted data is corrupted.


Learning elliptic curve cryptography for specific application

Consider this an oversimplified, though hopefully useful outline of the path to take.

Proficiency in calculations modulo n is a must. That includes results such as Lagrange's theorem, exponentiation, the Extended Euclidean algorithm, and quadratic residues (most likely I am missing some important items here). The essential concepts from group theory are largely embedded in this stage.

Besides its usefulness elsewhere (or I should say everywhere in asymmetric cryptography), a knowledge of the aforementioned items will put you at the right place for understanding the Discrete Logarithm Problem (DLP). The DLP epitomizes the impracticality of searching for, or computing, the discrete logarithm. This is important to understand because the safety of elliptic curves (EC) is premised on that computational impracticality.

A concise, introductory definition of elliptic curves is here. My first exposure to EC was pages 60-64 of Mastering Bitcoin, by Andreas M. Antonopoulos, but there is plenty of alternative resources that cover everything I've mentioned hitherto.

Upon learning about the DLP, textbooks cover El Gamal cryptosystem. Understanding this topic is relevant to EC because of the analogies between the idea behind El Gamal and the digital signing of messages (for instance, as used in Bitcoin).

Hash functions, AES, and key exchange protocols are further topics that oftentimes are combined with --or on top of-- EC but without being part of EC itself.

Note that nowhere have I mentioned RSA, factorization algorithms/heuristics, or the Pohlig-Hellman algorithm, since I am mindful that you are interested only in the requisites for dealing with EC.

To make this answer more self-contained, I will repeat my comment that other concepts you read in the answer to which you linked are similar to any context from telecommunications. For instance, the notion of broadcasting refers to divulging certain information --such as your address or public key-- that will let any counterparty know where to send you a message that only you can read/decrypt (by means of your private key). Boradcasting means no other thing in cryptography.


To get a collision with probability 1, you need to hash $H+1$ distinct values.  You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash output; if any reasonable sized hash function, this is extremely unlikely, but it does have a nonzero probability to happen.  On the other hand, if we hash $H+1$ distinct values, we know (by the pigeon hole principle (because there are only $H$ hash outputs), that two of the inputs must hash to the same output.


SHA-256 private/public coordinates to the PEM format

What you are sharing is indeed (lapo.it ASN.1 decoder) a 1023 bit public RSA key. RSA keys can be used for multiple things such as signature generation. In that case the signature algorithm may use SHA-256 to hash the message, but the key itself doesn't care about the hash function used (you won't see it in the structure in the link).

"private/public keys SHA-256 keys."

SHA-256 is a hash algorithm; it doesn't use any keys and certainly not a key pair.
OpenSSL command line only indicates the hash algorithm, but in that case it just assumes PKCS#1 v1.5 compatible RSA signature generation / verification if you use an RSA private or public key respectively; possibly other API's or command lines do the same.

However it returns me not a public key in a .pem format but, according to the datasheet, it returns me the coordinates X and Y of the public key, which are 64 bytes.

X and Y coordinates are not components of an RSA public key. Together they are usually indicating a point on an elliptic curve though. What you are likely getting is a flat representation of EC public key (usually indicated as variable name $W$). In that case they public key may consist of 2 times 32 bytes (i.e. two statically sized unsigned big integer values).

My first wrong assumption can be the fact that I am assuming that a SHA256 pair is the same thing as RSA-SHA256. I know that there are many variants of SHA256 algorithm, but from what I've read the RSA is the standard variant. So I am assuming that RSA-SHA256 is the same thing as SHA256. Am I right?

So no, there is no such thing as a SHA-256 pair. More likely it is a P-256 (or, alternatively named secp256r1) public key. Here P-256 and secp256r1 indicate the curve's domain parameters by name, i.e. a named curve.

Assuming I have the RSA-SHA-256, how can I convert these coordinates to .pem? On the server side, I was using the .pem public key of the device to verify the signature. Now I am only able to share some coordinates of the public key? It is possible to convert from coordinates to .pem? Or am I just misunderstanding a bunch of different concepts?

That's better asked at StackOverflow indicating the exact runtime & libraries that you plan to use.
The steps are:

put the numbers into the X9.62 structure;
put those into a SubjectPublicKeyInfo ASN.1 structure while indicating elliptic curve cryptography as algorithm and the domain parameters by OID;
DER encode above structure;
perform the PEM encoding to apply the "ASCII armor", i.e. make it text.

Yeah, I know, outside of your experience field, sorry.


As in the first equation one has $(x+k_1)^3 = (x^2+k_1^2)(x+k_1)$, i.e., $(x+k_1)^2 = x^2+k_1^2$ I'd conclude that the equation is over characteristic $2$.

This explains why all the terms with even coefficients are missing and why all odd coefficients are replaced by $1$.

The only remaining mystery is what happened to $3k_1^6k_2$ rsp. $k_1^6k_2$. Typo?


Where can I find NIST SP800-38E's Test vectors?

Test vectors, as well as the requirements for validation testing, are currently available here:

https://csrc.nist.gov/Projects/cryptographic-algorithm-validation-program/CAVP-TESTING-BLOCK-CIPHER-MODES

By the way, this was literally the first result for a google search of "XTS-AES test vectors"


Basic attacks on McEliece; finding S and P

After another good read through the current research papers [1, 2, 3] I'm not so sure anymore that the above stated problem does indeed have a solution, yet. I think it heavily depends on the chosen code $G$ whether it is possible to break the system; and all system breaking algorithms gave $S$ as well (or their equivalent in the Niederreiter cryptosstem).

I now do not think it is possible to retrieve $S$ given $G$ alone.


I did something similar last year with SHA-3 finalists. I can tell you from personal experience that the best course of action is to find the C/C++ reference implementations and port them to CUDA. Start naively by writing a kernel that does the entire operation in one GPU thread. Once you have it working, you can optimize for the hardware.


Distance between consecutive primes distribution

First some empirical results,
over the first 1 million primes the to 0.1% will show up 0.65% of the time
the top 1% will occur 4.7% of time and the top 10% will happen 29% of the time.

Looking at visual from https://en.wikipedia.org/wiki/Prime_gap

It doesn't look like it has a heavy tail and seems to decline super linearly. this suggest a small tail will never be a large portion.

For larger numbers the largest ratio between the prime gap and $ln(p)$ is 41 (This ratio is called merit), this is largest known and not an upper bound, but if we take it as an upper bound, and if we take ln(p) as the average distance and 2 as the minimum distance. The most extreme imbalance would be if all gaps were ever maximal or minimal (obviously not the case just for a bound). We mark the ratio of maximal gaps as r. So we will get $ln(p)=r * ln(p)*41+ 2*(1-r)$
which leads to $r=(ln(p)-2)/(41*ln(p)-2)$ for $p=2^{1024}$ this comes out 2.5%, and these would come up 99% of the time. But obviously we can't have many gaps of size 2. We can improve this somewhat but not much.

So we get a huge discrepancy between what we expect and we can prove. If we want a stronger claim then assuming maximal merit things get worse we can bound the gap to be no more than $p^{0.525}$ and if again assume to have a range where gaps are almost entirely either this maximum or very small, we will be able to get a more extreme ratio. Yet even this scenario won't get enough for e.g efficient factorization. If we have a range from $2^{1023}$ to $2^{1024}$ even with maximal gap there are still a lot of primes there. If we would try to factor with trial division we would get no more than a square root speed up over naive trial division which is not competitive with other methods.


If we should not reuse primes in DH, shouldn't we not reuse ECDH elliptic curve properties?

The fact is that the discrete logarithm problem (DLP) is solved using different algorithms in the cases of multiplicative groups (where normal DH applies) and elliptic curves (where ECDH applies).

The behavior of these algorithms is quite different.

For multiplicative groups, where the NFS for logarithm is used, a huge part of the computation depends only on the multiplicative group itself and not on the single discrete logarithm.

See for example the logjam paper where in table 2 they mention the costs for sieving, linear algebra and descent (where descent is the only phase requiring the single logarithm as input, and therefore can't be precomputed).
For DH-1024 sieving and linear algebra requires 45 million core years while just 30 core days are needed for the descent.
This means that after having done a huge precomputation, single logarithms are quite easy to extract.

For elliptic curve groups the situation is different. The best attack is Pollard's rho, which requires $\mathcal{O}(\sqrt{n})$ group additions for a group of size $n$. Now, computing in parallel $l$ discrete logarithm costs $\mathcal{O}(\sqrt{ln})$, which is speedup over the trivial $\mathcal{O}(l\sqrt{n})$, but not a significant one. In fact, the attacker is expected to compute $\mathcal{O}(\sqrt{n})$ additions before finding the first among them (see the "Batch Disscrete Logarithms" of the curve25519 paper.
Once the first discrete logarithm is found, the second one has still similar cost to the first one, not a much smaller one (like with the NFS).

Thus if $n$ is of reasonable size, it doesn't matter how $l$ is big as computing even the first logarithm will be out of reach.

Note: there are techniques that by using an extremely large precomputation effort allow to easily compute discrete logarithms. The important thing to understand the ineffectiveness of these approaches is that the precomputation effort costs significantly more than extracting a single logarithm (about $\sqrt[3]{n^2}$ additions which is greater than $\sqrt{n}$ for the single logarithm).
See this paper for details.


The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)".

As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us calculate with these things as if they were ordinary numbers, but so that the results of the calculations always stay inside the finite set.

Specifically, we require the operations defined on the elements of this finite set to satisfy the field axioms, which include the usual associativity, commutativity and distributivity rules you probably learned in high school algebra class.  In particular, we also require every element $a$ to have an additive inverse $-a$ and (if $a \ne 0$) a multiplicative inverse $1/a$, such that $a + (-a) = 0$ and $a \times (1/a) = 1$.  Thus, as long as you just stick to algebraic manipulations using these rules, the Galois fields all look exactly like the field of real numbers you're familiar with.

To learn how to do arithmetic (i.e. actual calculations with actual numbers) in Galois fields, it's probably easiest (particularly if you're already familiar with modular arithmetic) to start with the prime Galois fields $GF(p)$.  Arithmetic in these fields is simply ordinary addition and multiplication of integers modulo some prime $p$.  For example, in $GF(3)$, there are three numbers ($0$, $1$ and $2$) with the following addition and multiplication rules (and their commutative variants):

$$\begin{aligned}
0 + 0 &= 0 & 1 + 1 &= 2 & 0 \times 0 &= 0 & 1 \times 1 &= 1 \\
0 + 1 &= 1 & 1 + 2 &= 0 & 0 \times 1 &= 0 & 1 \times 2 &= 2 \\
0 + 2 &= 2 & 2 + 2 &= 1 & 0 \times 2 &= 0 & 2 \times 2 &= 1 \\
\end{aligned}$$

The only unusual rules here are $1 + 2 = 0$, $2 + 2 = 1$ and $2 \times 2 = 1$; those are the cases where, in normal arithmetic, the result would've been equal to or greater than $3$, so it's "wrapped around" by subtracting $3$.  From these rules, we can also determine the inverses.  It turns out that $-0 = 0$, $-1 = 2$ and $-2 = 1$ (since $1 + 2 = 0$) and $1/1 = 1$ and $1/2 = 2$ (since $2 \times 2 = 1$), so they indeed do exist and belong to the field.  (I'll leave verifying that the inverses are all unique, and that these rules indeed also satisfy all the other field axioms, as an exercise.)

Why do we require $p$ to be prime, then?  Well, it turns out that if a number $m$ is not prime, then some numbers won't have multiplicative inverses modulo $m$:  for example, there is no integer $a$ such that $2 \times a = 1 \pmod 4$.  Thus, the integers modulo $m$ don't actually form a field (but only a ring) unless $m$ is prime.

However, if $m$ is a prime power — i.e. a number of the form $m = p^n$, for some prime $p$ and some positive integer $n$ — then we can still save things by changing the rules on how addition and multiplication work.  This is where all that stuff about the vectors and polynomials comes in.  However, what you should keep in mind is that they don't really represent any added complexity, just alternative ways of looking at things.  Fundamentally, we're still dealing with a set of $p^n$ numbers and some arithmetic operations defined on them — it just turns out that, for example, the multiplication rule we'll need to use is pretty easy to describe if we identify each number in the field with a polynomial, at least if you still remember the rules for adding and multiplying (and dividing) polynomials that you may have also learned in high school.

So, let's start with vectors and addition.  Given a number $a \in \{0, \dotsc, p^n-1\}$, we can represent it in a natural way with $n$ base-$p$ digits $a_0, \dotsc, a_{n-1}$, such that $$a = a_0 + a_1 p + a_2 p^2 + \dotsb + a_{n-1} p^{n-1}.$$

This is exactly how you'd represent a binary number modulo $2^n$ as a string of $n$ bits.  We could also call the string a vector, since that's basically what a vector is: a finite-length sequence of numbers.

Now, when you normally add numbers together digit by digit, you need to keep track of carries.  On the other hand, when you add two vectors together, it's simpler: you just add up the corresponding numbers in each vector separately.  Now, it just turns out that the addition rule we'll need to use, to make the field axioms work in a field with $p^n$ elements, is exactly this "carryless addition".  For example, in $GF(4)$ (which we often write as $GF(2^2)$ to emphasize that $4 = 2^2$ is indeed a prime power) the addition rules look like this:

$$\begin{aligned}
0 + 0 &= 0 & 0 + 2 &= 2 & 1 + 1 &= 0 & 1 + 3 &= 2 & 2 + 3 &= 1 \\
0 + 1 &= 1 & 0 + 3 &= 3 & 1 + 2 &= 3 & 2 + 2 &= 0 & 3 + 3 &= 0 \\
\end{aligned}$$

They look a lot more logical if you write them out in binary:

$$\begin{aligned}
00 + 00 &= 00 & 00 + 10 &= 10 & 01 + 01 &= 00 & 01 + 11 &= 10 & 10 + 11 &= 01 \\
00 + 01 &= 01 & 00 + 11 &= 11 & 01 + 10 &= 11 & 10 + 10 &= 00 & 11 + 11 &= 00 \\
\end{aligned}$$

Here you can see that we're just adding up the digits modulo $2$ and ignoring any carries.  You might also recognize this "addition" rule as the same operation as bitwise XOR.  This is not unique to $GF(4)$; the elements of $GF(2^n)$ for any $n$ can be represented as $n$-bit bitstrings, and their addition as bitwise XOR.

So, now we know how to add numbers in $GF(p^n)$.  What about multiplication, then?  Well, this is where the polynomials come in.  You see, one way to describe the multiplication rule is to imagine that the digits $a_0, \dotsc, a_{n-1}$ of the number $a$ are the coefficients of a polynomial $$a[x] = a_0 + a_1 x + a_2 x^2 + \dotsb + a_{n-1} x^{n-1}$$ with the unknown $x$.  (Here, the variable $x$ is purely a formal placeholder; we'll never assign it a value, so you'll never have to worry about "what's $x$?".  It's just there so that we can use the high school algebra rules for manipulating polynomials in $x$.)

Then, to multiply two numbers $a$ and $b$, we just take their respective polynomials $a[x]$ and $b[x]$, multiply them together using the high school algebra rules (doing all the internal arithmetic modulo $p$), and take the coefficients of the result.  This is all pretty simple: remember that polynomial multiplication is also pretty straightforward, being just like normal digit-by-digit multiplication except that, again, there are no carries.

But wait!  Won't the multiplication sometimes give me terms of order $x^n$ or higher?  If I include them in the digit string, wouldn't that result in a number larger than $p^n-1$?

Well, yes.  That's why there's another step: after the multiplication, we need to reduce the result modulo a suitable polynomial (specifically, an irreducible monic polynomial of order $n$).  That is to say, we take the result of the multiplication and divide it by this reducing polynomial (which we can again do with high school polynomial long division), again remembering to do all arithmetic on the coefficients modulo $p$, and keep the remainder (which will be of order $x^{n-1}$ or less).  Of course, in practice it's usually more efficient to do the reduction during the multiplication, so that you don't need to store lengthy intermediate results.

OK, so where does that reducing polynomial come from?  Well, it turns out that we have some latitude in choosing it, since there are usually several polynomials that will work.  Each of them will give a different multiplication rule, although all the fields so constructed (and, more generally, all finite fields with $p^n$ elements) are isomorphic, in the sense that, for any two Galois fields $A$ and $B$ of $p^n$ elements, there's an invertible function $f: A \to B$ mapping one field to the other so that $f(a + b) = f(a) + f(b)$ and $f(a \times_A b) = f(a) \times_B f(b)$, where $\times_A$ and $\times_B$ denote the multiplication operators of the two fields.  Thus, when we only care about the general algebraic properties of the field, and not about the specific representation of the numbers, it's common to speak of "the" Galois field of order $p^n$, even though it might have multiple representations.

If you're asked to calculate something in a specific Galois field, the reducing polynomial will normally be given for you.  For example, if you're writing an AES implementation, it uses $GF(2^8)$ with the reducing polynomial $x^8 + x^4 + x^3 + x + 1$ (where, since $p=2$, all coefficients are either $0$ or $1$).

If you get to choose your own representation, and thus your own reducing polynomial, you should generally try to pick something that makes the calculations easy, subject to the irreducibility constraints stated above.  Often this means picking something with as few non-zero coefficients as possible, and with all those coefficients occurring on low-order terms (except for the $x^n$ term, which must have a coefficient of $1$ for the polynomial to be monic and of order $n$, of course).

I could go into more detail on how to implement multiplication in binary Galois fields $GF(2^n)$, since what I've written above is still on a rather abstract level, and since — especially to someone coming from a programming background — the theory is often more complicated than the actual code (or at least looks that way).  However, to be honest, I'm more familiar with the theoretical side of things myself, and in any case this answer is already more than long enough.  Wikipedia does have a nice article on finite field arithmetic that you could start with, though.

Oh, and what about Galois fields that are not of order $p^n$ for some prime $p$ and positive integer $n$?  Well, it turns out that there aren't any — you just can't satisfy the field axioms if the number of elements has two distinct prime factors.  So, alas, there's no such thing as $GF(6)$ or $GF(10)$.


What's the alternative should PKI collapse?

No, this is not correct.

Your fallacy here is to assume that a public-key infrastructure implies RSA. RSA is just a way of implementing an PKI.

There are other cryptographic schemes out there that do not reduce to the problem of factoring large numbers.


Why weak modes of operations are not banned?

All listed modes are vulnerable to manipulation attacks in one way or another. And all modes require specific prerequisites to be secure. This could be a maximum message size or having an unpredictable IV in the case of CBC.

Only authenticated modes can achieve message integrity / authenticity. Others are all vulnerable because changes to the ciphertext cannot be detected. Originally a lot of effort was spend on error propagation due to unreliable transport. This is what is meant when bit flipping attacks are mentioned. However, in modern times, the encryption is commonly performed in a higher layer where error correction has already been performed. So we're mainly interested in protecting against targeted attacks. Mixing confidentiality and error detection is not a big topic anymore.

As indicated, any of these old modes can be used to achieve confidentiality. For a higher level of security for actual messages you would probably want to use newer recommendations such as GCM and CCM though. However, above modes have not been broken so there is no need to retract them; that would involve rewriting many systems that are compliant.

Although ECB mode can be used for small messages (single block encrypt) or as building block, I guess ECB is the most contentious mode of the bunch. Even as building block, you could argue that directly using the block cipher makes more sense. But please do note that many higher level API's do not directly expose the block cipher to the user; you'd need to use ECB mode instead.


ISO 9797-1 MAC Algorithm 3 and Doc 9303-11

I need to calculate a MAC using ISO 9797-1 Algorithm 3 (padding mode 2)

and the context makes references to 3DES (as confirmed by the 8-byte width of the result without mention of truncation, and the fact that all bytes of the test key 7962D9ECE03D1ACD4C76089DCE131543 have odd parity).

ISO/IEC 9797-1:2011 (revising the 1999 edition) specifies MAC algorithms based on an iterated block cipher with CBC chaining, along the general structure of CBC-MAC. With Algorithm 3, the structure is:

The standard has a Padding Method 2 (not "padding mode 2") where a single 1 bit is appended to the input, then just enough 0 bits (possibly none) to reach a multiple of the block width. Since the input is 32-byte, there are four 8-byte blocks and a last padding block mx of 8000000000000000.

We get F97B82EC7727D582 after the fourth encryption, then 797B82EC7727D582 after XOR of the padding block, then 5F1448EEA8AD90A7as the result.

Caution: there is an attack on this MAC Algorithm 3 recovering the key with the order of $2^{32}$ MAC queries of short messages to find a collision, followed by in the order of $2^{57}$ offline DES operations to recover K1, then K2.


How to interpret the article claiming NIST P-256 curve to be unsafe?

Quoting CodesInChaos:

  P256 is secure, it just lacks some nice-to-have features that make writing a fast and secure implementation easier.


Range query on array of encrypted data using homomorphic encryption

There is order-preserving encryption made by Boldyreva. That is given $a$ and $b$ with $a>b$ then $\operatorname{OPE}(a) > \operatorname{OPE}(b)$ where the OPE is the order preserving encryption.

OPE has already many implementations and OPE used by CryptDB to execute the order based queries to test their capabilities and benchmark on TPC-C queries.

Note that OPE leaks information about the plaintext. An adversary can guess approximately the position of the plaintext of a ciphertext lives in the plaintext space.


Are there any practical attacks that create a printable chosen prefix MD5 collision?

In general, most of the readable MD5 attacks are carried out in formats that make it possible to add non-printing elements, such as postscript. It is hard, yet possible, to create collisions going down to pure ascii or hex. However, they may or most likely will not be readable, and if the hex is doing something meaningful, e.g. assembler code, the code will most likely be faulty.

In general, it is possible when certain bits are changed in certain positions- they have to be identified, by trial and error or looking for flaws, both in the algorithm or the implementation.

Here is a Stack Overflow question on creating collisions: Create your own MD5 collisions


The multiplicative group $Z_m$ of integers modulo $m$ has exactly $\phi(m)$ elements by definition. Thus for any element $a$ of $Z_m$ the equation
$$
a^{\phi(m)}=1~(mod~m)
$$
holds, where $1$ is the multiplicative identity of $Z_m$ (the residue class $km+1$ of all integers congruent to 1 modulo $m$).

In RSA, $e$ and $d$ are indeed inverses modulo $\phi(\phi(n))$ in the exponent arithmetic, since the order of the multiplicative group $Z_n=Z_{pq}$ is $\phi(n)=\phi(pq)=(p-1)(q-1).$

So the last line of the image is correct and you get
$$
e=d^{\phi(\phi(n))-1}=d^{-1}~(mod~\phi(n))
$$
in the exponent multiplicative group which is what you want, since
$$
M^{ed}~(mod~ n)=M
$$
if and only if
$$
ed~(mod~\phi(n))=1,
$$
if and only if
$$
e=d^{-1}~(mod~\phi(n))
$$
by uniqueness of inverses in any group.


Is tagging the hash of a password along with ciphertext secure?

You don't get empty output in AES, too. AES is a permutation and will always return a plaintext, correct or not depending on the key.

If I take the SHA3_512 of the Argon2ID-ed password and include it with the ciphertext, is the ciphertext now vulnerable to attacks?

One needs to find a pre-image to the key, and normally the cost of this is around $2^{512}$ for SHA3-512, however, if you are using xChaCha20 then the cost is around $2^{256}$ since the input is the 256-bit key. In any case, it is secure to be bruteforced.
You can also, encrypt the all-zero message block or any random message block you chose to validate the key.
Note that the Veracrypt uses Decryption is considered successful if the first 4 bytes of the decrypted data contain the ASCII string “VERA”

Is this scheme secure?

First of all, your password's strength is important. You should either use dicewire to have strong passwords or use a password manager to generate one, and those still require a master strong password from you.
The missing part is the integrity of the data, you can use Poly1305 together with the xChaCha20 to have the confidentiality, integrity, and authentication, too.
Another issue can be the update of the encrypted data. If you use the same $(Key, nonce)$ pair for the update, the updated parts of the file are vulnerable to crib-dragging and that part may fail the confidentiality. To mitigate this, you need either use a new $nonce$ and encrypt all of the message or use a new key, too.
A side note; you can use this strong password to derive multiple keys directly
with Argon2id or use HKDF's expand part since the derived key from Argon2id is already is a Pseudo-Random Key.


Definition of trapdoor function from Wikipedia;

A trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor".

The reverse trapdoor function is just the reverse usage of it.
Normally, for encryption, we want the encryption easy but the decryption is hard without the key. Consider the RSA encryption.
In the signature, we want the reverse, hard to produce without the key - i.e. forgery, but easy to verify.  Consider the RSA signature.

Consider RSA, given $(n,e)$ public key then $E(m) = m^e$ is trapdoor (actually trapdoor permutation) without the private key.
Forward usage: With the public key and $m$ it is easy to compute the $E(m)$, encrypt. But given $c = E(m)$ and public key it is difficult to compute $E^{-1}(c)$ without the private key.
Reverse usage: Given $(n,d)$ private key then $S(m) = m^d$ is the reverse trapdoor. Given $s = S(m)$ and public key it is easy to verify but difficult to compute $S^{-1}(c)$ without the private key.

Note 1: usually people confuse RSA decryption with the RSA signature. No, it is not. For proper RSA encryption, you need PKCS#1.5 or OAEP padding schemes and for signature you need RSA-PSS padding scheme. And in practice, it is not advised to use the same key for both.
Note 2: As pointed by Tylo, actually Bleichenbacher's attacks and its variations (DROWN, ROBOT) showed that the RSA PKCS#1.5 padding is not secure.
Note 3: PKCS#1 v1.5 padding has no formal security proof but RSA AOEP has.


How much faster in symmetric cryptography compared to asymmetric cryptography?

The page https://www.cryptopp.com/benchmarks.html has a comparison of the speeds of a number of different algorithms.  You will have to do a little math to covert to the time necessary to encrypt a 2MB file, but this should give you the base information necessary.


Why do MD5 and SHA-3 use different padding schemes?

From the Keccak Team:

  When a padding rule is used with particular properties, one can securely instantiate sponge functions with different rates with the same fixed-length permutation. The simplest padding rule satisfying these properties is called the multi-rate padding: it appends a single 1-bit, then a variable number of zeroes and finally another 1-bit.

So the goal was to make a padding construct that worked with all variations of Keccak, including those that became standardized as SHA-3. The approach keeps those variants prefix-free and as simple and similar as possible to aid cryptanalysis.

The length of the input is included implicitly in the state of Keccak based on the number of calls to the permutation and the padding value. Encoding the input length simply  isn’t needed in Keccak, so it was omitted.


This can be achieved using fair exchange protocols, which seek to ensure that either Alice and Bob both get what they want or neither of them does.


Does pairings based cryptography inherently require a CRS/trusted setup?

No. For example, these pairing-based protocols don't require trusted setup:

BLS signatures;
tripartite Diffie-Hellman, as mentioned in Elias' answer;
some identity-based encryption schemes (when users are their own PKGs, e.g. when using IBE for forward-secure encryption);
the Bünz–Maller–Mishra–Vesely polynomial commitment scheme. (This could in principle be used for NIZK arguments of knowledge, although it has $\Theta(\sqrt{N})$ verification and so is not fully succinct.)


Strength of MD5 in finding duplicate files

MD5 is ok here as usual cryptographic attacks do not apply in this scenario.
The probability of accidental MD5 collision is much less than usual probability for soft error. For details read more.

MD5 is currently considered too weak to work as a cryptographic hash. However, for all traditional (i.e. non-cryptographic) hash uses MD5 is often perfectly fine.

MD5 has one important benefit above SHA1, SHA2, and upcoming SHA3: many platforms allow faster implementation of MD5 than other hashes. The performance in this use case varies highly according to used hash function.

The practical attacks against MD5 are mostly against collision resistance. If these are not an issue, MD5 can be fairly ok. (See earlier question Is a second pre image attack on MD5 feasible?.) For instance, where MD5 is considered fine by many is HMAC-MD5.

To get back to this question. It can be assumed that find duplicate files is not something where collision resistance is such of an issue (you likely do not have $2^{64}$ files), so chances of collision are much smaller than in many cryptographic uses where it is assumed adversary tries to find collisions.

Thus, for usual hash uses, the space of MD5 (128 bits) is large enough. The probability of collision in usual situations is small enough, it is much larger probability to for example, detect false duplicates due to random hardware failure (like soft error).

For more accurate mathematics, see earlier question What is the probability of md5 collision if I pass in 2^32 sets of string?. This is applicable in scenario where user has less than four billion files, and you may use the formula for other values. One million files gives $2^{-89}$, which I would consider very small.

Even more efficient for duplicate file finding than MD5 is to consider all file sizes. Files which are not the same size are not duplicates. Only files that have size which is not unique need hashing. If file duplicate program using hashing wants to be safe from MD5 hash collision, the program may want to perform byte-per-byte comparison to ensure files are unique.


TLS AES_XXX_CCM mode of operation is encrypt-then-mac or mac-then-encrypt?

Given a specific block cipher such as AES, CCM is a specific AEAD scheme: authenticated encryption with associated data, with IND-CCA3 security, loosely meaning it resists eavesdropping and forgery simultaneously.

Encrypt-then-MAC is a generic way to compose an AEAD scheme out of a cipher and a MAC.  It always works, in the sense that if the cipher has the standard IND-CPA security expected of it, loosely meaning it resists eavesdropping, and the MAC has the standard UF-CMA security expected of it, loosely meaning it resists forgery, then the encrypt-then-MAC composition has the standard IND-CCA3 security expected of it.

MAC-then-encrypt is another generic way to compose an AEAD scheme out of a cipher and a MAC.  But it doesn't always work: there exist IND-CPA ciphers and UF-CMA MACs whose MAC-then-encrypt composition is not IND-CCA3.  And it has very sharp edges: some ciphers, such as AES in CBC mode, reject certain messages on decryption due to padding, but the MAC rejects them differently, and the difference reveals information about the plaintexts of messages.  This led to the Lucky 13 attack on TLS.

However, while MAC-then-encrypt doesn't always work, it sometimes works, and in the specific case of AES-CCM, which is a MAC-then-encrypt composition of the cipher AES-CTR and a length-tagged variant of the MAC AES-CBC-MAC, it turns out to have IND-CCA3 security and fewer sharp edges.  (Safety of randomly chosen nonces, and reuse of nonces, are left as a story for another day.)

Traditionally TLS used a generic MAC-then-encrypt composition for a cipher and a MAC negotiated independently between the server and the client.  Eventually the TLS designers realized this was a mistake, and the IETF adopted two remedies for TLS 1.2:

RFC 5246 ‘TLS 1.2’, §6.2.3.3 ‘AEAD Ciphers’: Let the server and client negotiate a specific AEAD scheme, such as AES-GCM or AES-CCM.
RFC 7366 ‘Encrypt-then-MAC for TLS and DTLS’: Let the server and client negotiate cipher and MAC independently as before, and also let them negotiate the use of encrypt-then-MAC composition instead of MAC-then-encrypt composition.

In TLS 1.3, RFC 8446, all cipher suites are AEAD; there is no generic composition at the layer of the TLS protocol, making the protocol substantially simpler.


Generally accepted algorithm for two-pass, misuse-resistant AEAD that is efficient in software

AES-SIV when done well can be very fast. If you have AES-NI then it is possible to get under a cycle per byte. It is not the original AES-SIV construction but rather this one based on GCM (I agree that the original AES-SIV is way too slow). I suggest also that you look at the Caesar candidates. In general, there is no "standard" yet here.


Multiplication by 2 in the Rijndael Galois field

I suspect you got the shift wrong.

Anything shifted left by 1 has an lsbit of 0; if you xor in 010101 (which you do in this case, as the initial value had a 1 msbit), well, 010101 has a 1 lsbit, and the xor of the two must have a 1 lsbit; your result had a 0 lsbit.

Perhaps you're doing a left circular shift (moving bit 7 to bit 0), rather than a left shift (which places a 0 into bit 0)


Other than an exponent greater than 1, what are the considerations when creating a random 256-bit private key using Diffie Hellman?

Are there any other issues, besides the randomness of the 256-bit private key to consider?

Not really.  The DLog problem really doesn't have any 'weak keys', that is, keys that can be broken with less effort than other keys.

Now, you might say "hey, isn't the key '1' easier to break than others?"  Not really; you might consider '1' easy to break because $g^1$ is easy to recognize - however, for any fixed value $1000000$, the attacker could compute $g^{1000000}$, and check for that exact value - if the attacker sees that value, he knows the private key, and the probability of that happening is exactly the same as him recognizing $g^1$

  For example, should the most significant bit always start with 1 in order to ensure a private key of a certain minimum size

No - if you set the msbit, then the attacker can limit the space he is searching by that bit, and that may reduce his effort by a factor of $\sqrt{2}$

Now, if you look at X25519, they really do set an msbit; however not for cryptographical reasons.  Instead, the X25519 designer was afraid that an overly clever implementer might skip the leading '0's on the exponent, which would introduce a timing variation (and, in any case, the space reduction point I made above doesn't apply to X25519, because the bits that are variable already cover (almost) the entire subgroup, so setting that one bit doesn't really reduce the attacker's search space).

  is the probability of flipping enough leading zeros to make the exponent small enough to be dangerous statistically

The probability that the leading bits are 000...000 is exactly the same as the probability that they are 011...101 (that is, an arbitrary fixed bit pattern).  By selecting the exponents randomly, you maximize the number of private keys that are possible.


Intuitive explanation for key exchange with public/private keys

I like it, but it only shows the use of 1 secret key, there's no concept of public key.

The exchanged "mixed colors" are the public keys in the scheme.

Also, color may not be as intuitive as I like because people tend to think you can unmix (even if we made the hypothesis we can't.) And a real-world experiment would probably get messy.

Sorry, but you will have to make some assumptions when performing analogies. And a real world experiment seems useless; if people don't get above analogy then they won't be able to understand key agreement.

Is there another example that would relay on 2 elements from each sides?

If you are relying on an audience that needs to perform work with their bare hands to understand an idea, then you've already lost, as they won't get analogies either. Some abstract thinking is required.


Security difference between $\mathrm{Keccak}(k\mathbin\|x)$ and $\mathrm{Keccak}(x\mathbin\|k)$

See chapter 5.11.2 of the paper “Cryptographic sponge functions” (the link can be found here):

  Note that one can also define a MAC function by taking as input the message followed
  by the key: $t = \left\lfloor {F(M \mathbin\Vert K)} \right\rfloor _n$.  In this case, an adversary has the advantage that she can try
  to generate inner collisions offline, i.e., without having to query the keyed sponge function. Additionally, she can try to construct a path to a state that occurs in the absorbing of a target
  message, leading to a second message with the same MAC.


If multiple hashing algorithms are chained together, is the compound hash function more collision resistant?

1) Just assume $H_1(x)$ is weak and you can generate two $x_1,x_2$ with the same hash. The other hashes then work on the same input, and hashes are deterministic, so the final output is the same. So on the first glance, it seems at best the collisions resistance is equal to the minimum of the functions. But it could also be worse. On the other hand, it depends on what kind of collisions you can create, because to find a collision for the original input would require finding preimages of the correct size in in the inner hashes.

A much better way would be to concatenate the previous hash with the message, and then hash that with the next one. That might give you the security properties of the strongest algorithm in the chain - but robust combiners also require careful consideration.

2) That depends if you consider all hashes secure. As stated above, that depends at worst on the security of the weakest hash: That is really bad, if you use a decent one and a broken one like SHA-1, then better just use the good one alone. Adding complexity can reduce security.

On a general note: Creating a crypto currency does not require knowledge of cryptography. Re-inventing the Caesar  cipher (or modification in a tiny aspect) would also not make that secure in a modern sense.

That article does not even mention the correct security properties of hash functions (collision resistance, 1st and 2nd preimages resistance), the content doesn't have a single well-founded argument. So the seriousness is questionable.


Does this mean they are a 512-bit RSA key?

No, this means they're using a 511-bit RSA key. A 511-bit key is for all security-related aspects essentially the same as a 512-bit key, but well, technically it isn't.

  When I generate my own, my public keys exponent is much smaller at
  only 17 bits long.

The implementation you used to generate the keys probably picked the standard exponent which is $e=65537=2^{16}+1$, whereas the developers of the key in question probably rolled their own key generation and just generated a random 128-bit exponent, which is valid, albeit quite slow.

  How can I create my own key pair that is this strange size?

What they have likely done is they sampled two primes $p,q$ that satisfy $2^{255}\leq p,q<2^{256}$ and got two primes which are closer to $2^{255}$ than to $2^{256}$ which results in their product only taking up 511 instead of the expected 512 bits. One small scale example for this would be $17$ and $19$ which when multiplied yield $323$, the latter taking only 9 bits to represent and the former two both taking 5 bits each to represent.

What you can now do is to either just break the key-pair they used by factoring their modulus, which would cost about 50-100USD on Amazon's AWS EC2 these days, this may be illegal though. Or you could just instruct your implementation to generate 511 bit keys if you really want to, which should work, otherwise you'll probably have to generate your own primes and just try 256-bit primes until you get a pair that yields a 511-bit product and then do the RSA key generation math, it's no that hard and I think the Java standard library has helper functions for that. Using this way you can also just pick a 128-bit public key. But note that depending on how you implement the prime search the private key may be easily factorable, but then this may not matter to you.


Yes, || means concatenation. If H means HMAC and 'secret' is a secret key then this is secure.

Usually hmac accepts key as first argument and message as second. If this protocols MACs the key using the message instead of MACing the message using the key, I don't know whether that is secure.

If H is a hash instead of a MAC, then this is insecure.


What are best known attacks for finding partial target pre-image?

In the generic setting, a $t$-bit partial preimage attack on an $n$-bit oracle $m \mapsto f(m)$ is the same as a full preimage attack on a $t$-bit oracle $m \mapsto \operatorname{trunc}_t(f(m))$.  If $f$ was uniformly distributed in $n$-bit functions, then $\operatorname{trunc}_t \circ f$ is uniformly distributed in $t$-bit functions, so there's no advantage to be had in knowing that it is a truncation of a larger oracle.

Of course, for particular functions $f$, there may be better partial preimage attacks, like $f(0^t \mathbin\| m) = 0^t \mathbin\| \operatorname{trunc}_{n - t}(H(m))$, $f(b \mathbin\| m) = H(m)$.  But we would need more particular details about $f$ like this to say.


ECDSA non random k - Retrieve private key

I have modified this Ruby script to not require public keys and to allow direct (r,s) input. Funnily enough, I stumbled on this thread (created two hours ago as of writing) on Google searching for the exact same problem. Note that I am using Secp192r1 (due to a CTF challenge), so feel free to modify that to your likings:

require 'ecdsa'

msghash1_hex = '000000000000000000000000000000000000000000000000'
msghash2_hex = '000000000000000000000000000000000000000000000000'

sig1 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x222222222222222222222222222222222222222222222222)
sig2 = ECDSA::Signature.new(0x000000000000000000000000000000000000000000000000, 0x333333333333333333333333333333333333333333333333)

group = ECDSA::Group::Secp192r1

def hex_to_binary(str)
  str.scan(/../).map(&:hex).pack('C*')
end

msghash1 = hex_to_binary(msghash1_hex)
msghash2 = hex_to_binary(msghash2_hex)

r = sig1.r
puts 'sig r: %#x' % r
puts 'sig1 s: %#x' % sig1.s
puts 'sig2 s: %#x' % sig2.s

# Step 1: k = (z1 - z2)/(s1 - s2)
field = ECDSA::PrimeField.new(group.order)
z1 = ECDSA::Format::IntegerOctetString.decode(msghash1)
z2 = ECDSA::Format::IntegerOctetString.decode(msghash2)

k_candidates = [
  field.mod((z1 - z2) * field.inverse(sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(sig1.s + sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s - sig2.s)),
  field.mod((z1 - z2) * field.inverse(-sig1.s + sig2.s)),
]

private_key = nil
k_candidates.each do |k|
  private_key_maybe = field.mod(field.mod(sig1.s * k - z1) * field.inverse(r))
  puts 'Private key maybe: %#x' % private_key_maybe
  next
end

Signature.new(r,s) are the parameters above. msghash_hex is basically the hex version of your HASH(message) without 0x and with quotation marks around it to make it into a string to be processed later.