No. Usually the Kerckhoff principle is considered. That means that the security of a cipher should rely on the key alone. The algorithm itself should be considered known. You could think of the algorithm as a single key that anybody that knows the algorithm possesses. Such a key should not be considered secure.

There is no generic way of testing the security of an unknown cipher, even if the plaintext and ciphertext are known. A block cipher is supposed to be a PRP - a pseudo random permutation - where the specific permutation is chosen using the key. Of course you could find relationships between the plaintext and the ciphertext for very weak ciphers. Usually attacks are on specific design or implementation details of the cipher, not directly on the ciphertext.

Basically to test the cipher you should create a paper formally describing it. The paper should indicate why you think the cipher is secure. You'd then have to find experts to take a look at it and possibly attack it. The best way to do that is to enter it into a competition.

If you're just experimenting, try to study attacks on other ciphers first. Then try and perform similar attacks on both your and other ciphers. See why other ciphers are broken.

If you subject your cipher to a competition prepare to be tossed out in the first round. Remember: the old ciphers of pioneers such as Bruce Schneier and Ron Rivest would be tossed out in the first round as well.


I'm just reading the book Advances in Elliptic Curve Cryptography, and Chapter II (by Dan Brown) is about provable security of ECDSA.

It lists some necessary conditions for the ECDSA components (group, conversion function, RNG, hash function), each with an associated forgery. For example, the group has to be resistant against discrete logarithms, as well as semi-logarithms.

With some additional conditions, we also get stronger unforgeability results, e.g. modeling the hash function as a random oracle means that semi-logarithm resistance also implies active existential unforgeability (i.e. the strongest result). Alternatively, modeling the group as an ideal group permits using only the necessary conditions on the hash function.

The book also contains sketches for the proofs.

Of course, this says nothing about whether a specific elliptic curve or class of curves really has the necessary semi-logarithm resistance, which seems to be what you really need.


$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$
Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ relation $\rel$.
Now assume that every statement in $\lang$ has a short witness, i.e. a witness of constant (as in your question) or at most logarithmic length. I.e. it holds that
$$
  \forall\,x \in \lang\ \exists\,w\in\bin^{\log(|x|) }. (x,w)\in\rel
$$

By definition of an $\NP$ language, it is possible to check whether $(x,w)\in\rel$ in polynomial time for any pair $(x,w)$. Say it takes at most time $p(|x|)$ to decide. It thus follows that¹ we can give a polynomial time algorithm for deciding $\lang$ as follows:
\begin{align}
&\underline{\mathcal{A}(x)\hspace{6em}}\\
&\text{for } w\in\bin^{\log(|x|)}\\
&\quad \text{if } (x,w)\in\rel \\
&\quad\quad \text{return } 1\\
&\text{return } 0
\end{align}

It is easy to see that this algorithm is deterministic, always decides correctly and runs in time at most $$2^{log(|x|)}\cdot p(|x|) = |x|\cdot p(|x|)$$ and therefore in polynomial time. We can thus conclude that any such language is in fact in $\mathsf{P}$.

And for any language there exists a trivial proof system, that consists of just sending nothing. The verifier can simply verify the statement themselves. Note that this proof system is trivially sound (as the prover cannot influence the verifier's decision at all), as well as trivially zero knowledge, since the simulator just needs to "simulate" the empty interaction.

Now you specifically asked about proofs of knowledge. It is easy to see that this is in fact also formally fulfilled here, as the algorithm $\mathcal{A}$ needs to be modified only slightly to extract $w$ from $x$ alone.

\begin{align}
&\underline{\mathsf{Ext}(x)\hspace{6em}}\\
&\text{for } w\in\bin^{\log(|x|)}\\
&\quad \text{if } (x,w)\in\rel \\
&\quad\quad \text{return } w\\
&\text{return } \bot
\end{align}

¹As you in fact observed correctly.


An RSA signature is a sequence of bytes of the same size of the modulus. If the key uses a 1024-bit modulus $n$, then the signature value is, numerically, an integer in the $1..n-1$ range, and the PKCS#1 standard specifies that this integer should be encoded as a sequence of bytes of the same length as would be needed to encode the modulus, i.e. 128 bytes for a 1024-bit modulus (big-endian unsigned convention).

The signature process looks like this:

The message to be signed $m$ is hashed with hash value $h$, yielding $h(m)$, which is a sequence of bytes (say, 32 bytes if $h$ is SHA-256).
The hash value is padded: a byte sequence is assembled, consisting of, in that order: a byte of value 0x00, a byte of value 0x01, some bytes of value 0xFF, a byte of value 0x00, a fixed header sequence H, and then $h(m)$. The header sequence H identifies the hash function (strictly speaking, there are for each hash function two possible header values, and I have encountered both). The number of 0xFF bytes is adjusted so that the total sequence length is exactly equal to the encoding length of the modulus (i.e. 128 bytes for a 1024-bit modulus).
The padded value is then interpreted as an integer $x$, by decoding it with the big-endian convention. Due to the sequence size and the fact that the sequence begins with a 0x00, the value $x$ is necessarily in the $1..n-1$ range.
The value $x$ is raised to the power $d$ (private exponent) modulo $n$, yielding $s = x^d \pmod n$.
The $s$ value is encoded into a sequence of the same length as $n$; that's the signature.

To verify, the signature is decoded back into the integer $s$, then $x$ is recovered with $x = s^e \pmod n$, and encoded back. The verifier then checks that the padding as explained above has the proper format, and that it ends with $h(m)$ for the message $m$.

All of the above is the "v1.5" PKCS#1 padding. The standard also defines a newer one, called "PSS", which is a bit more complex, but allows for some kinds of security proofs.


Is there an encryption algorithm, which is a magnitude faster than AES (with weaker guarantees)?

A classical table-based AES implementation would achieve about 160 MB/s on my current computer (a fairly recent MacBook Pro). However, one can do better; of course there are the AES-NI instructions, that easily bump up speed on that machine to the 5 GB/s mark (with a parallel mode such as AES-CTR; AES-CBC encryption is much slower). But even without these instructions, the Käsper-Schwabe implementation of AES-CTR would offer more than 400 MB/s, a substantial improvement.

Looking outside of AES, there is ChaCha20, as specified in RFC 7539. Using my own implementations, the purely generic, 32-bit plain C code (chacha20_ct) encrypts or decrypts data at 385 MB/s on my laptop; the SSE2-enhanced implementation (chacha20_sse2) offers a 584 MB/s.

Generally speaking, block ciphers like AES are versatile primitives, and it can be argued that, by forfeiting versatility and concentrating on the encryption/decryption role, better performance may be achieved. This is what stream ciphers like ChaCha20 are about.

About ten years ago, there was the eSTREAM project which resulted in a portfolio of stream ciphers. On my laptop, SOSEMANUK achieves about 1.64 GB/s, which is not bad for a design from ten years ago. Notably, it is 10 times faster than the table-based AES. (I wrote part of the code; I don't know who packaged it as a Zip archive with modified file names that break compilation.)

Among more modern designs, one may cite NORX. I encountered an implementation on small ARM systems that was consistently trouncing ChaCha20. I suppose it would also clear the 1 GB/s mark on a modern PC.

Summary: 1 GB/s is actually highly feasible with existing algorithms, on standard hardware, without using the AES instructions, and without sacrificing security: all of the above are currently unbroken, despite extensive exposure to vindictive cryptographers.

Of course, excluding the AES-NI instructions is rather artificial: it makes relatively little sense to make benchmarks on a modern CPU without using the features of that CPU. Performance on smaller, embedded systems without an hardware AES implementation may be more relevant.


Short answer: NO

especially for all $m$

as a secure hash function generate significant different output for even a small change in $m$. (see Random Oracle Model for further references).

therefore
\begin{equation}
m \neq E(m)
\end{equation}
\begin{equation}
H(m) \neq H(E(m))
\end{equation}

now a hash function is not same as encryption function.

therefore

\begin{equation}
m \neq H(m)
\end{equation}
\begin{equation}
E(m) \neq E(H(m))
\end{equation}

now from above equations, you can see it is only possible if $H() = E()$ but it is not plausible as

Hash function must be irreversible and producing a fixed length output where

Encryption function must be reversible and variable length output.

so it is not possible to exist even a single function obeying such criteria.


This is only a partial answer to the question, but still: The S-boxes where chosen to maximize confusion and to create an avalanche of change. For example, there were specific properties chosen to make the S-boxes resistant against differential cryptanalysis, by making sure that small differences between different inputs lead to larger differences in the outputs (i.e. the Hamming weight of the difference increases).  IIRC, the more straight-forward criteria about differentials include:

$HammingWeight(input_1 \oplus input_2) = 1 \Longrightarrow HammingWeight(output_1 \oplus output_2) \geq 2$
for any input difference $a$ and output difference $b$: $input_1 \oplus input_2 = a \Longrightarrow Probability(output_1 \oplus output_2 = b) \leq \frac{1}{4}$

Also note that the S-box design interacts with the design of the permutation P.  P makes sure that changes are distributed across all the S-boxes.

Some of the properties were chosen to resist specific attacks.  For example, the DES S-boxes could have been made more resistant against linear cryptanalysis, but they were not, because the designers were not aware of linear cryptanalysis at the time.

A paper describing the design rationale of the DES S-boxes was published in 1994.


What is Homomorphic encryption evaluation key

In short

Public key is used to encrypt, private key is used to decrypt, and evaluation key is used to perform homomorphic operations (usually, homomorphic product or, the somehow equivalent operation, a logic AND gate).

In detail

Public and private keys in homomorphic encryption (HE) schemes are just the same as in other types of schemes.

The evaluation key ($evk$) is also public, it is typically generated using the private key, and it is used to control the noise growth or the ciphertext expansion during homomorphic evaluation.

Some schemes have a "Key-switching" key instead of the evaluation key, but they are more or less the same. For instance, in the description of FV and YASHE, you can see that to perform a homomorphic product, one first multiplies the ciphertexts, $\tilde{c}_{mult} := c_1 \otimes c_2$, then uses this "extra public key" to adjust $\tilde{c}_{mult}$, that is, to get a ciphertext $c_{mult}$ with the correct dimension and that can be decrypted using the original secret key.

So, in general, this is how you use $evk$: you perform a homomorphic operation that introduces a lot of noise or that generates a ciphertext in higher dimension, then you perform an extra operation using $evk$ to "correct" that ciphertext.

As an extra example, take a look to FHEW Library Interface and you will see that the NAND gate uses $evk$, but the NOT gate does not.

Further observations

If you bootstrap, then you typically need $evk$, since you need it to perform homomorphic evaluations in general and bootstrapping is the homomorphic evaluation of the decryption circuit.
In principle, there is no special relation between multi-key HE schemes and evaluation keys (FHEW is not multi-key and also has an $evk$).
Even if the scheme is symmetric (i.e., does not have a public encryption key), it may still have evaluation key.
Some schemes do not have evaluation key (e.g., GSW).


Hashing - Digital Signing and Trivial Stretching

Response to Question 2 :

algorithm 1 : change the algorithm into this, it will be easier to explain

hash1 = sha512(password + salt1);
hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash1); // <-- Do NOT do this!
    hash2 = sha512(hash2); // <-- Do NOT do this!
}

