How does one attack a two-time pad (i.e. one time pad with key reuse)?

Well, the classical answer to "what is the correct thing to do after you have the XOR of the two original messages" is crib-dragging.

That is, you take a guess of a common phrase that may appear in one of the plaintexts (the classical example against ASCII english is the 5 letter " the "), and exclusive-or that against the XOR of the two original messages in various locations.  If one of the plaintexts had the text of the crib (" the " in our example), then the result of the exclusive-or is what the other plaintext had in that position; if neither plaintext had that, it's likely that the result of the exclusive-or is just gibberish.  And, once you have a plausible short section, you can extend it (for example, if you know that one of the plaintexts is " na**", you can go through the dictionary of all words that start with "na", use those as cribs, and see which makes the other plaintext make sense).

In addition, you can often deduce things directly from the bit pattern.  For example, if the messages are in ASCII, then one thing to note that bit 6 of letters is set, but bit 6 of spaces, numbers and (most) punctuation is clear; because spaces are far more common than numbers and punctuation, then that will give you a good guess of where spaces occur in the texts (albeit without telling you which message a specific space appears in).

Now, if you have 11 messages all encrypted with the same pad (an "11-time pad"), things get even easier.  Obviously, you can grab a crib across one message, and check it against the other 10; if it makes all 10 make sense, then it is almost certainly accurate.  Even better, by using the observation that you can distinguish spaces from letters (again, by comparing bit 6), you can find where all the spaces appear in the messages; these all act like 1 character cribs, probably revealing virtually all the text of all the messages.


Choice of delta-neighbors in Balloon Hash algorithm

If you use the Mersenne twister or any other non-cryptographic PRNG, then it is conceivable that an adversary could exploit some pattern in the Mersenne twister's outputs to find a shortcut to reversing the resulting hash.  Cryptographic PRNGs are designed so that despite decades of efforts, cryptanalysts have been unable to find any patterns in their outputs that are even detectable, let alone exploitable in context.

Don't use the Mersenne twister!  It's also bad as a non-cryptographic PRNG because it is expensive to initialize and requires a multi-kilobyte state, so it discourages parallelism and reproducible subtrees of computations.


Can I use a key twice if the message is longer than the key in one-time pad?

Re-using the key of a one time pad in a cycle makes your cipher a Vigenère cipher - it is no longer a one time pad.

This scheme is weak for lots of reasons. The easiest example is with known plaintext.   Let's pretend your scheme is used to encrypt packet data.  Chances are, the first 20 bytes are known or easy to guess packet header bytes so we have:

$
\text{KnownBytes} \oplus k_{1-20} \mathbin\Vert \text{Something} \oplus k_{21-512} \mathbin\Vert \text{Bytes1} \oplus k_{1-20} \mathbin\Vert \text{Bytes2} \oplus k_{21-88}
$

where $k$ is the key

Given this, we can recover the value $\text{Bytes1}$ simply by $\text{KnownBytes} \oplus k_{1-20} \oplus \text{Bytes1} \oplus k_{1-20} = \text{KnownBytes} \oplus \text{Bytes1}$.  Since you know $\text{KnownBytes}$ you can then compute $\text{Bytes1}$.

It gets worse. You've also reused key bytes 21 through 88.  Just because the attacker doesn't know the value of $\text{Bytes2}$ or the first few bytes of $\text{Something}$ doesn't make it secure.  The two ciphertexts can be xored to remove the key and yield the xor of the underlying plaintext.


It's mathematically not possible for a hash function to guarantee an exact probability of zero collision if it shrinks space, just by virtue of the pigeon hole principle.
This means that if, for example, targeted input is on average ~20 bytes, and content can be anything within these 20 bytes, but then you want to map that "space of all possibles" into a fixed-size space of 16-byte, thanks to a 128-bit hash function, it "shrink" the space, and therefore it is mathematically necessary for many entries to share the same hash value.
That being said, it's possible to make the probability of such collision to occur so small that it does not make sense to worry about it. For example, using a 128-bit hash, the probability of collisions between millions of elements is so ridiculously small that one would have more chances to get biten by a shark and striken by a comet and win the lottery ticket all together at the exact same time. If you start to worry about that, then you have to worry about a hidden bit-flip happening inside the cpu due to a rare X-ray interaction from solar flare, which is much more probable. And of course, there are myriads of other problems, starting with software bugs, which are way way more probable than that. So focusing on the infinitesimal risk while being blind to much more common sources of issues is an incorrect stance.
Side note : not sure if it matters in your case, but note that in the case of expanding space, or even identical space, it's possible to guarantee no collision with some hash functions. For example, XXH64 and XXH3_64bits guarantee no collision for 8-bytes->8-bytes hashes. Similarly, XXH3_128bits guarantees no collision for 16->16 hashes. It's even easier when expanding space, for example for mapping 6-bytes input into 64-bit hashes results in no collision.
Not all hash functions guarantee this outcome though. Select the ones advertising bijective transformations.


Why is it better to have the private key as the multiplicative inverse mod phi(n) in RSA?

In the standarized RSA algorithm the private key $d$ is calculated computing the modular multiplicative inverse with the Extended Euclidean GCD that satisfies:

$1\equiv e \cdot d\pmod {\varphi(p \cdot q})$

Notice that modular multiplicative inverse can be expressed as:

$$d=\frac{\varphi(p\cdot q)\cdot k + 1}{e}$$

for some $k$ multiple of $\varphi$($p\cdot q$). We know that $e$ is 17 bits (65537) so $k$ will be small, thus computing $d$ with this method would be realizable. You have to know the factorization of the semiprime for computing $\varphi(p \cdot q)$.

Mathematically other ways for computing the private key exist, such as the Euler Criterion.

For calculating the modular multiplicative inverse we would have:

$d\equiv e^{\varphi(\varphi(p \cdot q))-1}\pmod {\varphi(p \cdot q})$

As you can see we would need to have the factorization of $\varphi(p\cdot q)$, so we cannot deal with big semiprime modulus. Concretely we need the factors of $(p-1)$ and $(q-1)$ in order to compute $\varphi(p-1) \cdot \varphi(q-1)$


Are there any secure commutative ciphers?

For a set of $B$ elements (e.g. $B = 2^n$ for all the "blocks of $n$ bits"), there are $B!$ possible permutations. An ideal block cipher is such that an instance with an unknown key is indistinguishable from a permutation chosen at random, uniformly, in these $B!$ permutations.

Since permutations don't commute in general, a "perfect" commutative block cipher must work over a subset of these $B!$ permutations, where all elements of the subset actually commute with each other, and this makes a commutative block cipher highly distinguishable from a randomly chosen permutation. Namely, suppose that there is a black box which implements either the block cipher $E_K$ (for some unknown key $K$), or a randomly chosen permutation. The attacker can submit plaintexts to encrypt (that's a chosen-plaintext attack scenario), and observe the result; his goal is to determine whether the box really implements $E_K$ for some $K$, or not. He then does the following:

He selects a key $K'$ randomly, as well as a plaintext block $x$.
He sends $x$ and $y = E_{K'}(x)$ as plaintexts to encrypt with the box.
The box returns, respectively, $u$ and $v$.
The attacker checks whether $E_{K'}(u) = v$. That equation will hold with probability $1$ if the box implements $E_K$, but only $1/B$ (i.e. almost zero) if the box implements a randomly chosen permutation.

In that sense, a commutative block cipher cannot be secure "as a block cipher". Commutative encryption can be secure only as part of a protocol in which the commutative encryption primitive is not used in the same way as, say, AES. What the scenario explained above means is that a deterministic commutative cipher cannot be "IND-CPA secure" (indistinguishable from a random permutation in a chosen-plaintext attack setup). So you need some randomness injected "somewhere", which may be some padding or an other feature of the overall protocol (e.g. encryption is only applied on values chosen randomly and uniformly in a given set, which are then used to derive a "normal" symmetric key, aka hybrid encryption).


While I cannot point you to a specific paper that works as a great example for this technique, the idea is quite simple.

Assume two distributions $X,Y$ which have the same support, so random variables distributed according to one of these distributions are drawn from the same set.
Now assume you got a probabilistic adversary $A$ that takes as input $misc$ and a value $x$ that drawn according to $X$ and tries to solve some problem. Here $misc$ covers any additional inputs. As $X$ and $Y$ have the same support, we might also chose $x$ from $Y$ -- $A$ should at least accept such $x$ as input.

Let's switch to the games. Assume you got two games. In both you generate $misc$ the same way. But the games differ in how $x$ is chosen. In game 1 you chose $x$ according to $X$, in game 2 you chose $x$ according to $Y$. You might already see that if the success probability of $A$ differs, depending on if he plays in game 1 or in game 2, we can use this to distinguish the two cases, i.e. we can use this to decide from which distribution $x$ was chosen.

Say $A$ wins in game 1 with higher success probability than in game 2. Then we can built a distinguisher $D$ that takes a value $x$ and outputs 1 if $x$ was chosen from $X$ and $0$ if it was chosen from $Y$. $D$ simply runs $A(misc,x)$ and outputs 1 if $A$ succeeds. $D$ will distinguish the two cases exactly with $A$'s difference in success probability depending on which game he plays.

Hence, we can argue that if $X$ cannot be distinguished from $Y$ with probability greater $\epsilon$, the difference in $A$'s success probability between game 1 and game 2 must be limited by $\epsilon$.

That's how one game hop works. You can extend this arbitrarily. The important thing is that between two consecutive games you must only change the distribution of one of $A$'s inputs.


The requirements differ per mode of operation. AES itself is a block cipher, and as block cipher, it doesn't take an IV at all. Tweakable block ciphers may take a tweak, which may have some overlap with an IV, but AES isn't tweakable by itself.

CBC requires an unpredictable IV (to the adversary). One of the common ways is indeed to generate a 16 byte (one block) random IV. However, to do this you would require a cryptographically secure RNG, because a non-secure RNG may well be predictable given previous output.

You can use other, unique, known information as IV in some instances. However, CBC requires unpredictable data and a 16 byte IV. So e.g. a file number doesn't cut it by itself. However, you could use tricks to make it fit. For instance, you can use a secure hash on the unique data and use the leftmost 16 bytes as proto-IV. Then you can encrypt the proto-IV using the AES block cipher and use the result as IV. That way you would get an IV that is unpredictable and that doesn't have to be included with the message itself. Note that you should not perform decryption for that IV; the encrypted proto-IV is the actual IV.

Using a separate key would make your protocol ever so slightly more secure, as it brings down the chance of collisions (which an adversary might try to trigger deliberately, if possible) but it isn't required (in other words: you'd use a different key on PC's, but for embedded / lightweight systems you might a different trade off).

As indicated, creating a protocol is tricky and there may be many (other) attack vectors. Generally we try and use authenticated encryption schemes nowadays, as it at least doesn't allow for alteration of the encrypted message, which - for CBC - may also completely compromise confidentiality if plaintext or padding oracle attacks are feasible.


How can I avoid side channel attacks to scalar multiplication of Ed25519?

As pointed out in section 8.1 of the RFC, "the example implementations in this document do not attempt to be side-channel silent".

You can't write the algorithm as is. Basically, you need to always compute the point addition:

T = point_add(Q, P)
Q = select(Q, T, s & 1)
P = point_add(P, P)
s >>= 1

The select function (also called "conditional copy") selects one of the two operands depending on the value of the third, in constant time (or "side-channel silent" to be more precise). This means that you can't use branches, but just arithmetic operations.
The basic idea is to compute q ^= (q ^ t) & -b where q and t are the input and b is the select bit. If it is 0, q will stay the same; if it's 1, the -b will equal to 0xFFFF... and q will be set to t. You have to be careful to use the correct data types for it to work - though since you'll implement it in hardware that will be easy to handle. Of course, you'll need to do this for every word of every number in the elliptic curve points involved. There are many examples, here is one of them.


What are some real-world examples where one-time-pad encryption is used or can be used?

If you want to have the perfect secrecy then it is the only choice. However, it doesn't have integrity and authentication.

If you want to see when it is used, see OTP at Wikipedia, especially the cold war era.

It is not suitable for modern usage, where a lot of messages is sent/received. The drawback is the necessary condition; key length must be at least message length. Also, you must somehow transmit the OTP key securely, not by encryption. You must trust the carrier or you have to carry yourself.

A simple question arises what will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging.

Per comment: There is an interesting question on this site; Is there a companion algorithm for OTP to ensure integrity and/or authentication?, asking the companions for integrity and authenticity since the OTP only provides confidentiality. Clearly, If you send your data only encrypted with OTP, the Oscar, the middle man, can modify the message. Of course, if he has no knowledge of the structure of the data, the modifications are random. In the other case, the results can be catastrophic. Save the man can be converted into Kill the man.

As some said, (most of | sometimes,) the time integrity is more important the confidentiality. You may not need encryption but integrity is almost necessary.


Encrypting and Decrypting a 19-digits long BigInteger

Well, first of all, when we do encryption, we generally insist that there is a "key" involved; this key is something that the person doing the encryption and the person doing the decryption knows, but no one else.  The goal of an encryption method is that someone who doesn't know the key can't gain any information from the encrypted messages.

Note: there are methods where the key that the encryptor knows differs from the key the decryptor knows; for example, the encryption key might not be able to be used to decrypt.  This comes in handy at times; I'll assume that you don't need that.

Now, the next questions are:

Do you care whether, if you encrypt the exact same number twice, you come up with the same encryption"?  Usually, we do care (because we don't want someone looking at the encrypted messages to deduce that we sent the same plaintext message twice), however you might not (for example, you might know that you'll never actually encrypt the exact same number twice).
Do you care whether, if someone tweaks the ciphertext, and you decrypt that ciphertext, you get a warning that the ciphertext isn't what was encrypted?  Generally, we do; we do this by adding a cryptographical checksum; if that checksum doesn't validate, we know that something's not right.

However, here is a procedure that doesn't address either of these issues:

First of all, a maximum 19-digits long bignum fits within 64 bits (almost exactly); the first step of the encryption process will to convert the Bignum into an 8 byte (64 bit) integer.
Now that we have an 8 byte integer, the easiest way to encrypt it would be to have a 3DES key, and encrypt those 8 bytes in ECB mode (in case you're wondering, ECB mode is almost always the wrong solution; this is one of the few situations where it is appropriate).
Now that we have an encrypted 64 bit value, we convert that value into a base-32 value (using the 10 digits and 22 lower case characters to represent the 32 digits; a 64 bit value can be represented by 13 base-32 digits; that's our encrypted text.

Decryption (as long as you have the 3DES key) is straight-forward; you just follow the procedure backwards, reversing each step.

Now, why did I leave the above two issues unaddressed?  Well, that's because such an extension would cause the ciphertext to be longer.  The problem with that is your limit that the ciphertext be limited to a maximum of 16 digits and lower case characters; that means that we have (at best) 18 bits or so of possible ciphertext expansion, and that's not much.

What this means is that if you do care about the above two problems, you may need to rethink your limits of the ciphertext size (or possibly expanding the ciphertext alphabet; allowing upper case characters would mean we have 31 bits to play with).


Is secure communication without public-key crytography feasible?

The obvious answer is symmetric keys.  You'll find that this is actually what asymmetric keys end up used for, exchanging symmetric keys.  If you trust someone who gives you a key, and you can trust that no one else has it, that's about as secure as it gets.  The difficult of satisfying those requirements is why we have asymmetric keys.


In any RSA-type cryptosystem, a public key necessarily has a modulus $n$, and sometimes has an exponent $e$ if it's not prescribed by the cryptosystem.  Sensible cryptosystems like RSA-KEM can prescribe $e = 3$, but some defective standards, based on mistakes like RSAES-PKCS1-v1_5, may require $e$ to be $e = 65537$ or larger and may allow $e$ to vary.

A private key can come in any of several forms:

the factors $p$ and $q$ of $n = pq$
a private exponent $d$, which solves $e \cdot d \equiv 1 \pmod{\lambda(n)}$
Chinese remainder theorem exponents $d_p \equiv d \pmod{p - 1}$ and $d_q \equiv d \pmod{q - 1})$

Any of these forms of the private key is equivalent, given knowledge of $n$: from $p$ and $q$ you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ with the extended Euclidean algorithm; from $d$ you can recover a multiple $e \cdot d - 1$ of $\lambda(n)$ and without much additional difficulty proceed to factor $n$; etc.  Often, as in, e.g., OpenSSL, many redundant parts of the private key are stored together to speed up the computation.

The main question, then, is: Are the public exponent $e$ and the private exponent $d$ interchangeable?  And the answer is: No.

In Rivest, Shamir, and Adleman's seminal paper, the proposed method was to choose $d$ at random to be coprime with $\phi(n) = (p - 1)(q - 1)$ and then to derive $e$ from $d$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  One could do it the other way around: choose $e$ at random to be coprime with $\phi(n)$, and then to derive $d$ from $e$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  So, if you were stuck in 1978, it might look like the roles of the two exponents are interchangeable—but if you were stuck in 1978, your encryption scheme would also be trivially breakable,* so maybe you don't want to stay in 1978.

The main cost for a user of RSA is computing modular exponentiation, which for exponent $x$ costs $\lfloor\log_2 x\rfloor$ squarings and $H(x) - 1$ multiplications, where $H$ is Hamming weight.  The most efficient exponent is 3—but you can only do this for the public exponent!  If you always picked the private exponent $d = 3$, you would still have to publish $e$ in order for anyone to encrypt messages—but if you did that, then armed with knowledge of $e$ and $d$ I could find $\lambda(n)$ and factor $n$ and break the whole cryptosystem!

‘OK, fine,’ you say, ‘so $d = 3$ is no good, but what if I just picked $d$ to be small to speed up decryption?’  As it happens, if $d$ is merely smaller than about $\sqrt[4] n$, I can use Wiener's attack or a variant thereof to recover it!  It is therefore crucial that the private exponent $d$ be near uniformly distributed in the whole possible space, which is effectively the case even if you choose the public exponent $e$ to always be something small like 3 or 65537.

Thus while it is perfectly safe in sensible RSA-type cryptosystems to always use $e = 3$, it is dangerous to choose even moderately small $d$; the exponents are very much not interchangeable.

P.S.  You may be tempted, by the seductive symmetry of the equations $c = m^e \bmod n$ and $m = c^d \bmod n$, to treat encryption and signature as interchangeable too.  Don't do it!  It's a trap!  If you try to shoehorn a message into this shape, you'll likely end up shooting yourself in the foot; there's much more to encryption and much more to signature, and beyond the use of exponentiation they bear very little resemblance—and if you naively try to combine the two with the same keys you will probably shoot yourself in the other foot too.  At that point, you'd better hope you're an octopus.

* They recommend what is effectively RSA-ECB for encryption, and a trivially forgeable hashless signature scheme.  The first secure signature scheme by modern standards—assuming suitably scaled parameters—wasn't published until a year later by Rabin in 1979, using the qualitatively different exponent $e = 2$, and the first secure encryption scheme by modern standards wasn't published until some time after that.


enhanced hash password in bcrypt for nuGet library

Why do we use EnhancedHashPassword in nuGet library and chose an SHA algorithm like this?

The Bcrypt uses a 448-bit key that makes a 56-byte password limit. Some libraries can drop parts longer than 56-byte of the passwords or don't accept it. This is not good, therefore before bcrypt a hash is applied to the password. This is the  EnhancedHashPassword method in the library and this may increase the entropy.

The nuGet library by default uses SHA-384 which has known resistance to length extension attacks. SHA-512 doesn't have.

  when do we use the SHA algorithm after blowfish or before?

We use the hash algorithm before. The aim is using all of the password information in the blowfish. This is achieved by hashing which can hash arbitrary length input into a fixed size.

Modern password hashing algorithm Argon2 doesn't have the small password weakness. It can accept a password up to  $2^{32}\hbox{-}1$ bytes. On the other hand, PBKDF2 has no theoretical limit except the standard limits of the utilized hash functions 1,2.


Is there a way to compress multiple signatures of the same data?

You can use multi-signatures.

One example is the BN06 scheme described in the paper:
Bellare, Neven - Multi-signatures in the plain public-Key model and a general forking lemma


Do you have a noise model in mind?
If the noise affects only a small portion of shares, regular shamir secret sharing is robust. You only need k complete shares.
For other scenarios, like having a few bit flips across all shares. You add any error correction code after creating the shares before distributing them. E.g Reed Solomon. so That each party still gets a single share but with extra error correction information.


Discrete log problem, when we have many examples

In practice the view would be that no, it does not get any easier. Indeed many popular deployed schemes depend on it. For example the Trusted Authority in the Boneh-Franklin IBE scheme has a master secret s and issues private keys to users in the form s.ID_i, where ID_i is a point on an elliptic curve, and ID_i is related to the identity of the i-th user. It is a standard DL problem to find s from such a private key. Nevertheless the Boneh-Franklin scheme is assumed strong against a conspiracy of multiple users who can pool their secrets in an attempt to find the master secret s.


I have never heard of this reason, and I don't quite understand it. In general, the security of Diffie-Hellman key exchange is reduced to the DDH assumption. According to this assumption, the result of the key exchange is a group element that is computationally indistinguishable from a random/uniformly distributed element in the group. However, what is important to note is that a uniformly distributed group element is not a uniformly distributed string (where the latter must have each bit equal 0 with probability 1/2 and equal 1 with probability 1/2). In particular, if you work in $\mathbb{Z}_p^*$ then the most significant bit will certainly not be uniformly distributed. Likewise, if you are working in an Elliptic curve group, then the result is a pair of field elements which fulfill the Elliptic curve equation. Therefore, in order to derive a uniformly distributed string, you need to apply a function that extracts a uniform string from a high entropy source. These are called extractors or key derivation functions. This is the reason that you hash.

I note that it's possible to prove the security of Diffie-Hellman key exchange under the CDH assumption and in the random oracle model. In this case, the hash function is needed to get a long pseudorandom string from a computational assumption. However, I think that explaining this here will be "too much information".


Could a quantum computer recover files from ransomware if the attacker doubly encrypted them with RSA-4096?

Ask your friend:

Do you even have the RSA moduli used by the ransomware?

If not, even Shor's alogrithm on a real honest-to-goodness large quantum computer is not going to help.  And there's no reason for the ransomware to share the RSA moduli with you.
While RSA ciphertexts/signatures can be deanonymized by the German tank problem, there's not enough information to reconstruct enough of the modulus to apply Shor.

Do you have a billion euros rattling around in your pocket?

If not, you can't afford the research and construction for a quantum computer.

Do you have a couple decades to wait?

If not, you are too impatient and quantum computers won't be developed in time.

Do you feel lucky?

If not, you might have gambled your billion euros and decades of lifetime on a coin coming up heads when actually it's tails and quantum computers can't actually be made to work.

If the answer to any of these questions is ‘no’, your friend's data are hopelessly lost.  Advise that your friend invest in solid backups, and specifically in backups that cannot be deleted from the computer they are backing up—if you simply back up to an external USB drive, or simply back up to an S3 bucket with an access key that has authority to create and delete archives, then you are not protected.

Also advise your friend that Geek Squad is not their friend: the FBI cultivates informants at Geek Squad to actively search for material at the FBI's request on any computers they work on and forward their data to the FBI[1][2][3][4].

All that said, using RSA twice doesn't really matter: if you had the RSA moduli, then if made a Shor-capable quantum computer could factor the moduli in only twice the time, and the size of the quantum computer needed is linear in the number of bits in the modulus.


How to Distribute the Shares using Secret Sharing for arbitrary Monotone Access Structures

I will make a start by observing that not every monotone access structure can be realized by means of $(t,n)$ threshold secret sharing (here we require $t$ out of the $n$ shares need to be available for reconstruction).

First let us define a monotone access structure. Let $P$ be a set of participants. An access structure $\Gamma$ is a collection of nonempty subsets of the power set $2^P$. This structure is called monotone, if $X\in \Gamma$ implies $Y\in \Gamma$ for all supersets $Y\supseteq X$.

Note that defining monotone access structures perfectly makes sense in context of secret sharing, since every set in the access structure can reconstruct the secret, so every superset containing this set can trivially do so.

Shamir does not provide a general solution

Let us construct a counterexample for threshold secret sharing:

Consider the set of participants $P=\{A,B,C,D\}$ and a monotone access structure $\Gamma=\{\{A,B\},\{C,D\}\}$. We assume we use a $(t,4)$ threshold scheme to share a secret $k$ among the
participants $A,B,C,D$ and $k$ can only be reconstructed by subsets which are elements of $\Gamma$.

Now let $a,b,c$ and $d$
be the weights of the shares that are assigned to the users of $P$. Then it must hold that $a+b\geq t$ and $c+d \geq t$, where $t$ is the threshold.

WLOG let $a\geq b$ and $c \geq d$. Since

$a+b\geq t$ and $a\geq b$ we have $a+a\geq a+b \geq t$ which gives that $a\geq t/2$.
Furthermore, since $c+d\geq t$ and $c\geq d$ it follows that $c\geq t/2$.

This implies that $a+c \geq  t$ and thus $A$ and $C$ are able to reconstruct $k$, but $\{A,C\}\notin \Gamma$.

Towards secret sharing for monotone access structures

Ok, now we go on to realize secret sharing for general monotone access structure. Let $P=\{P_1,\ldots,P_n\}$ be the set
of participants.
We need some definitions first:

Minimal authorized subset: Let $\Gamma$ be an access structure then
 ${\cal C}\in \Gamma$ is a minimal authorized subset if $H \notin \Gamma$ whenever $H\subset {\cal C}$ (i.e., whenever we remove a participant, then the set will no longer be authorized).

Now we call the set of minimal authorized subsets associated to $\Gamma$ a basis and
 denote it by $\Gamma_0$. And it is sufficient to work with the basis henceforth (as $\Gamma$ can be obtained by taking the closure, i.e., by monotonicity).

If we look at a $(t,n)$ threshold scheme, then we have $\Gamma = \{G \subseteq P : |G|\geq k\}$
 and $\Gamma_0 = \{G \subseteq P : |G| = k\}$.

Maximal unauthorized subset: Let $\Gamma$ be an access structure and call  $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$
 the set of maximal unauthorized subsets if for every ${\cal B}_i$ holds: ${\cal B}_i\notin \Gamma$
  and ${\cal B}_i\cup P_j\in \Gamma$ for each $P_j\notin {\cal B}_i$ (i.e., whenever we take a participant that is not
  yet included we will obtain an authorized set)

Now we can define a dual representation of an access structure $\Gamma$ denoted as $\Gamma^*$.

We can write an access structure $\Gamma = \bigvee_{{\cal B}\in \Gamma} \bigwedge_{P_i\in \cal B} P_i$ or as a sum of products
  (replacing conjunctions by $\cdot$ and disjunction by $+$).

Then the dual access structure is obtained by exchanging the operators,
 i.e., $\Gamma^* = \bigwedge_{{\cal B}\in \Gamma} \bigvee_{P_i\in \cal B} P_i$ (or as a product of sums).

We have the following: Let $\Gamma$ be an access structure on $P$ and $M=\{{\cal B}_1,\ldots,{\cal B}_m\}$ the
 set of maximal unauthorized subsets, then $\Gamma_0^*=\{{\cal A}_1,\ldots,{\cal A}_m\}$ such that ${\cal B}_i=P\setminus {\cal A}_i$
 is the set of minimal authorized subsets in the dual form.

Ok, let us take additive perfect secret sharing over a prime field $Z_p$, i.e., the secret $k$ is represented $k=\sum_{i=1}^m s_i \pmod p$ for random
 $s_i$.

Then we can come up with the following matrix, where we have $b_{i,j}=1$ if $P_i\in {\cal A_j}$ and $b_{i,j}=0$ otherwise.

Now, we can distribute
 the shares $s_1,\ldots,s_m$ in the following way. Every user $P_i$ obtains the set of shares $S_i=\{s_j: b_{i,j}=1\}$ (i.e., a participant obtains a share if he shows up in the respective set of the dual basis or equivalently, obtains no share if he shows up in the respective set of the maximal unauthorized subsets).

I will not come up with an explicit example anymore today. But this secret sharing enables every authorized subset in $\Gamma$ to reconstruct the secret $k$ and any non-authorized set will not be able to do so.


First of all, it's not true that, in the "Base Conversion" case, that the output is actually equidistributed.  It is easy to show that, if the size of the alphabet isn't a power of 2, and that there is a bound on the amount of entropy you can draw, that no algorithm can generate a truly equidistributed output (although you can come arbitrarily close).

In the case of your algorithm, well, we can make a fairly bad case by considering an alphabet of 127 characters, and asking the algorithm for a string consisting of a single symbol; your algorithm will set bytes = 1, and thus draw a single random byte; this means that some (most) characters will be generated with probability $2^{-7}$, but a few will be generated with probability $2^{-8}$ (that is, a factor of 2 less).  This can easily be fixed by requesting a fixed constant (say, 16 bytes) above what you actually need.  This will reduce the ratio of probabilities for various strings to at most $1 + 2^{-128}$, which is probably good enough.

That said, I would personally recommend the value picking approach.  The value of that approach is that it is simpler; and simpler means easier to get right (and to verify that it is right), and getting things right is quite important for security.

Now, one complaint with your version of the value picking approach would be that if the alphabet is small, it'll take quite a few random outputs before you come approach bytes in the correct range.  This is easy to fix if you look at only the lower $n$ bits of the random output (where $2^n$ is the smallest power of 2 greater than or equal to the string size).  With this change, the average number of random bytes the value picking approach will use will be less than twice the output size.


This is similar to HMAC-SHA-256 with 64-byte key, except that

HMAC-SHA-256 has two SHA-256 layers where there is three;
HMAC derives its two key_j from a single one (using XOR with constants) rather than using independent keys;
HMAC potentially reveals its whole 32-byte output, rather than part of it;
HMAC's security model  includes the adversary choosing the messages (that is, values of special_key) for which it obtains input; and seeking something weaker than key recovery (ability to distinguish the function from random).

It follows this is at least as strong as HMAC-SHA-256 is: with a strong theoretical argument even for relatively weak hypothesis on SHA-256 (the generic proof of HMAC applies), and unbroken.

Key leak by some side channels might still be an issue for a particular implementation, though.


First of all, AES is like an alias for a winner of a contest that has started in 1997 and finishes in 2000 with the announcement of Rijndael's win. A nice document to learn AES is the link given by Richie Frame in the comments of this question.

Trying to do an small summary, there are two main families of symmetric ciphers and Rijndael is a member of the Substitution-Permutation Network (SPN). The other family is the Feistel Networks with DES as a highlighted member (the AES predecessor).

The main goal of a symmetric cypher is to provide enough confusion and diffusion (Shannon properties) and often this is provided by a set of rounds where different operations are applied on each of them. The key shall be applied in those rounds, and in the case of Rijndael is not the key itself, but parts of a Key Derivation Function.

Long a go I've wrote something, and perhaps the image I've made could help you to understand the iterative process of the KDF in Rijndael. It had a mistake and I'm placing here a fixed version of the image. That is for 128 bit keys, but it's not hard to imagine how different it is with the other key sizes.

Rijndael have some good characteristics like efficiency in software and in hardware, specially because in the lowest level all the operations are bit xors (but this has been already pointed in the comments). Perhaps one cons would be the complexity to protect against side channel attacks.


Yes, the attack you sketched out would work - in theory.

In practice, it's an efficient (computable in polynomial time) mapping $\psi:E\rightarrow\mathbb Z_n$ we're lacking. As for the unefficient mappings, $\psi:x\cdot P\mapsto x$ would be perfectly fine theoretically, but we don't know how to calculate it (it's the elliptic curve discrete logarithm problem, aka ECDLP).

Furthermore you might say: "well, we can construct an isomorphism in theory, so why don't we just map it somehow and apply the GNFS on $\mathbb Z_n$?" The problem is again, that we don't know an efficient mapping and even if we would, we would need one (for this attack) that preserves birational equivalence to transfer addition laws from one group to the other and if such a mapping would exist, people probably would have found it in ECC's 25 year(+) history.

Bottom line: The DLP isn't hard because of the elements you want to find, it is hard because of the element's representation.


For Diffie-Hellman key exchange method, what are examples of very poor a and b values?

In Diffie-Hellman key exchange, the values of the secret exponent like $a$ (or equivalently $b$) must be generated in a way such that from $g$, $p$, and $g^a\bmod p$ (which will get public), it can not be found $a'$ with $g^{a'}\equiv g^a\pmod p$, or equivalently $a'\equiv a\pmod q$ where $q$ is the order of $g$. This condition is necessary, because guessing $a'$ is as good as guessing $a$, and breaks the DH protocol.

This condition implies that some ways to generate $a$ are bad. In particular, any value of $a$ known or guessable by the adversary is bad, including small values of $a$.

As an illustration of the above, and that choosing $a$ randomly in a large set is not good enough, it would be bad to generate $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$: in this setup, DH could be attacked with algorithms requiring only $\sqrt{2^{80}}=2^{40}$ effort (including a simple variant of baby-step giant-step, now detailed in the last section).

Also, if it happened that the order $q_a$ of $g^a\bmod p$ was small (which is possible if the order $q$ of $g$ has small divisors), DH would be vulnerable; for example, to computing ${(g^a)}^j\bmod p$ for increasing values of $j$, allowing a guess of ${(g^a)}^b\bmod p$, as soon as $j\equiv b\bmod q_a$. Thus for maximum safety, $a$ should be such that the order $q_a$ of $g^a\bmod p$ is large. This explains why $q$ is often chosen to be a large prime: $0<a<q$ then insures $\gcd(a,q)=1$ and that $q_a$ is $q$ (thus large) without any explicit check.

Assume that the order of $g$ is a large prime $q$; perhaps $q=(p-1)/2$, or some other large prime dividing $p-1$, with $q>2^{2k}$ for $k$-bit security. It is then safe to generate $a$ uniformly randomly in range $[1\dots q[$. That criteria is used in the weakest form of the Diffie-Hellman assumption (thus the safest, and common).

It is demonstrably very nearly as safe to allow $a=0$, or/and generate $a$ uniformly randomly in range $[1\dots p[$ (which is also common and safe if the order of $g$ is $p-1$ with $(p-1)/2$ a large prime, rather than $g$ of prime order).

Another common method is generating $a$ as a string of at least $2k$ random bits; that's relying on a stronger form of the Diffie-Hellman assumption (thus less demonstrably safe, but still conjecturally safe).

Following (now gone) comments, here is how a choice of $a$ as $r_{80}+q\cdot r_{256}$ for some 80-bit and 256-bit random $r_{80}$ and $r_{256}$ (where $q$ is the order of $g$) could be attacked, with $\sqrt{2^{80}}=2^{40}$ work (essentially that many pairs of modular multiplications modulo $p$, and searches in a huge table):

Giant steps: tabulate $g^a\cdot{(g^{-(2^{40})})}^i\bmod p$ for all $i$ with $0\le i<2^{40}$, requiring about $2^{40}$ modular multiplications and comparatively negligible extra work.
Baby steps: for $j$ increasing from $0$, compute $g^j\bmod p$ and search it in the previous table until it is found; that will happen precisely for $j=r_{80}\bmod 2^{40}$, and the match will be with the value tabulated for $i=\lfloor r_{80}/2^{40}\rfloor$ (the proof uses that $g^q\bmod p=1$); it thus requires at most $2^{40}$ modular multiplications and searches.
We thus know $r_{80}=i\cdot2^{40}+j$. This is enough to compute $g^{a\cdot b}\bmod p$ as ${(g^b)}^{r_{80}}\bmod p$ and break DH.

Techniques exist to considerably reduce the amount of memory needed.

Note: $r_{256}$ is there as an (admittedly artificial) way to make the set of allowable $a$ large, but brings no actual security; the constant 256 is entirely arbitrary.


POODLE is primarily a padding oracle attack against SSLv3.0, which is inherently vulnerable to the attack due to the protocol design. The "on downgraded legacy encryption" part of POODLE's name comes from the fact that most SSL/TLS client implementations will allow a TLS connection to downgrade to SSLv3.0 if the handshake fails - see this answer for more detailed information around TLS downgrade attacks. Since an attacker in a man-in-the-middle position can simply drop or mangle packets, it is relatively trivial to cause a TLS connection to downgrade to SSLv3.0, which then becomes vulnerable to the padding oracle attack against CBC.

SSLv3.0 only validates that the padding byte length is ok, and doesn't require the actual padding bytes to be checked for validity; they can be anything, as far as the protocol specification is concerned. Furthermore, the padding is not authenticated; it uses a MAC-then-CBC method. The padding oracle attack works by causing the padding data to move across a block boundary (this can be done by increasing the plaintext length until the ciphertext length increases by one block) and then swapping out the padding block for any previous ciphertext block. If the decrypted result has a final byte of value equal to the expected padding length, it will be accepted, which leaks the value of a single plaintext byte. As the process is non-deterministic due to the random IV per connection, it should take at most 256 connections to leak each byte. The attacker can then shift the position of the target plaintext within the connection by one byte and attack it again, repeatedly testing via the oracle and shifting across until all target bytes have been revealed.

The normal recommendation for POODLE where SSLv3.0 cannot be disabled entirely is to implement TLS_FALLBACK_SCSV support. As this answer describes, this flag forces the negotiated connection to use the highest possible supported protocol version, which is mutually authenticated by the use of exchanged Finished messages, thus preventing downgrades outright.

There is a secondary variant of POODLE which works against certain implementations of TLS, instead of just the SSLv3.0 protocol. The key point here is that the vulnerability is not inherent to the TLS protocol at all, but rather is exploitable only in cases of poor implementation. The reason that sensible implementations of TLS (see note below) are protected against POODLE is that the CBC padding is fully validated at the server side (i.e. all padding bytes must be equal in value to the integral size of the padding, and the server must check this fact). This makes attacking the padding significantly more difficult. However, it was found that some implementations of TLS did not check the padding correctly, and were still vulnerable to POODLE.

(note: the TLSv1.0 specification does not state that padding must be checked; this requirement was introduced in TLSv1.1 and continued in TLSv1.2. As such, TLSv1.0-compliant implementations may still be vulnerable to POODLE, hence why I used the term "sensible implementations" rather than "compliant implementations" above.)


How to sign messages using the NOISE Protocol Framework?

If you need signatures, use the signatures API. Signing key pairs may or may not be ephemeral, this depends on your use case. You'll need some way to determine that a signing keypair belongs to whoever you think it belongs to, this can't be handled by the library alone.
Signing key pairs and key exchange key pairs are different data types (hydro_sign_keypair vs hydro_kx_keypair or hydro_kx_session_keypair) and thus can't be used interchangeably.
A session should last at most for as long as a given connection using the service lasts. That might be weeks, but is more likely only as long as a user stays active.


Does the public key and private key for WhatsApp only remain within a WhatsApp account

I got like a feeling that WhatsApp works by making use of public keys and private keys encryption.

That's correct, WhatsApp uses Curve25519.

  My question is, where would the private key of this recipient be stored, like within their account?

The keys are generated client-side, so they should be stored on your phone.

  Also, how would the whole key thing work in a WhatsApp group as there are multiple users involved?

According to their paper:

Traditional unencrypted messenger apps typically employ “server-side fan-out” for group messages. A client wishing to send a message to a group of users transmits a single message, which is then distributed N times to the N different group members by the server.

This is in contrast to “client-side fan-out,” where a client would transmit a single message N times to the N different group members itself.

The exact procedure

The first time a WhatsApp group member sends a message to a group:

The sender generates a random 32-byte Chain Key.
The sender generates a random Curve25519 Signature Key key pair.
The sender combines the 32-byte Chain Key and the public key from the Signature Key into a Sender Key message.
The sender individually encrypts the Sender Key to each  member of the group, using the pairwise messaging protocol explained previously.

For all subsequent messages to the group:

The sender derives a Message Key from the Chain Key, and updates the Chain Key.
The sender encrypts the message using AES256 in CbC mode.
The sender signs the ciphertext using the Signature Key.
The sender transmits the single ciphertext message to the server, which does server-side fan-out to all group participants.

The “hash ratchet” of the message sender’s Chain Key provides forward secrecy . Whenever a group member leaves, all group participants clear their Sender Key and start over.

Important here is point number 4:

  The sender individually encrypts the Sender Key to each member of the group, [...].

If you need even more details then you can click here to download their whitepaper.


How to perform the lfsr scrambling used in PCIe for 2 byte input?

The online magma calculator

http://magma.maths.usyd.edu.au/calc/

tells me this LFSR corresponds to a primitive polynomial since $$G(X) = X^{23} + X^ {21} + X^{16} + X^{8} + X^5 + X^2 + 1$$
is primitive.

Thus, some phase of the output sequence is given by $$tr(\alpha^t)$$ where $tr:GF(2^{23})\rightarrow GF(2)$ is the trace map and $\alpha \in GF(2^{23})$ is primitive.

The minimal polynomial of $\alpha^2$ is also $G(X)$ and it is the polynomial generating the decimation by 2 (the minimal polynomial of $\alpha^2.$ But this is the same polynomial since an element and its square are conjugates. This is because
$$
G(X)=\prod_{i=1}^{23} (X-\alpha^{2^{i-1}}),
$$
from standard finite field results.

The decimation by 2 is $s(t+2^{22})$ if $s(t)$ is the original sequence in its characteristic phase, i.e., the phase that satisfies $$s(2t)=s(t)$$
for all $t \pmod{2^{23}-1}.$


Where do key generation algorithms take the randomness from?

Applications that generate key get the randomness (entropy) from the operating system. The operating system, in turn, gets the randomness where it can find it. Ideally the OS gets randomness from a proper hardware generator, which is present in modern PC and smartphone processors. These hardware generators are based on physical phenomena that are not reproducible; a variety of techniques exist. Additionally, the OS accumulates randomness through the timing of user actions (such as moving the mouse), of network packets, of disk reads, etc. White noise from a microphone or camera can also provide randomness. The difficulty with such ad hoc sources is that it's difficult to estimate how random they are: a hard disk's timing is predictable in theory (and an SSD much more), a given user tends to act in broadly similar manners, a sensor may be saturated, etc. This is why a dedicated hardware generator is preferable, assuming that it's programmed and used properly.

Hardware randomness sources are never used directly, because they tend to have strong biases: they don't come in neat bits that have an even chance of being 0 or 1. The randomness is fed through a cryptographic algorithm called a pseudorandom number generator (PRNG) which produces a practically endless stream of uniformly random bits from a small amount (hundreds of bits) of entropy.

Operating systems have a useful tool to reduce the expense of collecting entropy: entropy doesn't wear out, so it can be saved and reuse. An operating system can save the state of the random generator and, at boot time, load it, generate a new state and save that. This way, as soon as there has been sufficient entropy once, there is sufficient entropy forever on that machine.

Applications such as Veracrypt, GnuPG, etc. ask the OS for randomness. On Linux, they can read /dev/random or /dev/urandom, or call the getrandom system call (the differences between those are beyond the scope of this answer). On Windows, the system call is CryptGenRandom. Other operating systems designed to support cryptographic applications have similar interfaces.

Applications almost always use the OS's random generator as a seed for their own PRNG. This is cryptographically safe and improves performance.

Why do some applications ask you to move the mouse? There are several reasons:

In case the OS doesn't have as much entropy in its random generator, this improves the situation a bit.
Some applications were written for 20th century operating systems that lacked a random generator interface (e.g. Windows 9x) and needed to collect their own entropy.
As you can witness, it gives the user a warm fuzzy feeling that they're getting something really random. It's actually mostly for show.


Someone answered it in another "exchange" site: https://electronics.stackexchange.com/questions/1830/md5-implementation-for-microcontroller

There you have links to C implementations, etc.

And yes, it's possible to implement MD5 and SHA1 in 8bits, you'll just have to worki with 16 (or 32) bits operations, not that hard...


OpenSSL supports AES, Camellia, ChaCha. How about Twofish, Threefish, Serpent?

AES is the main block cipher in use today, standardized by NIST. Camellia is a Japanese standardized cipher. ChaCha is a fast stream cipher specified by Bernstein and incorporated into TLS with support from Google.
Serpent and Twofish were AES last round candidates that didn't make it. Serpent is not that fast, and Twofish is relatively fast but not compared to AES when hardware acceleration is used. Both are block ciphers that are really not needed as long as we deem AES to be secure.
Threefish was mainly designed for the Skein hash function. This tweakable block cipher is not used much. It Skein had been chosen as SHA-3 then it would have stood a better chance. For now an authenticated form of Keccak would make more sense.
So yeah, two standardized ciphers and a fast stream ciphers are supported, none of which are broken. There is no reason to include the also-ran's and a cipher made specifically for a hash function which was also not standardized.


Is ElGamal encryption still secure if the randomness is known to be even?

Suppose that computations are done in $\mathbb{F}_p^*$ for some prime $p$.  Let $c = g^m g^{kr} \bmod p$.  If $r$ is even then $g^{kr}$ is a square modulo $p$.  As a consequence, assuming that $g$ is a non-square modulo $p$, the Legendre symbol of $c$ modulo $p$ will leak the least significant bit of $m$: if $c^{(p-1)/2} \equiv 1 \bmod p$ then $m \bmod 2 = 0$; otherwise $m \bmod 2 = 1$.

Remark  If $g$ is a generator of large prime order $q$ (as should be the case for a proper implementation of ElGamal-like encryption), choosing even values for random $r$ should not help an adversary.  To see it, observe that (1) $g$ and $h := g^2 \bmod p$ generate the same group of order $q$, and (2) letting $M = g^m$ the corresponding ciphertext $(g^r, M \cdot g^{kr})$ can be rewritten as $(h^{r'}, M \cdot h^{kr'})$ where $r' = r/2 \pmod q$.

However, if $r$ is chosen at random as an even integer in $[0, q)$ then one bit of randomness is lost.


Why was Rijndael the only cipher to have a variable number of rounds?

The others had a fixed number of rounds (32 for Serpent, 16 for Twofish, etc.) regardless of the key size. Why was this?
Is there some cryptographic attack which is unique to Rijndael which would warrant this?

During the second AES conference, the Rijndael team was asked about this design decision.
They turned it around, and pointed out that smaller keys have a smaller level of security (and hence a lower threshold on what would be considered a break).  After all, an attack that works with effort $O(2^{180})$ would be considered a break against a 256 bit key, but not against a 128 bit key, hence for 128 bit keys, you can get by with fewer rounds.  The same type of reasoning would appear to be applicable to the other candidates (although it would be a tad more complicated with MARS, given that it uses multiple types of rounds internally).
Now, the Serpent team responded that they didn't want to give anyone a reason not to use 256 bit keys, hence they would not consider a faster version for shorter keys.  As for the other three teams (MARS, RC6, Twofish), it appears that it just never occurred to them.


Well yes, $P$ can generate $A^cT$ and send it over, but why would it help?

The point of this protocol is that $P$ proofs to $V$ that it knows $x$, without revealing anything about $x$. The way that $P$ does this is that given some randomly chosen $t$ and a challenge $c$, it can compute an $s$ such that $g^s=A^cT$. The fact that $P$ can compute this $s$ proves knowledge of $x$ (note that $s=xc+t$). Anyone that does not know $x$, cannot compute $s$ (assuming some hard problem).

On the other hand, anyone can compute $A^cT$ given $A,c,T$, so this does not prove anything about knowledge of $x$.


Can pbkdf2 be used with a fixed salt to give a deterministic slow hash?

Yes, this is thought to be so.
The point of PBKDF2, scrypt & bcrypt is to produce the same output on the same input, otherwise they would be useless as key derivation function (KDF).
I personally prefer Argon2 since you can tweak it a bit more, it makes a better usage of RAM and computing time, etc.
As explained on Wikipedia, PBKDF2 is not the best because it can be implemented on ASIC devices, which makes brute-force attacks using ASICs or even GPUs easier than for certain other KDFs.
Using a fixed salt for all entries just allows a dictionary attack against your specific application to be mounted, although this should still be somewhat hindered by the computational cost it would imply. That's not too worrying as long as you've generated the salt yourself and are not using a generic value (such as the empty one). But in general we never recommend using a fixed salt.
Instead, note that the good practice would be either to derive the salt in a deterministic way (from the username, for example), or to store the salt in the database next to the password (so that each password has a different salt.)


Can a cryptosystem be unconditional secure if the same key $k \in \mathcal K$ is used for more than one encryption?

It is easy to construct an unconditionally secure encryption scheme where the key is reused to encrypt multiple messages. Simply take any unconditionally secure encryption scheme that can be reused $1$ time and then to generate keys sample $m$ keys of this original scheme (e.g., $m$ OTP keys). Now you can use these $m$ keys to encrypt $m$ messages and obviously the security is still that of the original scheme.

Of course, you may argue that this is 'cheating', because now we have an encryption scheme with keys of size $n\times m$, where $n$ is the size of a message. However, this cannot be helped. For the scheme to be unconditionally secure the key must be at least as long as the total amount of bits we can communicate using it. To see why this is the case consider that to have perfect secrecy given a series of ciphertexts any series of messages must be equally likely. This means that for each series of message bits (combining all the messages sent) we need one distinct key, i.e., the key must be at least the size of the total amount of bits encrypted.


Do the Syllae algorithm and Malaysian cipher from Rubicon exist?

Using a search engine, you would quickly have discovered hints that they’re “home-brew riddles”.
For example:

Travers uncovers the same messages hidden inside the crossword puzzles of several major newspapers. He stumbles upon a series of 27 10-digit numbers, one set for each World Series the Yankees have won, that, by way of historic baseball dates, lead to a group of names. And when he finds a sheet of paper marked with 21 three-letter clusters, it's described as a "simple" code designed to direct the recipient to particular letters in a certain book.

source: “Conspiracy thriller 'Rubicon' challenges viewers”, reviewjournal.com, 1 August 2010

Will's observational gifts begin to decipher clues for him that may uncover a sinister and complex conspiracy.

source: “Will Travers”, rubicon.wikia.com, 1 August 2010

As for your questions:

Are they real?

Obviously, the answer is “yes”… based on the fact that an amatuer/home-brew way exists with which viewers have been challenged. But it is my no means something you’ld expect to be known in the realms of professional cryptography.
So, they are “real” in the sense that they ”exist” as amateur/home-brew puzzles. Yet, there is a huge difference between amateur/home-brew puzzles or “deciphering riddles” and well-vetted, professional cryptography!

If so where could I find more info about them?

We don’t tend to handle amateur/home-brew ciphers at Crypto.SE, and we’re definitely not a valid replacement for your favorite search engine. But using the later, you should be able to find fan-sites and forums providing according information. One of many starting points would be the Rubicon Wiki.
Besides that, something tells me that watching the series might help too… but that might just be me.


Password-based encryption with small typos allowed

A possible solution:

When encrypting, ask the user to enter a password $p$. Produce a salt $s$. Enumerate the password with all tolerable typos to get array $a$. For each $a_i$, calculate $b_i=hash(a_i)$ to get array $b$. In the output file, write the salt. Generate a random key $k$. And for each $b_i$, write the pair $(hash(b_i||s),b_i\oplus k)$. Write the file to encrypt encrypted with key $k$.

When decrypting, ask user for a password $p_1$. Let $c$ be $hash(p_1)$. If $hash(c||s)$ matches any of $hash(b_i||s)$ in the encrypted file, the key is $k=c\oplus (b_i\oplus k)$. Decrypt the rest of the encrypted file with key $k$.

And you can reduce work when encrypting, but increase work when decrypting by letting array $b$ only contain little or no typos. (If your standard of tolerable typos is having 2 or fewer characters wrong, let $b$ be the array of the password with only 1 character wrong, or let $b$ only contain $p$.) When decrypting, enumerate $p_1$ with typos. If the hash of any of them matches any of $hash(b_i||s)$, it is the right password.


Is there a scheme that allows to use RSA based challenge response protocol limited to signing only 8 bytes to create a secure signature of any data?

Yes! Here is one such scheme.

Let $s=\mathcal S(x)$ be what that the question's tiny device produces for 64-bit input $x$, and $\mathcal V(s,x)$ the public verification function for that, which outputs $1$ if $s$ matches $x$, $0$ otherwise. I'll assume this resists existential forgery under adaptive chosen message attack, and we want to extend it to arbitrarily large messages $m$; and we can assume that the question's tiny device is used only as we specify.

Let $P$ be a PRF with 256-bit output, perhaps $P(K,m)=\operatorname{HMAC}_\text{SHA-256}(K,m)$.

The signer willing to sign $m$:

draws a 256-bit true random bitstring $K$ (it shall remain secret until the last step of the signature);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
obtains $s_0=\mathcal S(x_0)$, $s_1=\mathcal S(x_1)$, $s_2=\mathcal S(x_2)$, $s_3=\mathcal S(x_3)$ from the question's tiny device;
outputs $\overline{\mathcal S}(m)$ built as $\overline s=K\|s_0\|s_1\|s_2\|s_3$.

The public verifying function $\overline{\mathcal V}(\overline s,m)$

breaks $\overline s$ into $K$, $s_0$, $s_1$, $s_2$, $s_3$ (or if $\overline s$ does not have the appropriate length, outputs $0$ and terminates);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
outputs $\overline{\mathcal V}(\overline s,m)$ computed as $\mathcal V(s_0,x_0)\cdot\mathcal V(s_1,x_1)\cdot\mathcal V(s_2,x_2)\cdot\mathcal V(s_3,x_3)$.

With $K$ unpredictable to an adversary, it is impossible to obtain $\mathcal S(x)$ for chosen $x$. In 34 years of operation of the question's tiny device at a rate of one evaluation of $\mathcal S$ per second, it will output less than $2^{30}$ values of $s=\mathcal S(x)$. Thus each adversarial attempt at finding suitable $(K,m)$ has odds less than $2^{4(30-64)}=2^{-136}$ to yield $x_0$, $x_1$, $x_2$, $x_3$ all among those for which the corresponding $s$ was produced by the tiny device, which would allow a forgery. Thus if an adversary can make no more than $2^{96}$ evaluations of $P$, residual odds of forgery by that method are less than $2^{-40}$ (the only other methods are exploiting some weakness in the original $\mathcal S$ or $\mathcal V$, or the TRNG generating $K$, or the PRF $P$). A rigorous security proof could be made.

If we want to push things towards shorter signature, we could use three signatures rather than four by making $P$ costly to compute; say, using Scrypt: $P(K,m)=\operatorname{Scrypt}(P=K,S=m,N,r,P,{dkLen}=24)$ with parameters $N,r,P$ optimized to match the computing capabilities of the computer used for signature and yield one second computation. We could also shorten $K$ to $40$ bits (there will be a number of collisions, but it won't really harm much).

Addition: if for some reason a secure TRNG is not available to the signer, we can do with a 32-bit counter $c$, and an extra invocation of $\mathcal S$; we

generate $K$ as $\operatorname{SHA-256}\big(\mathcal S(\text{00000000}_\text{ h}\|c)\big)\;$; or if we know the format of the output of $\mathcal S$ we can isolate some random bits of that, rather than hashing;
use $x'_i$ rather than $x_i$ so that the left half of $x'_i$ is never $0$ (these input values of $\mathcal S$ being reserved for random generation as above); e.g. if the halves of $x_i$ are $l_i$ and $r_i$, we use $x'_i= \begin{cases}x_i=l_i\|r_i&\text{if }l_i\ne0\\(r_i\oplus i)\|r_i&\text{if }l_i=0\text{ and }r_i\ne i\\i\|r_i&\text{if }l_i=0\text{ and }r_i=i\\\end{cases}$
increment $c$ before disclosing $K$ or $\overline{\mathcal V}(\overline s,m)$.


In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

Well, Shamir Secret Sharing works over any finite field $GF(p^m)$, where $p$ is any prime, and $m$ is any integer $m \ge 1$ (N.B. the finite field $GF(p)$ (with $m=1$) is another name for $F_p$).  Any selection of $p$ and $m$ is perfectly secure (assuming we select the polynomial randomly; this is a practical concern, but doesn't really depend on $p$ and $m$), with the only provisos is that the number of shares we can distribute is limited to $p^m-1$, and the value of the shared secret $s$ is in the range $[0, p^m)$.

So, any $p^m$ that is sufficiently large will work and meets the security goals; we then turn to practical considerations.

One strong practical consideration is the size of the shares.  Each share is a value in the range $[0, p^m)$, for $p=2$, this can be conveniently expressed as $m$ bits; for $p>2$, this is a bit larger.  This is not a huge difference; however it is generally viewed the only other practical difference, which is the familiarity we might have with math in $F_p$.

Here is one slightly contrived example to high-light the difference: suppose that we want to share a secret, and we have decided to split up the secret into bytes, and share each byte separately (if each polynomial is selected independently, this is fine).  And, we do not have any need to generate more than 255 shares.  In this scenario, we have two obvious options; we could use $GF(257)$; that makes the math fairly easy; however because each share is a value between 0 and 256, it doesn't fit into a byte; hence the obvious way to encode shares would be twice as long as the original secret.  The other option would be to use $GF(256)$; the math is less obvious (however, with log and antilog tables, it isn't that bad), and each share turns out to be exactly as long as the original secret.


The example there is instructional, not for implementation. Also, if you only want 26 characters plus a few punctuation marks, 5 or 6 bits would be enough.


The polynomial f would be 0xe1, no?

it is $e1 \mathbin \|0^{120}$ i.e. 0xe1000000000000000000000000000000

What would be the value of the element P, if it corresponds to the polynomial α?

it is 2 reversed i.e. 0x40000000000000000000000000000000


Security of HKDF when part of output is exposed

In a secure KDF, the output is indistinguishable from random. In particular, all the output bits are independent, so revealing some of the output doesn't give any indication about the other bits.

Hugo Krawczyk's HKDF definition paper proves that HKDF is a secure KDF under some reasonable assumptions on the underlying hash function which SHA-2 is believed to meet (theorem 4).

With a 128-bit root secret, you only get at most 128-bit protection for anything based on derived material, even if you use a stronger algorithm. That's ok: 128-bit is generally considered unbreakable until at least 2030, and it doesn't get any better than unbreakable.

Allowing clients to pick arbitrary stanza-ids doesn't harm the server directly. It's just passing data through. It means that the server won't be able to use stanza-ids to meter communication, so you'll have to rely on some other means to avoid denial of service attacks (if anybody can submit data to your server, someone can upload terabytes that they won't be using, and you have no way to detect that).

Note that even if the server is unable to make a link between Alice and Bob through pure cryptography, it can make informed guesses by observing who uploads and downloads what data when. It'll take more than this part of the protocol to achieve some measure of anonymity.

I recommend using a proper authenticated encryption mode such as GCM, rather than building your own with AES and HMAC. You have less risk of an implementation mistake that way.


Is this method of deterministically using CBC secure?

Your construction seems quite similar to SIV mode, except that you're using CBC rather than CTR mode for the encryption step and that you're truncating the MAC value to only 32 bits (and re-expanding it by hashing to derive the actual IV).

The only obvious weakness I see in your scheme is the shortness of $y$ and the consequent small IV space.  I'd prefer a 128-bit $y$, but even just 64 or 48 bits would at least be a considerable improvement over 32.
With a 32-bit $y$, not only are collisions likely after about $2^{16}$ encryptions, but with about $2^{32}$ encryption oracle queries an attacker could even arrange for a chosen message prefix to be encrypted with any possible IV, which would allow them to carry out block-by-block dictionary attacks.  Depending on your implementation setting, that many oracle queries may or may not be feasible, but it's a bit too close to a practical attack for me to feel comfortable about.

(Also note that this attack can be easily carried out against multiple target messages simultaneously with little if any extra effort.  In fact, if the attacker only needs to decode one message out of several, having multiple targets will speed it up.)

Other than that, your construction looks OK to me.  Note that you don't necessarily need to use a hash function for the IV expansion step: simply padding $y$ to a full cipher block and applying the block cipher encryption function would do.  This method of deriving CBC IVs from a nonce is even explicitly endorsed by NIST SP 800-38A in appendix C.


Question about Cipher Block Chaining(CBC)

It depends on the position of the two interchanged bits. Assume they have different values, i.e. one is $0$ and the other is $1$. Indeed, if they had the same value, interchanging would not affect plaintext decryption.

Let's say $n$ is the length of every block.

In CBC, every ciphertext block is involved in two plaintext blocks decryption: its own and subsequent one, therefore if one CT is corrupted only two PT will be so.

To move back to your question:

If $b_0$ and $b_1$ fall in the same block

2 plaintext blocks will be corrupted, $n+2$ bits will be corrupted.

If $b_0$ and $b_1$ fall in two adjacent blocks

3 plaintext blocks will be corrupted, $2n+1$ bits affected.

If $b_0$ and $b_1$ fall in two separate blocks

4 plaintext blocks will be corrupted, $2n+2$ bits affected.


Fast irreversible transformation/compression of short messages using a secret

In the first part of this answer, I restrict to reading requirement 2 as "if one pair $(m,r)$ is known…", and assume that $k$ is chosen at random. I entirely disregard security when an adversary knows two distinct pairs $(m,r)$, or when related keys $k$ are used.
The following construction uses the Galois Field $(\mathbb F_{2^{64}},\oplus,\otimes)$, with some irreducible polynomial¹:
$$f:\{0,1\}^{64}\times\{0,1\}^{128}\to\{0,1\}^{64}\\
(m,k)\mapsto (k_1\otimes m)\oplus k_0=r\\
\text{ where }\ k_1\mathbin\|k_0=k\ \text{ and }\ |k_0|=64=|k_1|$$
Given $(m,r)$ and $(m_1,r_1)$ with $m\ne m_1$, there exists a unique² key $k$ with $f(m,k)=r$ and $f(m_1,k)=r_1$. It follows that the construction perfectly meets it's security objective, regardless of the computational power of adversaries.
Note: For any fixed $k$ with $k_1\ne0$, there are no collisions.
Note: We wan restrict to a smaller output by removing any number of bits from the the result. We can correspondingly shorten the key $k$ by removing the bits of $k$ (in $k_0$) that do not influence the result.
Note: Computation of $f$ is simple and efficient on a CPU with built-in support for binary field arithmetic, including most modern x86 CPUs, which have carry-less multiplication. There's little point to this method otherwise.
#include <stdint.h>
#if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later.
#include <immintrin.h>
inline uint64_t f(uint64_t m, const uint64_t k[2]) {
  __m128i u,v;
  u.m128i_u64[0] = k[1];
  u.m128i_u64[1] = 27;                  // X**64 + x**4 + x**3 + x + 1
  v.m128i_u64[0] = m;
  v = _mm_clmulepi64_si128(u, v, 0);    // u.m128i_u64[0] * v.m128i_u64[0]
  u = _mm_clmulepi64_si128(u, v, 17);   // u.m128i_u64[1] * v.m128i_u64[1]
  return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0];
}
#else // no _mm_clmulepi64_si128
#pragma warning(disable : 4146)         // silence silly compiler's warning
uint64_t f2(uint64_t m, const uint64_t k[2]) {
  uint64_t a = k[1], x = (m & -(a & 1)) ^ k[0];
  a = (a >> 1) | (1ull << 63);          // insert sentinel
  do                                    // 63 times
    x ^= (m = (27 & -(m >> 63)) ^ (m + m)) & -(a & 1);
  while ((a >>= 1) != 1);
  return x;
}
#endif

Now I read requirement 2 as "if some number of pairs $(m,r)$ are known…". If said number is large (larger than we are willing to process 64-bit key blocks), we can no longer build a perfectly secure system.
What the question asks can be nicely solved with a 64-bit block cipher, but then there is the question of choosing it. TEA? RC5? Blowfish? Prince? Simon? Speck? One of the lightweight crypto candidates? Any will do. And then we could venture into something custom.

¹ e.g. $x^{64}+x^4+x^3+x+1$, see Joerg Arndt's Binary irreducible polynomials with lowest-most possible set bits. This polynomial happens to also be primitive, but we do not need that property.
² Proof: that $k$ can be found as $k_1\gets(r\oplus r_1)\oslash (m\oplus m_1)$, $k_0\gets(k_1\otimes m)\oplus r$, $k\gets k_1\mathbin\|k_0$.


I think I got it:
I'm going to show that after round i the result will be $\overline{L_i}$ and $\overline{R_i}$ when the input was $\overline{L_{i-1}}$ and $\overline{R_{i-1}}$ and using $\overline k$ as key.

$L_i=R_{i-1} \implies \overline{L_i} = \overline{R_{i-1}}$

$\overline{R_i} = \overline{L_{i-1}} \oplus f(\overline{R_{i-1}}, \overline{k_i}) = \overline{L_{i-1}} \oplus f(R_{i-1}, {k_i}) = \overline{L_{i-1} \oplus f(R_{i-1}, k_i)}$.

$f(\overline R, \overline k)=f(R, k)$ because within the fuction the complement of expansion(R) and $\overline k$ are xored which eleminates the complement.

That way round the final result will be $\overline c$ when using $\overline m$ as input and $\overline k$ as key. The initial permutation does not change that.


Secure multiparty computation of conjunction

They could use 1 out of 2 oblivious transfer. Alice offers the messages $0$ and $a$ and Bob uses $b$ as his choice bit (I.e., choosing the first message if $b = 0$ and the second if $b = 1$.). It should be easy to see that Bob now receives $a \land b$ (if in doubt write down the truth-table). Now Bob can send the result to Alice (or they can do the protocol in reverse).

Of course this assumes passive (semi-honest) adversaries. Also, note that if one party has input 1, then $a \land b$ always reveals the other party's input (this is regardless of the protocol).

Btw, this is known as the "Dating Problem", because it can phrased as follows: Alice and Bob does not want to openly tell each other whether or not they want to go on a date with the other. They fear embarrassment if the other party rejects them. Using the above protocol they can learn if both want to go on a date but will not learn if only the other party wants to go on the date. Essentially what Tinder solves for thousands of people every day! (Although they do it in a totally non-cryptographic way AFAIK)


Private Information Retrieval with no server computations

Not when it comes to PIR. However, depending on your use case, have you considered using Oblivious RAM?
From Mayberry et al. (2013):

There are traditionally two ways to hide a user’s access pattern (given only a single server/cloud): Oblivious RAM (ORAM) and Private Information Retrieval (PIR). The traditional approach taken by ORAM is to arrange the data in such a way that the user never touches the same piece twice, without an intermediate “shuffle” which erases the correlation between block locations. [...]
Private Information Retrieval, in contrast with ORAM, hides the target of each individual query, independent of all previous queries. This can be accomplished by using a homomorphic encryption which the server uses to operate over the entire database, selecting out the block of data that the user has requested. The user generates encrypted requests and sends them to the server. Since PIR does not try to hide a sequence of accesses, but each access individually, the amortized cost is equal to the worst-case cost. Unfortunately, the requirement that the server computes over the entire database for each query is often impractical, especially for large databases.

So, for ORAM you generally have a single client, which holds some client storage. Of course it is possible to have multiple clients, but then they have to download/re-upload the client state before and after transferring blocks. One construction is Recursive Path ORAM, which for storing $N$ blocks has $O(\log N) \cdot \omega(1)$ blocks of client storage and $O(\log N)$ blocks of bandwidth, where we assume blocks are “moderately sized”, i.e. of size $\Omega(\log^2 N)$.


How is the key shared in symmetric key cryptography?

Handing keys, in general, is known as key management.

Symmetric keys should be kept secret from other parties than the participants in the scheme. The term "secret key" is often used as a synonym for the symmetric key. The private keys for asymmetric schemes are not shared, but are of course also kept secret, as privacy implies secrecy.

The establishment of symmetric keys between parties can be performed in several ways:

(Authenticated) Key Agreement (KA)
Sending of an (authenticated) encrypted key, also known as key wrapping
Derivation from a base key using a Key Derivation Function (KDF), using other data as input, for instance, a unique number. If the derivation is performed so the resulting keys can be used in different schemes it is often called key diversification. If keys are derived in an iteration we talk about a key ratchet.
Any kind of "out of band" procedure (after random key generation),

by a previous telephone call
sending a letter
meeting in a pub (handing over a USB stick or other data carrier)

Creating a key from key parts held by different persons (key sharing schemes)
Quantum key distribution

There are other methods for establishing symmetric keys, but these are some of the most commonly used ones. The security of these schemes depends of course on the implementation.


Key encapsulation or key wrapping is the encryption of a key with another key. There may be a symmetric key or asymmetric key pair that encapsulates the key destined for transportation; this key can then be called a key transport key.

Key transportation is simply the secure transportation of a key. For public keys you'd expect integrity and authenticity - so that the receiver can trust the public key to have been sent by the right entity. Secret keys require confidentiality as well - which is why they are commonly encapsulated. Private keys would also require confidentiality of course, but generally you should not transport private keys at all - they're private: not to be shared.

Commonly I'd expect encapsulation / wrapping to be used for secret keys for secure transport. It is however perfectly possible to secure them otherwise (diplomatic post with a USB-thumbstick for instance).

Key encapsulation & transport is just one way of establishing keys between two or multiple parties. Another way would be (authenticated) key agreement, key sharing schemes and so on.


Are there any special points on an elliptic curve which would weaken security?

Let's first consider your proposed secp256k1 curve. The order of the curve is prime, which means any (valid) point on the curve will generate the whole curve; for any choice of your base point $G$ except for the point at infinite $\mathcal O$, there are integers $r$ such that $[r]G$ reaches the whole curve. In other words, the only sub groups are the whole curve and the trivial group $\{\mathcal O\}$.

This is however is not true for all elliptic curves.  In fact, many have a composite structure (order $n=r\cdot h$), consisting of a large subgroup of prime order $r$ and a "cofactor" $h$. This property can lead to a subgroup confinement attack.  For more information about the cofactor, see this excellent answer. In order to avoid this, care has to be taken when these kinds of curves are used in protocols.

This is (of course) not the only attack we can think about, but it's the most evident from wording of your question. SafeCurves, a webpage by people with a lot more understanding of elliptic curve cryptography than me, lists up many curves with their flaws. Curves like secp256k1 may be safe from subgroup confinement, but have other flaws w.r.t. timing and side channels.


Information theoretical lower limit on the size of public and private keys

The private key can be reduced to $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance to brute force of $O(2^k)$ steps (on a conventional, non-quantum computer). Proof sketch: replace the RNG used for key generation by a PRNG with at least $k$-bit security and seeded with a $k$-bit key. And that bound can't be much improved since there must be at least $O(2^k)$ private keys to avoid a brute force search. Note: that does not apply to already generated private keys.

On a quantum computer, that goes reducing private key to $2k$-bit for $O(2^k)$-something quantum resistance. Argument: a symmetric cryptosystem secure to $O(4^k)$ classical steps is widely believed to require at least $O(2^k)$-something (time or/and qubits) on a quantum computer.

The public key must be at least about $k$-bit in any asymmetric cryptosystem (encryption or signature) with a resistance $O(2^k)$ to brute force (on a conventional, non-quantum computer). Argument: we could use the above compressed form of the private key, and there can't be much less public keys than there are private keys, since that would allow finding by enumeration with effort $O(2^k)$ a private key matching a given public key.

But there is doubt that a $k$-bit public key is achievable. All known asymmetric cryptosystems actually have their public key $2k$-bit or more, for security as above. $2k$-bit is achieved by schemes based on the Discrete Logarithm in an Elliptic Curve group, and that's a plausible lower bound for the public key size. I vaguely remember having seen it conjectured at sci.crypt(.fr?), but without a convincing argument; and I fail to dig it up.


After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

To answer your question "After implementing a novel encryption algorithm, how would one go about analyzing its security", well, the easy answer is "no, it's not secure".  The reason I can confidently give that answer is that you're a newbee, and newbee ciphers are never secure (unless they are massively overcomplicated; it doesn't sound like that's the case).  A newbee is about as likely to create a secure cipher as a blind man would be to paint a good piece of art; neither has any reference as to what works and what doesn't.

However, I assume you are looking for a more detailed answer than that.  Well, that gets tough for a newbee.  There are no automated tools that can validate an algorithm as "secure" (as secure means that no one can come up with a creative method to attack it, and automated tooling has difficulties with "creative").

So, you would need to have a human look at the cipher.  You could try to get an expert cryptographer to look at it, however (and you might find this shocking) there are no groups of expert cryptographers that are eager to attack ciphers from newbees.  And, even if you do get someone to look at it, you'll run into the next difficulty - they'll point out exactly how to break it; you'll tweak the cipher to stop that exact attack, and you'll have no idea whether tweaked cipher is any stronger than the original (except for that exact attack); indeed, the tweaked cipher could easily end up being weaker.

The alternative is to invest the time to become an expert yourself; the way to do that is to break ciphers yourself.  Yes, that's quite a commitment (becoming an expert in any subject is pretty much by definition hard work); but if you are serious about designing ciphers, that's what you have to do.  You might start with Stanford's course (note: I haven't gone through it myself); Schneier has an intro-to-cryptanalysis course here; or you might want to start by attacking your own ciphers.

The last isn't as silly as it sounds; here's a few suggestions:

Can you attack a 'reduced strength' version (say, with a reduced 'byte size')?
Suppose that the attacker can encrypt messages of his choosing (which is actually a standard cryptographic assumption)?  How can he use that?  For example, for your first method, suppose he asks for the encryption of thousands of repetitions of the same character?  What can he deduce from the ciphertext?
Once you can figure out how to break it with chosen plaintext, how can he attack it if he knows some of the plaintext (but obviously not all)?  How can he attack it if he doesn't know any of the plaintext, but he does know that it is, say, English-ASCII?

To give you a target, I suspect that against your first method, I could decrypt the encryption of perhaps a 10k English-ASCII message, or a 200 byte English-UCS-2 message.  And, no, I won't tell you how; that's for you to discover (hint: why do I need so much less text with UCS-2?)


If plaintext is random, how does it affect my choice of encryption algorithm?

Generally, no, but it depends somewhat on what you want to do with your random file.

For example, let's say you want to send the random file to your friend for use as a one-time pad.  Since you're worried that someone might be intercepting messages between you and your friend, you decide to encrypt the pad with a simple Vigenère cipher, like this:

$$P'_i = (P_i + K_{i \,{\bmod}\, L}) \bmod N$$

where $P$ is the original one-time pad, $P'$ is the encrypted pad, $K$ is a key (of length $L$) known to you and your friend, and $N$ is the size of the alphabet.

However, let's say that an adversary does intercept the encrypted pad $P'$ and saves a copy of it.  When your friend uses the decrypted one-time pad $P$ to send you a message $M$ encrypted as

$$M'_i = (M_i + P_i) \bmod N$$

the adversary intercepts that too, and uses the encrypted pad $P'$ they captured to decrypt it:

$$\begin{aligned}
M''_i &= (M'_i - P'_i) \bmod N \\
&= (M_i + P_i - P_i - K_{i \,{\bmod}\, L}) \bmod N \\
&= (M_i - K_{i \,{\bmod}\, L}) \bmod N
\end{aligned}$$

Now they have a string $M''$ which is simply $M$ encrypted with the same simple Vigenère cipher that you used to encrypt $P$ into $P'$ (except that the key has been negated, but that's a minor detail), and they can use standard Vigenère cipher breaking techniques to try and recover $M$ fairly easily.


Does the Initialization Vector in DES have to be 8 bytes long?

The IV is part of the block cipher mode of operation, not of the block cipher itself. The block cipher simply doesn't have any input for an IV, it just takes an input block and produces an output block using a key. So you cannot implement an IV for DES itself.

The block size is however usually of influence to the mode of operation. Even then, the IV may still be different from the block size for some modes. To make it a bit more complex, some modes of operation such as CTR mode and GCM mode (for 128 bit block ciphers such as AES) may have different options to implement an IV or nonce.

The DES block size is always 64 bits, regardless of the key size, just like 128 bits is always the block size of AES. The key size is not (necessarily) of any influence to the block size, although it may be advantageous for the key size to be a multiple of the block size in case keys need to be encrypted by other keys (wrapping a key by another "wrapping" key).

For CBC mode, which is often explained as one of the first modes to starting cryptographers, the IV needs to be the full block size. Furthermore, for CBC the IV needs to be indistinguishable from random to any adversary. That means that the IV is always set to 8 bytes or 64 bits.

Note that DES itself only supports 64 bit keys, of which 8 bits are parity bits, so an effective key size of 56 bits. Triple DES or DES-EDE may use two keys. It then uses key A for the first encryption, key B for DES in decryption mode and keyA again for encryption, so an ABA-key.

However, as these block encrypts / decrypts are simply stacked on top of each other, the block size stays the same: 64 bits. Therefore, for CBC, the IV does need to be 64 bits / 8 bytes as well.


Does QUIC use a 96-bit MAC tag? If so, what are the implications?

One can argue about whether security for adversaries running in time $2^{96}$ is feasible or not, and the current standard is to require 128-bit security (or at least 112). However, an attack requiring sending in the range of $2^{90}$ messages to attempt to forge is way beyond feasible. The success probability of an attacker shouldn't exceed something reasonable, but what is reasonable is also subjective. NIST recommends that for block cipher modes of operation, the probability of a breach shouldn't exceed $2^{-32}$. For that reason, with a random IV, you can only use CTR or GCM to encrypt $2^{32}$ different messages (since the IV is of length 96 and you have a birthday problem). For MAC tags, taking 96 bits is more than enough...


Interesting malleability property of Goldwasser-Micali PKC

This property is a consequence of the homeomorphic property of GM (plus the fact you don't need to know $r$ to encrypt a 0).

In GM, given $Encrypt(A)$ and $Encrypt(B)$, you can compute $Encrypt(A \oplus B)$.  This is what the above observation is doing; generating a random encryption of 0, and then computing $Encrypt( A \oplus 0 )$ (which, of course, stands for the same plaintext as did the original $Encrypt(A)$.  Because someone without the private key couldn't tell that your random $Encrypt(0)$ held a 0 or not, they also can't tell whether your new ciphertext has the same plaintext as same as the old.

You can do the same with Pallier; you can encrypt a 0, and then compute $Encrypt(A + 0)$; again, no one without the private key can tell whether the new ciphertext conceals the same value as the old.


How to generate own secure elliptic curves?

Of course there are others.  Of interest might be the paper 'Efficient ephemeral elliptic curve cryptographic keys' by Mieli and Lenstra, which claims to generate fresh Elliptic Curves sufficiently quickly that they can be created on the fly for a single ECDH exchange, and then discarded.


Establish more secure symmetric crypto system given A and B have small initial secret

My understanding is $x$ or $g^{atx} \bmod p$ or $g^{btx} \bmod p$ would be expensive to find for Trudy, thus Alice and Bob retain confidentiality.

Not really.  Trudy knows $g^a$ (Alice sent that) and $t$ (Trudy picked that); let us assume that Alice uses the value $g^{atx} \bmod p$ for something, such as deriving symmetric keys, and then uses that to encrypt a message.  What Trudy could do it compute $(g^a)^{tx} \bmod p$, for all possible values of $x$, and derive keys from all of them; that's 16384 possible keys.  Trudy can then try to decrypt Alice's message using each key; the one that works will tell her the correct value of $x$ (and then she can either continue with a MITM attack, or impersonate Bob).

There are protocols that don't have this weakness, examples include EKE and SRP; these don't prevent Trudy from taking a random guess of $x$, attempting a MITM attack (and learning whether that was the $x$ that Alice and Bob shared); what they do is make sure that Trudy can't do any better; to test 1000 possible $x$ values, she'll need to perform the MITM attack 1000 times.


Application level encryption and key renewal

DEK (data encryption key): The key that encrypts the actual content.
The DEK gets changed less often than the KEK (see below).

KEK (key encryption key): The key that encrypts the DEK.
The KEK gets changed ("rotated") at regular intervals according to best practices and company security policies.

As the volume of content grows, the more arduous it will be to rotate the DEK. You still might actually rotate a DEK from time to time, but doing so would mean re-encrypting all of your content with a new key.

It is much easier to simply use a new key to re-encrypt the DEK, rather than re-encrypting the content that was encrypted by the DEK, since encryption keys are tiny compared to the content that they encrypt.

You should rotate the KEK as you go, over time, whenever its expiration date passes, or incidentally, such as in the event of a breach or a suspected breach.


The reason I am asking about the RSA private key is the HMAC key needs to be stored so that the HMAC can be validated by the server on future requests. An RSA private key is an easy to manage, persistent value.

You seem to be under the misguided and mistaken belief that an RSA key is somehow easier to manage and persist than a symmetric key.

  I am wondering if there are any good reasons not to use an RSA Private Key for this purpose.

RSA private keys were not designed or intended for this purpose, and there seems to be no legitimate reason why you would actually want to do it. Use primitives for the purposes they were designed. Don't try to be clever. And don't invent your own crypto.


How does AES introduce confusion and diffusion?

Put simply:

The add key layer ensures the encryption function is only computable by someone who knows the key

Adds some confusion because the key is (psuedo) random

The subBytes s-box layer creates confusion

each symbol is mapped to another symbol in a way that impedes common methods of cryptanalysis (high resistance to linear and differential cryptanalysis)

The shiftRows and mixColumns operations combine to provide full diffusion over the course of 2 rounds

The state is a 4x4 grid of 8-bit words
mixColumns operates vertically on each 4 word/32-bit column

One bits difference in any word in the input column will spread to multiple places in multiple words in the output column

shiftRows ensures that over the course of successive rounds different words are grouped up as inputs to the mixColumn function
There's a good answer that is slightly more specific here

For more information, consult the book on the design of Rijndael, or maybe try one of the handy diagrams or animations that exist.


Can quantum computers put computer security in jeopardy?

can they (quantum computers) do such complicated computing (cryptanalysis)?

Not currently. Current quantum computers (including the adiabatic variants specialized in quantum annealing) do not perform anything useful for cryptanalysis. In the future: we don't know.

  Is it possible quantum computers put the computer security in jeopardy?

It is reasonable to worry for the long term. There's therefore a lot of activity to be prepared for quantum computers useful for cryptanalysis. The quasi consensus is that 256-bit symmetric crypto (AES-256, SHA-512, SHA3-512 and the like) will remain safe in the foreseeable future. Most currently used asymmetric/public-key crypto (RSA and others based on factorization; DSA, DH, Schnorr signature, ECDSA, EdDSA, ECDH and others based on discrete logarithm) may not, especially for the smallest key sizes currently considered safe. But practical quantum-safe asymmetric cryptography seems feasible, and is in the works. There's preliminary standardization effort at NIST.

This related question asks how to predict when and if quantum cryptopocalypse is coming.


Key escrow on indistinguishability games

Not always, it depends on the particular encryption scheme.  Strictly speaking, the proofs only say that breaking indistinguishability is equivalent to breaking the hardness assumption they are based on.  There are some cryptosystems, like Rabin's, where the security of the key is equivalent to the security of the ciphertexts, i.e. factoring <=> key recovery <=> message decryption.  However, others like RSA do not have this property.  For RSA, factoring <=> key recovery => message decryption, but it may be possible to decrypt messages without being able to factor.  That is why it is not said to be based on the hardness of factoring, but of the "RSA assumption".  In this situation, the security of the key is greater than or equal to that of the messages.

Long story short, the answer is generally no, but in some particular cases yes.


While encrypting what can happen between words

Keys are not known, algorithm is not known.

Wrong initial assumption. The only secret must be the key by Kerckhoffs's_principle.

  but in order to make it harder I could add consecutive letters to consecutive words

and

  another example would be encryption using Caesar...

This is not new, this is nearly 600 years old, it is commonly called Vigenère Cipher and it is super weak with nowadays assumption such as Chosen Plaintext Attacks.

  Are there any known and used methods that happen every word or every sentence?

Yes, for example Cipher Block Chaining. Note that sentences are not composed of words anymore but seen a bit-string that you are splitting into blocks (sort of words) of the same length.


Verify membership of an item within a set while obscuring the number of elements in the set?

You don't mention multiple parties at all, so the question is: Who knows what? And who must not know the number of elements in the set?

And then, the most simple solution actually doesn't need cryptography:

Let's assume Bob has the set of elements and Alice wants to know if some element $x$ is in the set.
Alice sends $x$ to Bob.
Bob answers with yes or no.

Obviously, this doesn't hide $x$ from Bob. If we use some hash value $h(x)$ instead (Bob hashes all elements, too, the rest is the same), then given enough entropy in $x$ Bob might not be able to find $x$ - if it isn't in the set (if it is, he also knows the preimage as you can assume Bob didn't delete the original elements).

Depending on what kind of properties you want, there are various constructions. For example set membership proofs, where Bob actually has to prove that the element is in the set and a simple yes or no isn't enough. If you want to achieve that Bob doesn't even know if the answer is yes or no, this might also be possible - based on some sort of oblivious transfer.

Another interesting construction, which might suit your needs, might be  accumulators - and that's my best guess right now: Bob gives the accumulator to Alice, which doesn't expose the elements or their number on its own. But he is able to prove that some element is actually contained in the set represented by the accumulator.