For 2 different inputs hash1 and hash2, if there is a collision on iteration 10 then the next 990 iterations will crunch the very same work and output the same hash1 and hash2.

The more you hash, the more intermediate collisions you could create at iteration 12, 15, 20, 100, 101, 314 .... Every additional iteration increase the probability of collision.

if Bob run this code (half of the previous loop)

hash1 = sha512(password + salt1);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash1); // <-- Do NOT do this!
}

And if Alice run this code (half of the previous loop)

hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash2 = sha512(hash2); // <-- Do NOT do this!
}

As of previous comment, security decreases, because Bob and Alice could impersonate each other because of the increased collision probability. When the algorithms complete

P(hash1 == hash2) > 1000 * P(sha512(password + salt2) == sha512(password + salt1) )

If there are more than Bob And Alice, John, Joe, Jack and Jeremy are running this loop, then the probability of collision is still increased by devastating effects of the "birthday paradox".

algorithm 2: something is different on each iteration, that is the big difference.

hash1 = sha512(password + salt1);
hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
    hash1 = sha512(hash + password + salt1);
    hash2 = sha512(hash + password + salt2);
}

If there is a collision at iteration i, then the next iteration i+1 is more than likely to produce a non-collision. Every iteration has provably the very low collision probabilities of sha512 when provided with different input. Split the algorithm between Bob and Alice, when the algorithm completes

P(hash1 == hash2) == P( sha512(password + salt2) == sha512(password + salt1) )

Note : It is possible to have different values of salt at each iteration, as suggested by the referenced page.


Can you please give me some direction for such proof?

You're looking for a proof that the RSA problem is hard?  No such proof is known (even in the specific case of $e=3$).  Furthermore, there is no known reduction to a 'more fundamental' problem, such as factorization or discrete log.

The closest we can get is a proof that if you can find the 'decryption exponent', that is, the value $d$ such that $y^d \equiv x \pmod N$, you can factor $N$ (and using the value $d$ is how the holder of the RSA private key recovers $x$ in practice).  However, this does not show that there isn't another way (that's easier than factoring) to recover $x$.

The only 'proof' we have that the RSA problem is hard is 'lots of smart people have looked for a way to solve it, and they haven't found one'


How you find the unpadded short plaintext using RSA?

As kelalaka hinted, the issue with particularly short plaintext in unpadded RSA is that it is subject to brute force via chosen plaintext attack.

For each plaintext $m$ in the short space you suspect the enciphered plaintext to originate from calculate $c = m^e \text{ mod } n$ where $e$ is the public encryption exponent and $n$ is the public modulus. Then compare $c$ to the ciphertext for which you are trying to find the plaintext. If identical, the message $m$ is the same as the padded short plaintext in question. Because RSA is deterministic, identical plaintexts produce identical ciphertexts.


How does redundancy in a file effects performance and security of encryption?

Pretty much all modern encryption systems (including AES, in any standard mode) are data-agnostic: they are designed to encrypt any byte (or bit) stream regardless of its content, and their performance does not depend in any way on what the stream contains.

Indeed, if this were not the case, that would open the encryption scheme to timing attacks — if the performance of the encryption system depended on the data being encrypted, an attacker would be able to learn something about the data by timing how long it takes to encrypt it.  Modern encryption systems are designed to avoid such attacks, primarily by ensuring that their performance is constant regardless of the data being encrypted or the key used.

(That said, ensuring that the execution time of an encryption routine remains perfectly constant can be difficult, and it's not at all uncommon for timing attacks to be discovered against insufficiently careful implementations of even standard crypto algorithms.  This is one reason why writing secure low-level crypto code requires a lot of skill and attention to detail.  However, even when such vulnerabilities exist, they're typically a lot more subtle than what you describe.)

As for security, modern encryption schemes are also supposed to be secure regardless of the data being encrypted.  Indeed, the minimum level of security typically expected of a secure encryption scheme is ciphertext indistinguishability under a chosen-plaintext attack (IND-CPA), which requires that, even if the attacker gets to choose the messages being encrypted, he still cannot distinguish the encrypted output from a random bitstring (of equal length).

That said, while encryption systems in current use (such as AES, in any secure mode) are assumed to meet this level of security, and while no-one currently knows (or at least has published) any attacks that would violate that claim, no-one has also ever managed to unconditionally prove that any encryption scheme actually meets that standard, and sometimes new attacks do get discovered against systems previously thought to be secure.  If an encryption system is sufficiently badly broken, it is possible that the nature of the data being encrypted might affect the ability of an attacker to exploit the system's weakness.  That said, any system for which that would be the case would be regarded as hopelessly insecure and unsuitable for use today.


PRF and deterministic polytime function implie PRG

For your points:

Your discussion of expansion is correct. In particular, you can show that $\ell(r) = mr \geq 2r > r$, which is essentially what you explain.

You can write a formal proof that $F_C$ is poly-time in essentially the same way you would show any algorithm is poly-time. In this case, it is quite obvious that the result is poly-time, so if it feels obvious to you that this is the case that should be normal. That being said, there are some subtleties --- concatenating two things with polynomially-sized representations is poly-time, but what if you have exponentially many things? This would no longer be poly-time. Can you be sure the algorithm is still poly-time in light of this (and if so, why?)

You have a definition of pseudorandomness for PRGs (definition 3.14), which likely want to relate to a definition of pseudorandomness for partial function (in particular $F$). I would suggest finding the particular definition you're working with first. Your proof strategy should be reduction to $F$'s pseudorandomness -- some statement along the lines of "Any distinguisher for $F_C$ implies a distinguisher for $F$, which as $F$ is pseudorandom does not exist, so the distinguisher for $F_C$ cannot exist as well". This is the "general template" of proofs by reduction within cryptography, so you would do well to internalize this "strategy".


Indeed hashing is used to ensure integrity, but not this way.

What you have in mind it seems is sending (msg, Hash(msg)). Indeed this is not secure because of the attack you describe.

The first step starts with something you say by yourself:

  hashing algorithms are universal algorithms

The name is not univesal but public, it means anyone knows it.
Instead of a hashing algorithm we will use a MAC (Wikipedia:MAC), which a hashing algorithm with a key. A well-spread MAC construction is HMAC: HMAC(msg,key1,key2) = H( key1 || H(key2||msg) ) where H is a cryptographic hash and || is concatenation.

If we prevent the adversary from knowing the key we used, he cannot re-compute the MAC after he modified the message.
So now we only need privacy on the MAC key, which is another challenge, you can solve it with a Key-Exchange protocol (typically: Diffie-Hellman), probably with authentication if you have a Man-In-The-Middle, and so on ...


Extension of a password hashing algorithm using Fibonacci

Ignore the integer overflow issue I mentioned in a comment, for a moment.

I don't see how this adds any security.

For all $n>2$, the function you are calling Fibonacci is one-to-one, and since $n<256$, you could easily build a lookup table without much memory to invert the function.

Therefore, to break this, all one has to do is invert the Fibonacci related stuff (not too hard), then attempt to break the SHA-1 hash. So, it isn't much harder than just breaking the SHA-1 hash by itself.

  if not, if you can give me some suggestions

Well, that would just take all the fun out of your class, now wouldn't it. That said, look into functions like PBKDF2 and bcrypt to see how they make things harder.

The integer overflow issue could make it harder to invert the function. Though, likely not in a cryptographically secure manner. But to really say no, it doesn't add security, I'd have to check how the integer overflow problem manifests itself.


In the SIKE known answer tests, why is there only one secret key?

This Wiki page describes SIDH, a key exchange protocol.

SIKE is a key encapsulation mechanism, like all entries in the NIST PQ competition, it has a different API.


How does the SSH server know the length of data encrypted?

Quoting the SSH protocol:

  "Note that the 'packet_length' field is also encrypted, and processing it requires special care when sending or receiving packets."

Generally ciphers process bytes from left to right. This means that the packet length can be available before the encryption is ended (or before all the information is received, for that matter).

This is a horrible protocol decision because it means you have to interleave between the packet decoding and decryption layer, and you will get the message length before it is authenticated. Still, it is practically doable.

There is probably one advantage: you can add more padding to avoid some side channel attacks that use the length of the send packages. However, this advantage is hard to use, because you'd now also have to mix the application and encryption code.

Note that the other sizes - such as MAC length - are determined by the protocol and protocol configuration during the handshake.


How does Euler's Theorem show that $(m^e)^d ≡ m \bmod n$

I thought that Euler's theorem basically proved that, for $(m^e)^d \equiv m \pmod n$ to work, $ed \equiv 1 \pmod {\phi(n)}$ must be true

No; a direct application of Euler's theorem shows that if $ed \equiv 1 \pmod {\phi(n)}$ is true (and $\gcd(m,n)=1$, Euler's theorem needs that as well), then we always have $(m^e)^d \equiv m \pmod n$

However, it does not imply the converse (and in fact, the converse is not true).

A stronger statement would be (assuming $n = pq$ for distinct primes $p, q$) that if $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$, then we have $(m^e)^d \equiv m \pmod n$ for all $m$.

And, in this case, the converse is true; if we have $(m^e)^d \equiv m \pmod n$ for all $m$, then we necessarily have $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$.  In fact, if we have either $ed \not\equiv 1 \pmod{ p - 1}$ or $ed \not\equiv 1 \pmod{ q - 1}$, then we'll necessarily have $(m^e)^d \not\equiv m \pmod n$ for at least 1/3 of the possible $m$ values.

Another (perhaps more common) way of writing these two equivalences is to express it as $ed \equiv 1 \pmod{ \lambda(n) }$ for the function $\lambda(n) = \text{lcm}(p-1, q-1)$.

How does these stronger statements relate to your original relation?  Well, if we have $ed \equiv 1 \pmod{\phi(n)}$, then we necessarily have $ed \equiv 1 \pmod{\lambda(n)}$ (and hence RSA "works")


Is possible that find numbers where the product of 3 numbers is congruent modulo to 1?

It is possible that find the a, b, c randomly in here?  $abc \equiv 1{\pmod {\varphi (N)}} $

The most obvious way is to select $a, b$ randomly (relatively prime to $\phi(N)$), and then compute $c = (ab)^{-1} \bmod{ \phi(N) }$.  It is easy to show that if $a, b$ are chosen uniformly and independently from $\mathbb{Z}_{N}^*$, then $c$ is also chosen uniformly.


SHA256 HMAC brute force with chosen plaintext attacks

I'll assume that "sha256hmac" designates HMAC using SHA-256 as the underlying hash function.

HMAC is used for its intended usage: the first parameter privatekey is a key, I assume random and secret, of fair length (128-bit); the second parameter word is a (possibly public) message; output is a (possibly public) cryptogram. Observing any number of (word, output) pairs, even for word of an adversary's choice, will not enable to recover privatekey or otherwise compute new result.

Its hard to tell if having (word, output) pairs makes the task significantly easier: it goes from impossible with no pair at all, to infeasible using any foreseeable technology with some pairs (unless we consider quantum computers practically applicable to cryptography as foreseeable, which requires some dose of optimism).

With one privatekey of 128-bit, I think we are good against brute force for two decades, with fair confidence. If there was billions privatekey and the adversary could obtain output for the same word for each of these privatekey, we would NOT be quite that safe with the 128-bit key size (the adversary has a remotely feasible task of finding one privatekey), and we would need more bits: 192 are fine, 256 aplenty.

The most practical danger is privatekey leaking, by organizational means, or side-channel attack.

The modern security argument for HMAC is Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance (full version), originally in proceedings of Crypto 2006.


DES: How to find the Inverse of the Initial Permutation?

The inverse of the Initial Permutation (IP) of DES is the Final Permutation (FP) (in the Standard (NIST FIPS 46-3) FP is called "IP-1").  Number the 64 bits of the input to IP from 1 to 64.  Subject them to IP, so that the 1st 8 bits of the output of IP are bits { 58, 50, 42, 34, 26, 18, 10, 2 } etc. of the input.  Renumber (not reorder) the bits of the output of IP from 1 to 64.  Treat that as the input to FP.


Tests on /dev/urandom entropy can be considered useful or not?

Bear in mind that entropy is measured against a source using a model. It is unlikely you will find any model or attack against /dev/urandom that worked purely by analysing its output - from that perspective it will have "perfect" entropy by any realistic measure. However, so would Mersenne Twister unless you knew how to build a model that extracted its state . . . in which case you could reduce that to zero entropy after 624 measurements.

In short, measuring "entropy" of any RNG with a generic model is unlikely to show you anything. If you don't take care, even very bad RNGs will pass tests such as compressibility or naive checks for patterns.

There are tools that allow you to check that a source is statistically random in various ways. I could suggest Dieharder as it provides a command-line interface which is easy to connect via a *nix pipe. This will run a variety of simulations and pattern-detection algorithms against a source of alleged random bytes.

A test against /dev/urandom should look like this:

cat /dev/urandom | dieharder -g 200 -a

. . . and may take a few hours to complete, since the tests consume large amounts of source data.

Caveats:

Proving something is "random" is not easy. At best you get a probability of getting the same result from a theoretical truly random source. If you run hundreds of tests (like Dieharder does), then some will probably end up reporting a low $p$ value - e.g. 0.01 or less. This is not necessarily bad. RNGs that really fail Dieharder tend to do so very dramatically with $p < 0.000001$ in multiple related tests.
If you find that a source is statistically random, that does not mean it is secure, just that it has demonstrated one desirable property of a secure system.


Would a HMAC digest make sense in an RSA / ECDSA signature?

If we view HMAC as a message authentication code or a PRF, this doesn't quite make sense: the security property for a MAC or a PRF assumes that the forger doesn't know the key, but you've given them the key $k$ in the signature.  But you have the right intuition that there is something here.

While a signature scheme in terms of $H(m)$ requires $H$ to be collision-resistant, a randomized signature scheme in terms of $H(r, m)$ requires $H$ to have only the much more modest property of enhanced target collision resistance, eTCR, which even MD5 may still exhibit.  So yes, what you suggest does seem to improve security in the face of unkeyed collision attacks on hashes like MD5 and SHA-1.

Obviously, if you're looking to be compatible with an existing system that uses ECDSA and can't be modified, the idea won't help you.  But modern signature schemes like EdDSA use it as part of the design, and you can always adapt an existing signature scheme to use it—NIST even standardized it in NIST SP 800-106, Randomized Hashing for Digital Signatures.  HMAC might work for the purpose too.

If you want more details, there's a lot of history here, so buckle up, buckaroos, for some story time!

Early history: Rabin signatures and the importance of hashing.
The first secure signature scheme in history, due to Michael O. Rabin[1], took a public key to be a pair $(n, b)$ of integers and a signature on a message $m$ to be a pair $(s, u)$ of an integer $s$ and a bit string $u$ such that $$s\cdot(s + b) \equiv H(m, u) \pmod n.$$  The signer, of course, knows the secret factors $p$ and $q$ of $n = pq$, in terms of which computation of square roots modulo $n$ is cheap, particularly if $p \equiv q \equiv 3 \pmod 4$.  The hashing and randomization served two purposes that Rabin articulated:

Allow the signer to vary $u$ until $H(m, u)$ admits a solution to the equation at all in $s$.
Reduce the probability that the signer accidentally reveals distinct square roots $s \ne s'$ of a common square, which would reveal the factorization of $n$.

We might also add a property that Rabin may have felt too obvious to state:

Compress long messages and destroy any structure, like integer perfect squares whose integer square root could be used to forge signatures.

It's unclear whether active attacks exploiting collisions were considered at this time, but provided that $H$ is collision-resistant, Rabin's scheme remains secure today by the modern standard of existential unforgeability under chosen-message attack (EUF-CMA), assuming suitable parameter sizes.  In fact, $H$ may not even need to be collision-resistant, but it's not clear that anyone noticed this until Schnorr a decade later.  Soon after Rabin, Hugh C. Williams[2] (paywall-free) showed how to efficiently compute squaring-type signatures deterministically with tweaks when $p \equiv 3 \pmod 8$ and $q \equiv 7 \pmod 8$, obviating the need for randomization to achieve purpose (1).

Hashing, collision resistance, and discrete log signatures.
The importance of hashing appears to have been lost on Taher Elgamal initially in his discrete-log-type signature scheme[3], which was trivially breakable as a consequence—a signature under a public key $y$ on a message $m$ is a pair $(r, s)$ of integers such that $$a^m \equiv y^r r^s \pmod p,$$ which, for example, admits the trivial forgery $(0, 0)$ on the message $m = 0$ for any public key.  ($p$ is the standard modulus and $a$ is the standard generator of some subgroup of $\mathbb Z/p\mathbb Z$.)

Not everyone neglected hashing, though, and by the late '80s the importance of collision-resistant hashing was in the air: in Claus P. Schnorr's discrete-log-type signature scheme[4], where a signature under a public key $v$ on a message $m$ is a pair $(e, y)$ such that $$e = H(a^y v^e \bmod p, m),$$ Schnorr observed that the hash function $H$ need not be collision-resistant if it is randomized, and therefore could presumably be half the length a naive composition of, e.g., Elgamal with a collision-resistant hash would require for the same security.

The NSA—ahem, I mean, NIST—recognized the importance of collision resistance in a fixed hash in the Digital Signature Standard, FIPS 186, but carefully made the opposite of every good design decision of Schnorr[5] for fear of treading upon a patent, including randomization of the hash.  They also, of course, made DSA vulnerable to bad RNGs when making signatures, over the vociferious objections of contemporary cryptographers which NIST casually brushed off[6].

Provable security and industry standardization: RSA-PSS and RSA, Inc.
Early standardization of RSA like PKCS#1 v1.5 used an ad hoc way to shoehorn a message hash into an element of $\mathbb Z/n\mathbb Z$—specifically, into a minuscule sparse subspace of $\mathbb Z/n\mathbb Z$ which is useless for studying in relation to the difficulty of computing $e^{\mathit{th}}$ roots of a uniform random element of $\mathbb Z/n\mathbb Z$, which is the RSA problem and which is presumably more closely studied than the RSASSA-PKCS1-v1_5 problem.

In 1996, Mihir Bellare and Phil Rogaway[7] studied the security of RSA- and Rabin-type signature schemes in what more closely resembles the modern framework of ‘provable security’—showing how to use a forger as a subroutine in an otherwise cheap algorithm to compute $e^{\mathit{th}}$ roots modulo $n$, or to factor $n$ in the case of squaring-type schemes.  They were able to prove that if $H$ covers the whole of $\mathbb Z/n\mathbb Z$, then forgery of signatures $s$ satisfying the signature equation $$s^e \equiv H(m) \pmod n$$ called RSA-FDH, can be used for an algorithm to compute $e^{\mathit{th}}$ roots modulo $n$.

Bellare and Rogaway weren't satisfied with the specific theorem they proved, though, because its high cost for modest success probability meant nothing in the case where you sign lots and lots of messages.  So they considered a randomized variant, a probabilistic signature scheme or PSS, with the signature equation $$s^e \equiv \bigl[r \mathbin\| H(r \mathbin\| m)\bigr] \pmod n,$$ roughly.  Randomization in PSS enabled them to easily prove a stronger theorem.*  They also observed in their proposal for IEEE P1363[8] that using $H(r \mathbin\| m)$ did not seem to rely on collision resistance of $H$.  But what was actually standardized instead uses $H(r \mathbin\| H(m))$, which is vulnerable to collisions in $H$. In particular, this was standardized in IEEE P1363 in 2000 (paywall-free; §12.1.2 ‘EMSA2’, pp. 60–61) and by RSA, Inc., in PKCS #1 v2.1 in 2002 (§9.1 ‘EMSA-PSS’, pp. 33–36).

Coincidentally, I'm sure, this was around the same time that the NSA donated ten million dollars to RSA, Inc., to encourage them to deploy the highly superior Dual_EC_DRBG to their BSAFE customers[9].  Not much later—it is unclear from the public record exactly when, but almost certainly not later than 2007—the governments of the United States and Israel exploited an MD5 collision attack[10] to forge signatures on code-signing certificates in an international incident of industrial sabotage against Iran.  Oops.

Formalizing and standardizing collision resilience.
In 1989, Moni Naor and Moti Yung introduced universal one-way hash functions or UOWHFs[11] to formalize what one would expect of randomized hashes for digital signatures: if an adversary submits $m$ up front and is then given $r$, it is hard to find $m' \ne m$ such that $H(r, m') = H(r, m)$—essentially a restricted case of second-preimage resistance.  In 1997, Bellare and Rogaway had the brilliant innovation of giving the concept a more pronounceable and memorable name, target collision resistance or TCR[12], but in spite of the rebranding the notion received little attention for a decade.

Then, in the mid-2000s, as the foundations of collision resistance were cracking at the seams, cryptographers began to seek ways around it, and dusted off old volumes of Naor and Yung and of Bellare and Rogaway.

Phil Rogaway and Tom Shrimpton comprehensively studied relations between various standard notions of security of keyed hash functions—collision resistance, preimage resistance, second-preimage resistance, etc.—and proved implications and gave counterexamples for nonimplications[13]; TCR features as ‘eSec’ or ‘everywhere second-preimage resistant’ in their work.
Shai Halevi and Hugo Krawczyk studied randomization of signatures[14], and invented an even better version of TCR called enhanced target collision resistance or eTCR: if an adversary submits $m$ up front and is then given $r$, it is hard to find $(r', m') \ne (r, m)$ such that $H(r', m') = H(r, m)$.  This is important for signatures schemes where the randomization $r$ does not naturally figure in as it does in PSS, and where the adversary therefore has latitude to control it—as in your suggested generic use of HMAC to strengthen signatures by randomization.  They proposed a generic construction called RMX[15], submitted a now-expired internet-draft to the IETF[16], and persuaded NIST to standardize it as NIST SP 800-106.

Bellare and Rogaway observed that the usual Merkle–Damgård structure doesn't guarantee TCR, which is why Halevi and Krawczyk proposed RMX.  But even though collisions have been found in, e.g., MD5 and SHA-1, there doesn't seem to be much evidence that they fail to exhibit eTCR.  So while the Merkle–Damgård structure doesn't imply eTCR, the design principle of using $H(r \mathbin\| m)$ instead of $H(m)$ in a signature has been adopted in newer schemes like EdDSA[17] following Schnorr's observation in 1989.  It seems unlikely that $\operatorname{HMAC-}\!H_r(m)$ would fail eTCR either even for $H = \operatorname{MD5}$ or $H = \operatorname{SHA1}$.

Conclusion.
Today, there is only one signature scheme that new applications should use unless they have exotic needs: Ed25519, which has this kind of collision resilience built-in by design.  Legacy applications may be stuck with signature schemes like DSA or RSASSA-PSS that have collision vulnerability built-in by design, but maybe if you're only partly stuck on legacy system—you can't use a new signature primitive because you have auditors clamoring at the door about FIPS, but you can use a legacy signature primitive in a new way—you can adapt it to be collision-resilient by randomizing it with RMX, or perhaps with HMAC, or perhaps even with the simple prefix $H(r \mathbin\| m)$.

* The role of the randomization in these theorems is a little peculiar.  Even a single bit of randomization apparently makes a difference in the tightness of the theorems about $e^{\mathit{th}}$ root schemes but not square root schemes[18], which should raise a few eyebrows about the years of effort in the provable security literature that have been dedicated to this single bit of randomization while the US and Israel were at about the same time actually exploiting collisions in MD5 to forge signatures in real standards to wreck Iran's nuclear program.


Does it make any sense to sign a GCM authentication tag with RSA?

Not much; signing the GCM tag using RSA is inadequate.
For a start, knowing the AES secret key, it's easy to make a message with any desired content (except in the very end), and an AES-GCM cryptogram that checks, and has any desired tag. Thus any holder of the AES secret key can forge a message that pass verification under the RSA public key of another person, after intercepting a ciphertext signed by that person.
Also, one holding the AES secret key can prepare two very different messages and their AES-GCM encryption sharing the same tag, allowing to spread FUD by showing that the signature of one message also applies to another message.
Further, if RSA-signing the tag was done nevertheless, that must not be with textbook RSA, which is insecure when directly signing small values $m$ such as the 128-bit tag (e.g. when $e$ is so small that $m^e<n\,$, or under the Desmedt-Odlyzko attack for any $e$).

An appropriate way is sign-then-encrypt: signing the plaintext using RSA (e.g. per RSASSA-PSS or RSASSA-PKCS1-v1_5), appending the signature, then using AES-GCM on the whole. This way only the holder of the RSA private key (rather than any holder of the AES-GCM secret key) can make a valid message that pass verification under the corresponding public key; and the signature (which discloses information about what's signed) is not accessible before decryption.
Here I don't recommend encrypt-then-sign, because I do not rule out that the integrity could be vulnerable to a replacement of the original AES secret key.


It depends on what blockchains are you talking about and what you considered as plaintext.
For example, in Bitcoin, the transaction includes the signature, public keys, amount etc., and the amount being transferred is in plaintext. For Monero, the transaction includes more elements (i.e. a list of public keys, a signature, commitment to the amount), amounts are encrypted in a way that the only recipient can open.
The hash of the current block is the hash of the data in the current block and the hash of the previous block (i.e. $B_i = h(B_{i-1}, \{tx| tx \in B_i\})$). So what happened when you modified the data in block $B_{i-1}$? $B_{i}$ will change.
If you understand how $\mathsf{git}$ works? it's very similar. It's more interesting to see how the network agrees on a single chain.


Is appending the hash of the plaintext to the end of an encrypted message sufficient to ensure integrity?

Not in the sense of authentication. Such a construction is malleable for many reasonable encryption algorithms. It also leaks the plaintext to anyone who can guess it, since they can calculate $h(P_i)$ for guesses (brute force or dictionary attack) and compare to the hash value.

As for malleability, if the cipher is a stream cipher and the attacker can guess that the message is $A$, then they can turn it to an equally long message $A'$ by calculating a new ciphertext $C' = C \oplus A \oplus A'$ and replacing the old hash with $h(A')$.

CTR, OFB etc. modes are essentially stream ciphers so the above applies. Similar attacks, perhaps more limited, are possible against some other block cipher modes as well. For example, with CBC the attacker can replace the last message block with some earlier block to make a deterministic change to the message (xor by a xor of certain ciphertext blocks). They can then calculate the new hash and replace.

Even if you encrypted the hash, to avoid guessing, it might still not be a secure MAC. Further, if is was, you would be using encrypt-and-MAC since the hash is over the plaintext. Encrypt-then-MAC has some advantages over it.

If this a real world scenario, consider instead appending an HMAC of the ciphertext or using an authenticated encryption mode.


Does rsa-oaep provide or not plaintext integrity in addition to confidentiality?

RSA-OAEP does not provide "plaintext integrity in addition to confidentiality".  By the definition of PKE, anyone with the public key can encrypt whatever plaintexts they choose.  In particular, encrypting "a symmetric session key appended with a hash or eventually crc value for insuring integrity" doesn't help.  To get integrity, there has to be something [the honest party knows which the adversary doesn't know] or [the honest party can do that the adversary can't do].


Why does .NET's ECB mode implementation append a constant block to my ciphertext?

I believe what you are seeing is that .NET automatically uses PKCS #7 padding. This will always add padding. Thus if your plaintext is a complete block length, one extra block of padding will be added.

The reason the ciphertext ends up being the same in both of your test cases is that it is adding the same padding in both cases (see PaddingMode Enumeration for details on PKCS #7).

You can have .NET use no padding by using the Padding Property.


Is there a relationship between the secp256k1 public key of the sum of two private keys, and the public keys of those original two private keys?

If I have two secp256k1 private keys and add them together, can I derive the public key for the sum, if I only know the public keys for the two original private keys?

Yes.
While the idea of 'public keys' and 'private keys' depends on the cryptosystem (and not the elliptic curve it uses), most ECC-based cryptosystems (including the one used in bitcoin) have a private key that is a secret integer $a$, and a public key that is the elliptic curve point $[a]G$, where $G$ is a publicly known elliptic curve point (which is part of the definition of the curve), and $[a]G$ is computed using 'point multiplication'.
So, your question boils down to "if we know two public keys $[a]G$ and $[b]G$ (with private keys $a$ and $b$), can I derive the public key $[a+b]G$, which is the public key for the sum of the private keys?"
The answer is, yes, because this identity always holds:
$$[a+b]G = [a]G + [b]G$$
where the addition on the left side is integer addition, and the addition on the right side is point addition.  The right side is easy to compute, when we can get the public key for the sum of the private keys.


Meaning of epsilon in proving a PRG is predictable/ un predictable

Loosely, ‘negligible’ means small enough to ignore.  A difference in probability of $2^{-128}$ is likely small enough to ignore; a difference in probability $2^{-10}$ may not be.

Formally, in the language of complexity theory, a function $f\colon \mathbb N \to \mathbb R$ which assigns to each natural number $n$ a real number $f(n)$ is negligible if it goes to zero faster than the inverse of any polynomial—that is, if for any polynomial $p$, there exists a number $n_0$ such that for any $n > n_0$, $|f(n)| < |1/p(n)|$.

For example, $n \mapsto e^{-n}$ is a negligible function.

  Sketch of proof: Let $p(x) = x^d$; at what point $n_0$ do we have $e^{-n} < 1/n^d$, or $e^d < n^n = e^{n \log n}$, for all $n > n_0$?  We don't need to solve this exactly—it suffices to set $n_0 = d$; as long as $n > n_0 = d$, $n \log n > n > d$, so $n^n = e^{n \log n} > e^d$ and thus $n^{-d} > e^{-n}$, or $e^{-n} < 1/n^d$ as desired.  Finding the corresponding bound $n_0$ for other polynomials left as an exercise for the reader.

In the language of complexity theory, we usually consider ensembles of cryptosystems that scale with a security parameter, and we consider the asymptotics of the growth curves of the user's cost and the adversary's cost as the security parameter scales.

The same is true for algorithms more generally, which is why software engineers will casually talk of quicksort's $O(n^2)$ worst-case time but $O(n \log n)$ average time, because it's a useful proxy for estimating concrete costs—and, unlike a measurement in seconds or joules, it doesn't change if you move from one machine to another, which is helpful for understanding how it will scale if you feed it more and more data even if you use a slightly faster machine.

Of course, we must be careful not to lose sight of the concrete numbers without asymptotics: while it is proven[1] that multiplication can be computed in $O(n \log n)$ bit operations, you'll still get an answer faster in wall clock time using a naive $O(n^2)$ algorithm for any input that is possible to work with in practice.

Similarly, while the Blum–Blum–Shub pseudorandom generator has a polynomial-time reduction theorem relating the difficulty of distinguishing BBS output to the difficulty of factoring the BBS modulus, the concrete security of BBS[2] (paywall-free) is such that it costs $2^{43}$ bit operations to generate a mere 128 KB of data at a ~100-bit security level, using somewhat old estimates for factoring costs.  At 2.5 GHz, that takes a minute of computation.  In contrast, e.g., AES-256 can generate the same amount of data in microseconds at a much higher security level.


No, because this is just an intermediate step. Roughly, if you want to get $n$ standard (correlated or not) OTs where the receiver chooses what he gets, our construction has four main steps:

a) Build a correlated OT where the choice vector is a random $t$-sparse vector (a very large vector, but with only $t$ random 1's). This is what is done using a sum of $t$ PPRFs.
b) Transform the "correlated OT with sparse choice vector" into a "correlated OT with pseudorandom choice vector". This is done using the dual LPN assumption. The idea here is simple: after doing (a), the sender has $\Delta, \vec q_0$, and the receiver has $\vec b, \vec q_1$, where $\vec q_0 + \vec q_1 = \Delta\cdot \vec b$, where the vectors are of length $n$ and $\vec b$ is $t$-sparse (this is exactly $n$ correlated OT with a $t$-sparse vector of choice bits). Now, all parties multiply their vectors using a public random compressing matrix $H$: the sender has $(\Delta, H\cdot \vec q_0)$ and the receiver has $(H\cdot \vec b, H\cdot \vec q_1)$. Observe that
$H\cdot \vec q_0 + H\cdot \vec q_1 = H\cdot (\vec q_0+\vec q_1) = H\cdot (\Delta\cdot \vec b) = \Delta\cdot (H\cdot \vec b)$,
so this is still $n$ correlated OT, but now the vector of choice bits is $H\cdot \vec b$. By the dual-LPN assumption, if $\vec b$ is a random $t$-sparse vector, then this $H\cdot \vec b$ is indistinguishable from a truly random vector.
c) If you want non-correlated OTs in the end, transform the $n$ correlated OTs with pseudorandom choice bits above into $n$ standard OTs with random choice bits; this uses IKNP-style decorrelation, i.e., just hash everything with a correlation-robust hash function to "break" the correlation. If you are fine with correlated OTs, skip this step.
d) It only remains to convert your $n$ OTs with pseudorandom choice bits into OTs with chosen choice bits. This is actually your question 2:

There is standard method to convert an OT with random choice bit (and random inputs as well) into a standard OT witch chosen inputs and choice bits. This involves three bits of communication per OT, which is optimal (you cannot hope to transmit one bit out of two chosen bits, using a chosen 'choice bit', using less than three bits of communication). Note that silent OT has communication sublinear in the total number of OTs generated, but only because the inputs and choice bits are pseudorandom - converted into standard OTs, they give OT with quasi-optimal communication, $3+o(1)$ bits per OT (amortized over $n$ instances).

The standard method is relatively simple. The sender has random inputs $(r_0,r_1)$ and true inputs $(s_0,s_1)$. The receiver has random choice bit $b$, knows $r_b$ (because of the random OT), and has true choice bit $\sigma$. Then, the receiver does the following ($\oplus$ denotes XOR):

If $b = \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_0, r_1 \oplus s_1)$, and recover $s_\sigma = s_b = u_b \oplus r_b$.
If $b \neq \sigma$, ask the receiver to send $(u_0, u_1) = (r_0 \oplus s_1, r_1 \oplus s_0)$, and recover $s_\sigma = s_b = u_{1-b} \oplus r_b$.

Note that the message from the receiver to the sender involves communicating only $b \oplus \sigma$, i.e., telling the sender if $b = \sigma$ or not. Since $b$ is random, this reveals nothing about $\sigma$. Sender security is easy to see as well and is left as exercise for the reader :) In total, the above has two rounds and involves three bits of communication for each chosen OT.


Near in place encryption with BouncyCastle CCM, How large must IV and MAC be?

So I'll answer in order:

  Q1: Is a 16 bit MAC effective at all in this scenario?

You have defined (part of) your protocol, but you haven't defined your system. What happens if a MAC doesn't get accepted? If you have only a 16 bit MAC then there are only 65536 values of the MAC. If an adversary can just generate messages and fire them at the receiver then brute forcing a tag is entirely possible. Even if you can just have one try: a chance of $1 \over 65536$ is not considered secure enough.

Using 8 bytes would be a great idea, but that leaves you only 2 bytes for a nonce, so you would only have 65536 messages.

  Q2: Is it kosher to create a nonce from partially known data?

Sure thing, a Nonce just needs to be unique - but note that in the case of CTR and CCM the nonce size also influences how many counter blocks can be created, and therefore how much data can be processed per nonce. CCM is just like CTR in that sense; it even requires an additional byte of meta information in the counter, leaving less space for the nonce and counter.

Kind of obvious, but the other requirement is that the receiver must be able to re-generate the nonce.

  Q3: How can i verify that my nonce is being incremented properly inside the code? I just appear to pass a static nonce even though its supposed to increment according to CTR... right?

No, the counter is being incremented - not the nonce. The nonce is just used to create the counter. Often the nonce is simply the most significant part of the counter. In the case of CCM this is true as well, even though the most significant byte is skipped. see for instance NIST SP 800-38C chapter A.3 where the counter increase is being implemented.

In GCM mode it is also possible that the nonce is pre-processed to generate the initial counter value, so there are certainly differences in how the nonce is used between the various implementations of authenticated encryption, even though CTR mode is used in virtually all these modes.

Note that the counter mode specified by NIST does not specify how the counter value must be generated; implementations are free to choose any scheme they want.


Inside attack (attack from participants) in secret sharing

I think you are mis-understanding secret sharing and what it can and cannot do. In a $(t,n)$ secret sharing scheme, the server/trusted party creates $n$ shares of the secret. At least $t$ shares must be present in order to recreate the secret from the shares. Now, if after reconstruction, the secret itself is revealed to the $t$ share holders requesting re-construction, then they each know the secret, and it is possible that the secret will be revealed milliseconds after the shares have been distributed when at least $t$ shareholders promptly send their shares back with a request for reconstruction! "Don't given me a share of the secret, just tell me the secret!" would be the rallying cry. Whether the reconstructed secret is also provided to the other $n-t$ shareholders and not just the $t$ requesters is an open question.

The way secret sharing is meant to operate is that reconstruction of the secret enables some further action (e.g. making a payment) that can be authorized by any $t$ shareholders but doesn't require approval of all $n$ shareholders. The secret is the password that is used to authorize the action. Thus, setting $t > \frac n2$ would mean a majority of the shareholders approve taking the further action and so authorize it. The secret itself is not revealed to those requesting re-construction; doing so would mean that any of the shareholders who now know the secret can carry out the further action all by themselves without the knowledge or approval of anybody else.

With this as an introduction, let us consider what the OP wants. There are $t$ shareholders who wish to reconstruct the secret, but $t-1$ of them are "cheaters" who want to "cheat" the honest participant. Well, regardless of whether valid shares are presented or are sheer gobbledygook, the trusted party will reconstruct something. For example, as I described in this answer, with Shamir secret-sharing, the secret is
$$s_0 = (-1)^t (x_1x_2x_3\cdots x_t) \sum_{i=1}^t \frac{y_i}{x_i\cdot c_i}$$
where $y_1, y_2, \ldots, y_t$ are the share values as submitted by the share holders, $x_1, x_2, \ldots, x_t$ are the corresponding "locations" used in computing the shares, and
$$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_t).$$
There is no checking as to whether the submitted "shares" are valid or not; we get $s_0$ which is the correct secret if the shares are valid as submitted, or is gobbledygook if any of them are not. So, when the trusted party who reconstructs the secret tries to use the reconstructed gobbledygook as the password for taking the requested action, that login fails! Thus, the only question is how, if at all, the honest shareholder is cheated in all this. Well, presumably the honest shareholder wants the action to be taken, and that action will not be taken if the $t-1$ cheaters (or even just one cheater!) have submitted invalid shares. So the honest shareholder has been cheated of his desire by fickle friends who pretended to support him in in his desire but thwarted him by choosing to submit invalid shares.

Is it possible that $t-1$ cheaters can prevent reconstruction of the secret?  Yes, if there are only $t$ shares available. With more shares available for reconstruction, things might be  done. But we are too far afield already.


What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI

ChainOfFools (or Microsoft's Chain of Fools) or CurveBall is a vulnerability in Microsoft's X.509 certificate verification affecting certificate chains that use ECDSA at any point, discovery by NSA!1.
From Microsoft site for CVE-2020-0601

An attacker could exploit the vulnerability by using a spoofed code-signing certificate to sign a malicious executable, making it appear the file was from a trusted, legitimate source. The user would have no way of knowing the file was malicious because the digital signature would appear to be from a trusted provider.

From the CERT site

Any software, including third-party non-Microsoft software, that relies on the Windows CertGetCertificateChain() function to determine if an X.509 certificate can be traced to a trusted root CA may incorrectly determine the trustworthiness of a certificate chain.

Therefore, an attacker can create a valid certificate chain so that a malicious code can be trusted.
Details:
TLS often uses ECDSA to authenticate servers and clients. Windows code distribution often uses ECDSA for code-signing. The vulnerability affects certificate checking if ECDSA has been used at any point in the chain (code signed with ECDSA, or website authenticated with ECDSA, or a CA authenticated with ECDSA by a root CA, etc.).
Given an ECDSA signature, one can easily create a new private key that has the same public key matches if domain parameters are controllable.
The trick is simple, let begin with defining a curve over a finite field $\mathbb{F}_p$;
$$E:y^2 = x^3 + ax + b$$
Standards defines the parameters, $(p,a,b,G,n,h)$, where $G$ is the base point, $n$ is the order of $G$ and $h$ is the cofactor. See for example secp256k1.
Since we agree on the standard we all use the same parameters. Then one selects a private $k \in [1..n-1]$ and calculates the public key by scalar multiplication $[k]G$. So, your private key is a number, but, the public key is a point on the curve and protected by the EC discrete log.
The attack point:
What if the programmers/designers of a library forget to check the base point?
Now the attacker can create a new private key that has the same public key with a different base point as follows;
Let the target public key be $P$ with $P=[k]G$ of the private key $k$. Then the attacker chooses random key $k'$ and calculates their malicious base point $G'$ with
$$G' = [1/k']P$$ the $1/k=k^{-1}$ is computable since the inverse exists in the finite field $\mathbb{F}_p$ and can be computed by the extendedGCD.
Now, in the new curve where all parameters are the same as the previous except the base point, the public key is the same as the target key, but the private key is not.
Since we assumed that the library is not checking the base point, the attackers can exploit this vulnerability and spoof the Windows certificate chain and the website or signed code will appear as a legitimate source.

A Sage code can be found in Hacker News by zahllos.
One can test their system on https://curveballtest.com/ (no https!)

1 Or, they don't need anymore!


Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes?

Attacks on a cryptosystem with a 128-bit key are often much cheaper than $2^{128}$.  If you have the strings $\operatorname{AES}_{k_1}(812738)$, $\operatorname{AES}_{k_2}(812738)$, $\dots$, $\operatorname{AES}_{k_{1000000}}(812738)$, it costs only about $2^{128}/1000000 \approx 2^{108}$ AES evaluations to find one of the $k_i$ keys if you can parallelize it $p \geq n^2$ ways, and it will take the time for about $2^{128}/np \leq 2^{128}/n^3$ sequential AES evaluations.

You should use 256-bit keys, whether with ChaCha or AES or HKDF-SHA256 or KMAC128 or anything else.  The only reason ChaCha supports 128-bit keys at all, on paper, is that eSTREAM wanted to support 128-bit keys, so Salsa20 was made to support 128-bit keys, on paper, and the design carries over to ChaCha.  Hardly anyone ever actually does this.  The eSTREAM profile also specifically selected Salsa20/12, the 12-round version instead of the full 20-round Salsa20/20, also known as just Salsa20; similarly, ChaCha12 formally exists, but hardly anyone uses it instead of ChaCha20, also known as just ChaCha.

Now that we've gotten the generic issue of key size out of the way, there are a number of substantive advantages of ChaCha over AES that don't fit neatly into the glib ‘bits of security’ framework.

AES essentially cannot be computed efficiently in software without timing side channels.  ChaCha was designd for fast software implementation without timing side channels.

To match ChaCha's level of side channel security, AES requires hardware support—and that means you need to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the physical machines you might be using, from spiffy x86 servers to years-old laptops to ARM phones to MIPS tablets.
AES is a pseudorandom permutation family of 128-bit blocks.  ChaCha is a pseudorandom function family from 128-bit inputs to 512-bit outputs.

This is mostly jargon that application developers don't need to concern themselves with, but these different shapes have a significant consequence: In most protocols, it is unsafe to use a single AES key for anywhere near ${\approx}2^{64}$ blocks of data, whereas there are no practical data volume limits per key on ChaCha.

For example, probably the most widespread use of AES is in AES-GCM, which uses it in the forward direction only, to approximate one-time pads, just like the ChaCha stream cipher.  The fact that AES is invertible is not helpful—in fact it makes AES appreciably worse at approximating one-time pads than ChaCha, thanks to the birthday paradox.
AES has a substantial key setup cost.  ChaCha has zero key setup cost.

To mitigate the data volume limits under a single key, or just to make key management simpler for complex applications, you can derive subkeys from a master key with a key derivation function or KDF.  This is how, for example, the XChaCha stream cipher supports a 192-bit nonce: it derives a subkey from 128 bits of the nonce, and then uses ChaCha with that subkey and the remaining 64 bits of nonce.  This is also how AES-GCM-SIV provides reasonable security bounds in spite of AES's $2^{64}$ birthday bound.

AES's high key setup cost means subkeys are expensive, while ChaCha's zero key setup cost means subkeys are essentially free.  For example, AES-GCM-SIV was designed under the premise that you are Google and you can afford to audit your entire software stack all the way down from the high-level protocols to the assembly code you're actually executing on all the servers in data centers that you care about, so you can reliably use hardware support for AES both to mitigate side channel attacks and to ameliorate the key setup cost with subkeys.  For the rest of us who are not Google—and even within Google on the teams that do Android and Chromebook development on a variety of platforms—the tradeoff of relying on AES hardware is not so clear.
The highest number of rounds broken by an attack cheaper than brute force for AES-256 seems to be 7, and for ChaCha also seems to be 7.  (The standard biclique attacks on full AES-128 are not obviously cheaper when you consider space and communication costs.)  But AES-256 has only 14 rounds, while ChaCha has 20.  So ChaCha has a higher ‘security margin’ than AES, which is a very rough fuzzy notion that you shouldn't worry too much about because neither one is broken; it just makes ChaCha come out looking a little sprightlier than AES.


Spartacus: Maybe i came out with the solution, since the cryptosystem described above is not CCA-secure, an adversary A can intercept (A,B) and compute a new ciphertext $$C = 2B\bmod N = 2^er^e \bmod N$$ Since he's carring out a CCA-attack he has access to a decryption oracle and since: $$C\neq B$$ the oracle output $$RSA^{-1}(C) = 2^{ed}r^{ed}\bmod N = 2r\bmod N$$ So he can simply recover r by half of computed plaintext, and computing r - A he obtains the deterministic encryption of the message. Is it right?
Artjom-B: You forgot something $2^eB\bmod N=2^er^e\bmod N$. I don't think this is complete, because the decryption oracle would decrypt $(A,C)$ and not $C$ alone.
Spartacus: Maybe it's true but by definition i can't query a decryption oracle with original challenge ciphertext A. If it were possibile we got zero chance of getting a CCA-secure cryptosystem
SEJPM: Hint1: This scheme isn't even IND-CPA secure. Hint2: What Henrick said. Hint 3: Given $(A,B,m,e,N)$, can you somehow recover $r$, possibly using A and m somehow?

Okay, let's prove that the scheme is not IND-CPA secure:

An adversary A outputs two messages $m_0,m_1$.
A uniform bit $b$ is chosen $b \leftarrow \{0,1\}$ and then the challenge ciphertext $C$ is computed as follows: $$ A = r + m_b^e \bmod N$$ $$B = r^e \bmod N.$$
The pair $(A,B)$ is output to the adversary A.
Before guessing the value of $b$ the adversary A still has access to the public key, so he can compute the two deterministic encryptions of $m_0$ and $m_1$ as follows: $$C_0 = m_0^e \bmod N $$ $$C_1 = m_1^e \bmod N$$.
Now he can compute the two possible plaintext values of r as follow  $$P_r^1 = A - C_0 $$ $$P_r^2 = A - C_1.$$
A doesn't know yet which of the two possible computed plaintext values was used, but he has the ciphertext of the right one and the public key, so he computes $$ C_r^1 = (P_r^1)^e \bmod N$$ $$ C_r^2 = (P_r^2)^e \bmod N.$$
Now he can simply compare the ciphertexts as follows:
if $C_r^1 = B$ then use $P_r^1 $, else use $P_r^2 $.
Let $P_r^k$ be the chosen value. Now the adversary can simply compute the deterministic encryption of the challenge ciphertext $C$: $$ C_d = A - P_r^k \bmod N.$$
Now it's easy guess the value of $b$: if $C_d = C_0$ then $b'=0$, else $b'=1$.

So the probability that A output $b'=b$ is equal to $1$; the encryption scheme is not IND-CPA secure.


A simple block cipher based on the SHA-256 hash function

First of all, this no block-cipher at all. It's a stream-cipher. Thus you can use every key only once, and you can't use any cipher modes built on block-ciphers.

Your scheme is vulnerable to a known plaintext attack. If the attacker knows 32 aligned(or 63 unaligned) bytes of plaintext, he can calculate the state of your cipher:

$ S_i = P_i \oplus C_i $

The later $ S_j (j>i) $ only depend on the $ S_i $ the attacker recovered, i.e. he can calculate all of them. And thus he can decrypt everything that comes after that known plaintext.

Such a plain text attack is often possible in practice. Files often start with known magic bytes, network protocols often contain known sequences in headers (http headers should be long enough),...


Signal Double Ratchet - How can Alice send 2+ messages in the beginning of the Signal Protocol?

X3DH derives a shared secret using Alice' static identity and fresh ephemeral with Bob's static identity and semi-ephemeral (and optionally, if available a one-time ephemeral).

Alice sends Bob her static identity and a fresh ephemeral along with her encrypted messages. Bob can complete the handshake and read messages Alice sent him. All messages so far may be compromised if Bob's static and semi-ephemeral keys have been compromised and Bob didn't have any one-time ephemeral keys left. Bob may respond and introduce a fresh ephemeral key. All messages after this point are safe even if Bob's static key and semi-ephemeral were compromised.

Notice how the hash-ratchet is deriving per-message keys independent to the dh-ratchet, so it does not wait for any round trips as it derives multiple message keys.

For more information you may see the X3DH and Double Ratchet specifications.


Finding an elliptic curve of specific order

There are many academic works on finding a curve for a given order.

1994 - Georg-Johann LayHorst G. Zimmer - Constructing elliptic curves with given group order over large finite fields

A procedure is developed for constructing elliptic curves with given group order over large finite fields. The generality of the construction allows an arbitrary choice of the parameters involved. For instance, it is possible to specify the finite field, the group order or the class number of the endomorphism ring of the elliptic curve. This is important for various applications in computational number theory and cryptography.

The task solved in this paper are;

Given an integer $m > 3$, find a prime $p$ and an elliptic curve E over the finite
field Fp of order $\#E(\mathbb F_p) = m$.
Given two integers $n$ and $c_{max}$, find an elliptic curve $E$ over the finite field $\mathbb F_{2^n}$ with $\#E(\mathbb F_{2^n}) = c \cdot q$ with $q$ a prime and $c \leq c_{max}$. ( Note that binary curves are off)
Given an integer $n > 1$, decide whether or not there is a prime $p > 3$ and an
elliptic curve $E$ over $\mathbb F_p$ with structure $E(\mathbb F_p) \sim (\mathbb Z/n \mathbb Z) \times (\mathbb Z/n \mathbb Z)$.
Given a prime $p > 3$ and an integer $m$ with $|p+ 1 - m  < 2 \sqrt p$ , build an
elliptic curve over $\mathbb F_p$ whose group order is m and whose endomorphism ring
has small class number.

2001 : Erkay Savaş, Thomas A. Schmidt, and Çetin K. Koç Generating Elliptic Curves of Prime Order

A variation of the Complex Multiplication (CM) method for generating elliptic curves of known order over finite fields is proposed. We give heuristics and timing statistics in the mildly restricted setting of prime curve order. These may be seen to corroborate earlier work of Koblitz in the class number one setting

The citers of the first one should help if there is a specific work directly your case.

2007 : Reinier Broker, Peter Stevenhagen Constructing elliptic curves of prime order

We present a very efficient algorithm to construct an elliptic curve E and a finite field F such that the order of the point group $E(F)$ is a given prime number N. Heuristically, this algorithm only takes polynomial time $\mathcal{\tilde{O}}((\log N)^3)$, and it is so fast that it may profitably be used to tackle the related problem of finding elliptic curves with point groups of prime order of prescribed size. We also discuss the impact of the use of high-level modular functions to reduce the run time by large constant factors and show that recent gonality bounds for modular curves imply limits on the time reduction that can be obtained.


Can non-repudiation be ensured without public-key cryptography?

Is this a structural limitation of symmetric-key cryptography? Or is there some construct that ensures non-repudiation without using public/private keys?

Non-repudiation implies that nobody other than the private key holder* could have produced the signature, which rules out symmetric constructions such as HMAC.

With a symmetric MAC (from a construction like HMAC), anyone who has the ability to verify a MAC also has the ability to construct one, so such constructions cannot be used to provide non-repudiation.

So in that sense yes, it is a limitation of symmetric-key cryptography.

While Hash-based signatures do exist, those are still an asymmetric cryptosystem with public/private keys, despite the fact that they use traditional hash functions.

Note

It is arguable whether or not signatures provide non-repudiation, which is a legal concept. It is arguable that cryptography itself is limited in the capacity to provide non-repudiation.


Sextic twist optimization of BN pairing - cubic root extraction required?

You need to recall how the extension is built. $\mathbb{F}_{p^{12}}$ is built on top of $\mathbb{F}_{p^2}$ using the reduction polynomial $f(x) = x^6 - \xi$, where $\xi \in \mathbb{F}_{p^2}$ is a non-square and non-cube (using the notation from the paper). In other words, this is the set of polynomials with coefficients in $\mathbb{F}_{p^2}$, modulo $f(x)$.

Since we're working modulo $f(x)$, then $f(x) = 0$ which means that you can write $x = \sqrt[6]{\xi}$. However, this does not mean that you actually carry out the sextic root (it does not exist in $\mathbb{F}_{p^2}$), but you can "define" the sextic root of $\xi$ as $x$ (which is an element of $\mathbb{F}_{p^{12}}$: $x = 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0$). This process is called "adjoining roots": here is a good explanation. (A good analogue is with how you build the complex numbers by "defining" $i$ as the square root of $-1$, which does not exist in the reals).

In your question, $i = \xi$. This means that $i^{1/2} = (i^{1/6})^3 = x^3$ and $i^{1/3} = (i^{1/6})^2 = x^2$. They are just $\mathbb{F}_{p^{12}}$ elements with one coefficient $1$ and the others are zero and are trivially "computed"; you don't need to carry out any square or cube root.

There are some other issues since the sextic extension is often built as a quadratic extension over a cubic extension, but the reasoning is the same.


Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

The Lim-Lee Prime Generation Algorithm you reference has been used in GPG’s libgcrypt for almost 20 years.  As long as the bit length of the smallest prime (other than 2) dividing the prime (p) is greater than or equal to twice the desired bit security the Lim-Lee prime generation produces sufficiently strong primes for use in Diffie-Hellman key exchanges.  For instance, if one wished for 128-bits of classical security, the smallest prime (other than 2) dividing p-1 should be at least 256 bits in length.

Using the Lim-Lee algorithm to generate a prime p gives all of the prime factors of p-1.  These factors can be used to prove the primality of p using an extension of Pocklington’s theorem.  If you were to use the Lim-Lee algorithm for generation of ephemeral primes for a Diffie-Hellman key exchange you should consider using deterministic RNG for the Lim-Lee algorithm.  If you sent the seed for the deterministic RNG to the other side of the key exchange, they could  re-run the Lim-Lee algorithm, produce the prime p, the factors of p-1 and check that p is indeed prime and that all of the prime factors of p-1 are suitably large.  Sending a seed rather than the prime and all its prime factors is more bandwidth efficient.

Given the widespread use of GPG in the world, I would assume that if there were some major weakness in the Lim-Lee algorithm someone would have published a criticism of the algorithm by now.  I have never run across such a criticism.  Therefore, I believe that the Lim-Lee generation scheme is fit for the purpose you describe.


Offline app authentication - embedding hashed password inside an encrypted file

Yes, the scheme is weak, and made weaker by adding the SHA-512 hash of the password.

The ciphertext being assumed known, this scheme allows testing if a user password is genuine with little effort:

compute the SHA-256 hash of the password to be tested
using that as the key, decipher at least the portion of the ciphertext corresponding to the SHA-512 hash of the password
compute the SHA-512 hash of the password to be tested, and compare it to the above. If it matches, the password guess is most likely correct (is not, it is certainly wrong).

There is no attempt to make any of this process slow. Therefore the scheme is awfully vulnerable to a password cracker such as these, which will simply test likely passwords using this procedure (or, most likely, a simpler version thereof using another redundancy in the plaintext, but we can't tell which from the question). With the exponential progress of CPU power, it is safe to say that most passwords humans will use are vulnerable to password cracking in such a scheme; this trend will only get worse with hardware progress.

Main problem is: building a key from a password is the job for a properly parameterized Password-Based Key Derivation Function, such as scrypt. As an aside, passwords must be salted. Failures in this regard are common mistakes in amateur encryption programs (and a number of others).

No, the scheme does not insure message integrity, and adding the SHA-512 in the plaintext does not help towards that.

The adversary can simply alter another portion of the ciphertext, and with many common modes (CBC, OFB, CTR), or if the SHA-512 hash of the password is at the beginning of the ciphertext, this will not prevent decryption. Plaintext might be garbled, but this still goes against the definition of message integrity.

Further, with many common modes (OFB, CTR, and CFB for the last block of the file), if the adversary knows some section of the plaintext (e.g. TWO), she can change it to anything of the same length that she wishes (e.g. to ONE).

For encryption and authentication, use an authenticated encryption mode, such as AES-GCM. Or a more traditional MAC, using a different key than the one used for encryption, especially if this MAC is based on the same block cipher as used in the encryption. In password-based encryption with integrity protection, that different integrity key can be derived from the same password as for encryption, but a different salt.

And of course, if the adversary succeeds in finding the correct password, she can encipher any message she wishes even with the best such schemes.


Committing Bilinear equation in Groth-Sahai framework

Firstly, note that Groth-Sahai framework doesn't provide proofs of knowledge of exponents, because all commitments to exponents in it are computationally irreversible. It only provides proofs that show that such exponents exist. That is, a prover can claim to know $x$ but actually only know $\mathcal{A}^x$ for some $\mathcal{A}$, and still be able to produce a valid proof.

Secondly, the equation can be rewritten as follows:

$$e(K,g_2)^ye(g_1,g_2)^{-xy}=\tau$$

Since $e(K,g_2)$ and $e(g_1,g_2)$ are constants, this equation is linear in terms of $y$ and $-xy$. There is an article describing proof of knowledge systems for such equations:

Camenisch, J., & Stadler, M. Proof Systems for General Statements about Discrete Logarithms.

Alternatively, if it's necessary to use Groth-Sahai framework, the equation can be rewritten as follows:

$$\mathcal{X}=g_1^x\wedge\mathcal{Y}=g_2^y\wedge e(K\mathcal{X}^{-1},\mathcal{Y})=\tau$$

The first two equations are MSME, and the last one is PP. However, there are now three equations instead of one, so the proof is larger than necessary. Also, at least in the DLIN instantiation, a prover can produce a valid proof while only knowing $\mathcal{X}$ and $\mathcal{Y}$ but not $x$ and $y$. I don't know whether it is possible in SXDH instantiation, but anyway, Groth-Sahai proofs are not proofs of knowledge of exponents.

It may also be possible to use Camenisch-Stadler proof system to prove the knowledge of exponents that correspond to commitments in Groth-Sahai proof system. This way, it may be possible to prove the knowledge of exponents as well as the validity of quadratic equations over them.


Generating random vector for Full Homomorphic Cryptography

After thinking about it here's what I think.  Let me know what you think.

First, I generate a random vector of floats and figure out what the dot product is.

I then pick one of the elements of the float vector that correspond to a 1 in the binary array (randomly?), and then adjust that value the necessary amount to make the dot product come out to the value I want.

Thoughts? Seems like it should be ok.


Clarification on Hill Cipher crib dragging technique

I suppose (as you use a length $4$ crib) that your encryption matrix $C$ is of the form

$$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix}$$

and so assuming word $(w_1, w_2, w_3, w_4)$ at a certain position $m$ gives two systems of equations $$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix} \begin{bmatrix}
w_1\\
w_2\\
\end{bmatrix} = \begin{bmatrix}
c_m\\
c_{m+1}\\
\end{bmatrix}$$ and

$$\begin{bmatrix}
k_{11} & k_{12}\\
k_{21} & k_{22}\\
\end{bmatrix} \begin{bmatrix}
w_3\\
w_4\\
\end{bmatrix} = \begin{bmatrix}
c_{m+2}\\
c_{m+3}\\ \end{bmatrix}$$

which gives $4$ equations in the four key entries, rewritten as, e.g. $$
\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\
\end{bmatrix} \begin{bmatrix} k_{11} \\ k_{12} \end{bmatrix}
= \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$ and

$$\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\
\end{bmatrix} \begin{bmatrix} k_{21} \\ k_{22} \end{bmatrix}
= \begin{bmatrix}c_{m+1} \\ c_{m+3}\end{bmatrix}$$

which allows us to compute the candidate key entries as $$
\begin{bmatrix}k_{11}\\k_{12}\end{bmatrix} = {\begin{bmatrix}w_1 & w_2 \\
w_3 & w_4\\\end{bmatrix}}^{-1} \begin{bmatrix}c_m \\ c_{m+2}\end{bmatrix}$$

etc. where we only have to compute the inverse of the plaintext matrix once in advance.

Then test these candidates on another part of the ciphertext (after WITH say) and check for sensible text. If we find it we have the correct $m$. The above holds if the crib WITH starts at a position where it is encrypted as (W,I) (T,H)
which you should try first so $m$ even.). If it is at another position, we get more equations (6 for 3 pairs of cipher text) in 2 more unknowns (the 2 two missing plaintext characters before and after the crib) and have to solve those (easy by computer).


Yes, an adversary can definitely decrypt a DES message, given sufficient funding.  Fifteen years ago, in 1998, the EFF built a DES cracker (nicknamed Deep Crack) that can recover a DES key in a day.  Today, anyone with the money can purchase a commercially available DES cracker named COPACOBANA.

For RC2, I'm not aware of any practical attacks.  (You still shouldn't use it.)

For RC4, the answer is complicated.  It depends.  It depends upon how you use RC4.  There are lots of attacks known, and whether they will be applicable or not to your particular situation will depend upon many fine details of your particular situation.


Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme?

If you only use the group in a black-box way (meaning, if you wish to rely on the discrete logarithm problem on an arbitrary group), we do not know of any encryption scheme (searchable or not) whose IND-CPA security reduces to the discrete logarithm problem. What we can do from the discrete logarithm problem directly is quite limited. In particular:

you can design a commitment scheme whose binding property reduces to the discrete log problem, this is the famous Pedersen commitment scheme.
The key-recovery security of the ElGamal encryption scheme (i.e. the hardness of computing its secret key given only its public key) reduces to the discrete logarithm assumption.

However, in some specific groups, it is known that the computational Diffie-Hellman assumption is equivalent to the discrete logarithm assumption - this was shown by den Boer in this paper.

Furthermore, we know how to construct advanced types of encryption schemes from the computational Diffie-Hellman assumption. For example, using the Goldreich-Levin harcore predicate and the ElGamal encryption scheme, one can construct an encryption scheme whose IND-CPA security reduces to CDH. IND-CCA secure cryptosystems from CDH where given in this paper.

Very recently, in a breakthrough result, Garg and Döttling have shown that identity-based encryption can be obtained assuming CDH only.

In a follow up to the previous paper, this result was extended to anonymous IBE. Furthermore, it is known that encryption with keyword search can be constructed from anonymous IBE - see this paper. Combining all of the above, this gives you a CDH-based searchable encryption scheme.

All these schemes are secure under the discrete logarithm assumption when instantiated in the groups identified by den Boer. However, it should be noted that the dlog-based keyword-search scheme obtained this way is extremely inefficient and only of theoretical interest.


Cryptographic scheme where a single message cannot be decrypted but if combined with other it can be

You could accomplish this using a secret sharing scheme, which doesn't require any public key cryptography.  An $(n,k)$ secret sharing scheme allows a secret to be divided up into $n$ shares such that the secret can be recovered from any $k$ shares.  However, if you only have $k - 1$ shares you cannot recover any information about the secret.

Here, we will use a simple additive $(3,3)$ secret sharing scheme over a finite field $\mathbb{F}$.  Given a secret $s \in \mathbb{F}$, we can split it into three shares:

$$
[s]_1, [s]_2, [s]_3 \in_R \mathbb{F} \mid s = [s]_1 + [s]_2 + [s]_3
$$

Each of the three shares is uniformly distributed at random, so an adversary holding only one or two shares learns nothing about the secret $s$.  Recovering the secret from all three shares is simple:  just add them
all together.  A nice property of this scheme is that it's linear, so we can add two secrets together by adding their shares together:

$$
s_a + s_b = ([s_a]_1 + [s_b]_1) + ([s_a]_2 + [s_b]_2) + ([s_a]_3 + [s_b]_3)
$$

This means that we can do additions on the secret values while they are secret shared, and thus we can compute simple functions without revealing
the secret inputs!  In fact, there are even (complicated) protocols for
doing other operations on these secret shares, such as multiplication and exponentiation.

The protocol

Alice wants to send her secret $s_a$ and Bob wants to send his secret $s_b$ such that Charlie can only learn the sum $s' = s_a + s_b$ but not the individual values.  We assume here that all of the players are connected by secure authenticated channels.

Alice shares her secret $s_a$ by:

Keeping $[s_a]_A$ for herself
Sending $[s_a]_B$ to Bob
Sending $[s_a]_C$ to Charlie

Bob shares his secret $s_b$ the same way:

Sending $[s_b]_A$ to Alice
Keeping $[s_b]_B$ for himself
Sending $[s_b]_C$ to Charlie

Now we want each party to compute $s' = s_a + s_b$ on their local
 shares:

Alice computes $[s']_A = [s_a]_A + [s_b]_A$
Bob computes $[s']_B = [s_a]_B + [s_b]_B$
Charlie computes $[s']_C = [s_a]_C + [s_b]_C$

Finally, Alice and Bob open their result towards Charlie:

Alice sends Charlie $[s']_A$
Bob sends Charlie $[s']_B$

Charlie now has the following information:

One share of $s_a$:  $[s_a]_C$
One share of $s_b$:  $[s_b]_C$
Three shares of $s'$:  $[s']_A, [s']_B, [s']_C$

Charlie doesn't have enough shares to recover $s_a$ or $s_b$, but he can
easily recover $s'$ as:

$$
s' = [s']_A + [s']_B + [s']_C
$$

Note that this simplistic scheme is not robust, because Alice (or Bob)
could lie and provide shares $[s_a]_A + [s_b]_B + [s_b]_C \ne s_a$.  To
protect against this, you'd want to use a verifiable secret sharing
scheme so that the players can detect an inconsistent sharing.

This protocol is interactive, because it requires Alice and Bob to send their $[s_a]_B$ respectively $[s_b]_A$ values to each other.  With some
minor modifications, it could be made non-interactive.


Alternatives to Diffie Hellman and other Public Key Exchange schemes

Strictly concerning public key exchange methods, do many of these ideas exist? Dozens? Hundreds?

You have to define "exist" more precisely. If you mean widely known and/or standardized primitives, there are the obvious classic cryptosystems such as DH, RSA, ECDH, which would make dozens probably too high of a number to use.

If you mean "exist at all", including the broken ones (as well as the non-broken ones), unpublished ones* by amatuer researchers, and even minor variants of other algorithms, etc, then surely there are at least dozens. Hundreds would be surprising if we are limited to only primitives that facilitate key exchange.

You might consider some algorithms to be variations of others - this could easily influence your count by a large amount. ECDH and DH are an example. In that case, you'd be probably be interested in what different problems and assumptions are used in cryptosystems, and it would probably reduce your count back down to the order of a dozen or so at the most.

  Would commercial value exist in creating a new method?

Almost certainly not, at least in the direct and immediate sense. Cryptographic algorithm design is a poor business strategy, because you are competing with widely used, freely available, efficient, standardized algorithms. Unless you come up with something new that nobody else has but everyone wants, patenting your algorithm will probably just ensure that nobody uses it.

You could create specialized hardware for performing your algorithm very quickly or with very little power and sell or license that. But unless your algorithm is standardized and widely used, it is unlikely that it will receive much/any attention.

  To this end, is it a problem being pursued in the world today? (Classical computing - I am aware quantum is an academic direction at this time)

NIST's call for Post-Quantum algorithms actually just concluded. So research into it is indeed big at the moment, but if you are were hoping to design an algorithm and have it standardized, you probably just missed your chance.

For the curious, there were 59 KEM/PKE schemes submitted to NIST (according to the previous link).

*Disclaimer: This is my personal github, it just so happens to illustrate my point quite nicely


Excluding specific factors for Pohlig-Hellman

Suppose we have a point $P$ of order $q$ on an elliptic curve where the prime decomposition of $q$ is $q =  p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$. We also have a point $Q=kP$ and we want to find $k$.

Pohlig-Hellman algorithm

The idea of Pohlig-Hellman's algorithm is to to compute a discrete logarithm in the subgroups of prime order.

Easy case

We suppose $\alpha_i=1$ for $1\leq i \leq n$, so $q=p_1\cdots p_n$ and all primes are distinct.

Let
\begin{align}
q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j} \\
P_i & =  q_i P, \\
Q_i & =  q_i Q.
\end{align}

The point $P_i$ has order $p_i$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i$. The discrete logarithm can be computed with discrete_log on Sage or another software, and the value $k_i$ is recovered.

Do this only for primes that are in your interest, such as those that are small enough. If the value $k$ is inferior to the product of those primes, it will be found using the Chinese Remainder Theorem (with CRT([list of k_i], [list of p_i]).

Hard case

Now we suppose $\alpha_i$ is larger than $1$ for some of them. Again, we compute
$$
\begin{align}
q_i & = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j^{\alpha_j}} \\
P_i & =  q_i P, \\
Q_i & =  q_i Q.
\end{align}
$$
The point $P_i$ has order $p_i^{\alpha_i}$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i^{\alpha_i}$. Then, we write the decomposition of $k_i$ in base $p_i$:
$$
k_i = k_{i,0} + k_{i,1}p_i + k_{i,2}p_i^2 + \cdots + k_{i,\alpha_i-1}p_i^{\alpha_i-1},
$$
where $0 \leq k_{i,j} < p_i$ for $0 \leq j < \alpha_i$. To obtain $k_i$, we will get all $k_{i,j}$ one by one. First, for $k_{i,0}$, we construct the two following points:
\begin{align}
P_{i,0} & = p_i^{\alpha_i-1} P_i, \\
Q_{i,0} & = p_i^{\alpha_i-1} P_i.
\end{align}
The point $P_{i,0}$ is a point of order $p_i$ and we have the relation $Q_{i,0} = k_{i,0} P_{i,0}$. The discrete logarithm can be computed with discrete_log.

The next value $k_{i,1}$ can be found in a similar way. We compute
$$
Q_{i,1} = p_i^{\alpha_i-2} (Q_i-k_{i,0}P_i)
$$
and we have $Q_{i,1} = k_{i,1}P_{i,0}$, and discrete_log gives the value $k_{i,1}$. Then
$$
Q_{i,2} = p_i^{\alpha_i-3} (Q_i-(k_{i,0}+k_{i,1}p_i)P_i)),
$$
and we have $Q_{i,2} = k_{i,2}P_{i,0}$, and we get $k_{i,2}$, and so on, until $k_i$ is complete.

Again, do this only for primes $p_i$ that are in your interest.


This construction isn't generically secure, you need to analyze it for each blockcipher you want to use it with to see if it's secure.

For example, consider a block cipher that simply xors the key into the state between rounds. In that case your construction is equivalent to xoring the tweak into the key. This has several consequences:

Since we generally assume related and attacker controlled tweaks, this exposes the blockcipher to related key attacks. There are blockciphers which are secure with random keys, but not related keys (e.g. AES)
It enables multi-target attacks, with each tweak acting as a separate target. For example if the attacker sees a 4TiB of known plaintext, that corresponds to $2^{42-4}$ 128 bit blocks, reducing the security level of a 128 bit cipher to 90 bits.

Even if there is no direct interference between the cipher's key schedule and the tweak, the tweak gives an attacker more influence over what happens inside the cipher (assuming random keys but attacker controlled plaintext/ciphertext/tweak). To compensate for that, you need to increase the number of rounds, decreasing performance.

=> This construction might be worth a consideration when designing a new tweakable blockcipher to replace AES, but it's not something you should simply add to an existing cipher, like you can with XTS and similar constructions.


To expand on what kasperd says in a comment. This sort of thing should be handled in the protocol. This would typically be done by adding message authentication code (MAC) in the traditional encrypt-then-mac paradigm or using authenticated encryption.

So then instead of doing if (client.aeskey != server.aeskey), print Error, you would be doing if (MAC(received_ciphertext, correct_key) != received_mac), print Error (in practice your crypto library that has built in authentication checks would do this for you and return an error).

As far as

  a way for me to know what AES key the client actually used

goes. There isn't a reliable way without additional assumptions (e.g., we assume that at most 2 bits were flipped).

We traditionally think of these designs as checking for modifications of the ciphertext, but if the incorrect key is used (say due to errors in the storage mechanism or whatever), it would also detect that. The benefit of doing this is you don't have to decrypt before realizing that something is wrong. Instead, you check the MAC and if that fails, you don't decrypt at all.

There are some practical things you should take into consideration. Your best bet would be to use a commercial library. The right one will depend on your setup and needs.

Warning, the absolute wrong way to do this would be to check the padding at the end of the plaintext (assuming you are using mode like CBC that requires padding), and then return an error if the padding is incorrect. This leads to a devastating attack known as a padding oracle attack.


A "permutation", by definition, must have the same domain and range, i.e., the same possible inputs and possible outputs. You can look at it as either as a bijective function from some domain onto the same domain, or as a reordering of that domain.  Any reordering of things may also be referred to as a "permutation".

The DES "expansion permutation" is called a permutation, because it rearranges bits, but it is not a permutation at all, because it copies bits as well.

The purpose of the expansion permutation is to make sure the S-boxes have overlapping keys... for some arcane reason.  It's part of providing "confusion and diffusion", and it has nothing to do with ensuring that the encryption can be reversed.

It is the Feistel structure itself that ensures that the encryption is reversible no matter what the Feistel function $f$ is.  That gives the designers of encryption algorithms lots of leeway to do whatever they want without having to worry about using only reversible operations.

Mapping $(A,B)$ onto $(A \oplus f(B),B)$ is easily reversed just by doing it again:
$$(A \oplus f(B),B) -> (A\oplus f(B) \oplus f(B),B) = (A,B)$$

where $\oplus$ is the XOR operation.

Since DES is encryption is essentially a sequence of Feistel rounds, it can be decrypted by performing the same Feistel operations in reverse order.


Turning a 64 bit block cipher into a 128 bit block cipher

There are two well-known Encryption modes, that can construct a $mn$-bit tweakable blockciphers from a $n$-bit blockcipher ($n=64$ for DES) with $1\le m\le n$.

The older one is CMC, being not parallelizable.
It was superseeded by Encrypt-Mix-Encrypt (EME), which is parallelizable.
The basic idea of the two algorithms is to encrypt each block of input data once, then perform a nonlinear transformation on the resulting bits and feed those into the second round of blockcipher calls. This is neccessary as otherwise attacks on the schemes would be possible. For the stong linking of the two input and  output blocks, double encryption can't be avoided.

As EME requires $2m+1$ blockcipher calls, in your case $m=2$, $5$ calls to DES are neccessary for each block of data.

As DES is slow compared to AES, using AES for 128-bit modes and Threefish for larger modes is preferrable.

Besides the performance issues with EME ($>2$ times the work) there also seem to be patent issues with EME.


Is inversion always cheap with Twisted Edwards curves?

In the particular case of jubjub, it will be used in a Rank-1 Constraint System(R1CS) where inversion is cheap, costing one multiplication.

Jubjub is an embedded curve and the main purpose of developing it, is due that you can use it in a constraint system. Outside of its applications in R1CS, inversion is not cheap.

Since inversion is cheap, we can use the affine formula directly.