How fast does a pseudorandom number generator have to be in order to be competitive?

On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instructions, and ARX ciphers like ChaCha.

When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.

Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want a more precise estimate. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For ChaCha8 (which is hoped to have at least 128-bit security), the cost is $\approx113n$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).

Update on the security of ChaCha8 per this other comment: I'm reasonably confident that ChaCha8 is at least 128-bit safe, but reluctant to state much more because

ChaCha is an evolution of Salsa20, with the same number of 32-bit additions and XORs, and a faster diffusion. While that could make it safer, I'm using that as safety margin.
In the abstract of the Salsa paper, Daniel J. Bernstein recommends the 20-round version for typical applications, and presents 12 and 8-round variants as reduced-round versions recommended for applications where speed is more important than confidence.
Salsa20 was proposed for eSTREAM, in the category asking for fast software ciphers with 128-bit security. While DJB presents Salsa20/20, Salsa20/12 and Salsa20/8 as 256-bit ciphers (which they are as far as key size goes), I'm not reading him as claiming 256-bit security, especially for the reduced-round versions.
There is a known attack with complexity $\approx2^{249}$ against Salsa20/8, thus definitely it does not have security matching its key size. Again, ChaCha8 differs only by its diffusion pattern.
There is a known attack with complexity $\approx2^{153}$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.


Are there any algorithms or alternatives to create short signatures?

Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary.

Absolutely; if you want a public key signature (which, when cryptographers use the term 'signature', that's what they mean), then you can consider ECDSA or EdDSA; those can have signatures of circa 64 bytes for "128 bit security" (that is, we expect that it would take circa $O(2^{128})$ operations to generate a forgery without the private key).

On the other hand, you said that you can have both sides share the same key; that means that you can use a Message Authentication Code (MAC), which are even smaller.  There are a number known (HMAC, KMAC, CMAC); those can have very long keys, and can have very short tags (what you call a 'signature'; again, cryptographers don't use that terminology to describe the output of a MAC).  The size of the MAC is essentially determined by how unlikely you want it to be that someone can just guess the correct tag for a message; if you are happy with making this probability $2^{-128}$ per attempt, you can use a 128 bit (16 byte) tag

My suggestion: if you are happy with both sides sharing the same key, a MAC makes a lot more sense.  It's a lot simpler (easier to get right); I would personally suggest HMAC-SHA256 (although there are a number of quite reasonable alternatives avaiable)


Is there any difference between NIST and SECP curves in-terms of their algorithms and implementation?

Please check https://tools.ietf.org/search/rfc4492 - espessially, the "Appendix A.  Equivalent Curves (Informative)" part.

For example: NIST P-256 is refered to as secp256r1 and prime256v1. Different names, but they are all the same.


Broadcast encryption not using symmetric keys

Asynchronous Ratcheting Tree (ART) is an n-way Diffie-Hellman key exchange. The group initiator selects members and instantiates the tree, revealing only public information such that each other member may recompute the group shared key. Users may update their key-share as a measure to implement forward secrecy of a later compromise of their long-term static identity key.

As you're interested in at least revocation, you'll want to extend ART with dynamic groups which introduce the operations: join, leave, partition and merge.

Leaving is done willingly, however, partitioning and merging can enable selective revocation, computing partial tree updates without recomputing a whole new tree (which is not too expensive anyway).

With the group key you now use symmetric authenticated encryption.

Edit: You may additionally use the group key to derive a shared asymmetric identity such that anyone may encrypt messages to the group; but only group members (1-of-n) may decrypt the messages. As the group membership changes, the encrypting user is responsible for using the latest identity to encrypt for.


Is choosing $1$ as a public exponent valid in RSA?

TL;DR: it is a matter of conventions and context that $e=1$ is allowed or not.
Definitions of RSA vary:

The original RSA article asks to first choose the private exponent $d$ as « a large, random integer which is relatively prime to $(p−1)\cdot(q−1)$ », then to compute $e$ as « the “multiplicative inverse” of $d$, modulo $(p−1)\cdot(q−1)$ ». This makes it extremely improbable that $e=1$, but allows it. Later descriptions of RSA tend to choose $e$ first.
PKCS#1 v1.5 / RFC 2313 asks to « select a positive integer $e$ as its public exponent ». That allows $e=1$.
PKCS#1 v2.0 / RFC 2437 states « the public exponent $e$ is an integer between $3$ and $n-1$ satisfying $\gcd(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ ». That does not allow $e=1$, but still allows $e=\lambda(n)+1$ and $e=(p−1)\cdot(q−1)+1$, and perhaps a few other values of $e$ that are such that $x\mapsto x^e\bmod n$ is the identity function over $[0,n)$ just as it is for $e=1$. PKCS#1 v2.2  has the same prescription for $e$.
FIPS 186-4 states « the exponent $e$ shall be an odd positive integer such that $2^{16}<e<2^{256}$ », and that forbids $e=1$. Combined with $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ and a minimum for $d$, that makes it impossible $x\mapsto x^e\bmod n$ is the identity function.

For computer implementations, that depends on if an explicit test against $e=1$ is present or not. Both exist.
Sometime, public keys with $e=1$ or $e=\lambda(n)+1$ (which is more rarely disallowed by software) are used in test keys, or in reverse-engineering, in order to allow easy analysis of padding. Of course, such keys must not be used for encryption or signature of valuable data.


How to calculate Trace function for a point on an elliptic curve

Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. In this case, $t$ is called the trace of $E$.

Also, $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $$V_0 = 2, V_1 = t,\text{ and }V_n = V_1V_{n−1}−qV_{n−2}$$ for $n ≥ 2$. In your question it's enough to compute $V_{431}$.

For more details, see Guide to Elliptic Curve Cryptography.


For all standard modes, AES isn't secure at all if you reveal the key; even if you keep the IV hidden.

Exactly how this works out varies between modes; for CBC mode, the attacker will be able to decrypt the entire text except for the first block (well, last block because of your reversing the file), even if you didn't give him an IV.  The same goes for CFB mode.

As for OFB and CTR modes, the 'IV update' function is reversible and independent of the message; hence revealing any intermediate IV will allow the attacker to decrypt the entire message.

What you want is unusual (at least, I never heard of the requirement before), and it's not surprising the existing modes can't handle it.

One idea which might work out is a varient of OFB mode using SHA-256 (for example), that is:

$IV_{i} = SHA256(IV_{i-1})$

$C_i = P_i \oplus upper128(IV_i)$

where $P_i$, $C_i$ are the i-th plaintext and ciphertext blocks (128 bits), and $upper128$ extracts 128 bits of its input.

The idea is:

The IV update function is noninvertible, hence the attacker does not have immediate access to previous states
Even if the attacker has a guess for the previous plaintext block, he cannot validate it.  That is, if he is given $IV_i$, knows $C_{i-1}$ and has a guess for $P_{i-1}$, he can't determine if his guess is correct; that guess tells him what 128 bits of $IV_{i-1}$ would be, but $IV_{i-1}$ has 128 bits he isn't given, and that's too much to search over).

Now, this is nonstandard, nonvetted and slow compared to AES-based transforms.  However, it might address the problem you're looking at.


By uniqueness of factorisation, this problem is well defined. If $e$ is uniformly distributed as you suggest it must be uniformly distributed in some finite range, say in $(1,2^N)$. Rewrite the equation as
$$
v \log_2 b = \log_2 e.
$$
Note that the random variable $Z=\log_2 e$ is distributed in $(0,N]$ with a highly nonuniform distribution exponentially biased towards the high end, namely
$$
\mathbb{P}(Z\in (s-1,s)) \propto 2^{N-s+1}
$$
while the primes from which $b$ is drawn are distributed (by the prime number theorem) result in the distribution
$$
\mathbb{P}(W \in (f-1,f)) \propto
\frac{\log(f-1)}{\log f} 2^{N-f+1}
$$
where $W=\log_2 b.$ Note that $s,f$ are reals not integers.

One can set up a faster than brute force search algorithm given $v$ by first searching for $(f,s)$ pairs with $s=f/v$ starting with $f=N$ and decreasing $f$ while testing the nearest integer to $2^{f/v}$ for primality.

Rewriting the original equation $b^v=e$ as the approximation
$$
\left| \frac{1}{b}-\frac{e}{b^{v+1}}\right|<\frac{1}{2 b^{v+1}},
$$
a $v+1$ step continued fraction approximation will be enough to run, prior to primality testing the nearest integer to the approximation.


Dmitry's suggestion to use AES in counter mode sounds good to me, assuming that you only need confidentiality, and not integrity protection.  (Counter mode, like most stream ciphers, is very malleable.)

One trick you can use to save a bit of space is to use the current time as part of the nonce.  (Of course, this only works if your devices have fairly well synchronized clocks.)  To make this scheme more robust against slight clock skew, you should transmit a few of the least significant bits of the timestamp as part of the message, so that the receiver can adjust their timestamp to match it.

For instance, let's say that your devices have clocks that are assumed to be synchronized to within one minute of each other, that they'll need to transmit at most 256 messages per second, and that there are at most 256 devices communicating with each other.  Then you could use the following four-byte header for each message:

Byte 1: Sender ID.
Byte 2: Receiver ID.
Byte 3: Eight least-significant bits of the current time (in seconds since epoch).
Byte 4: An 8-bit message counter, reset whenever byte 3 changes.

This header would be transmitted in the clear, at the beginning of each message.  The remaining 28 bytes can then contain data encrypted using AES-CTR (or some other stream cipher), with a 16-byte IV constructed as follows.

Bytes 1–8: A unique 8-byte identifier for this group of devices.
Bytes 9–10: Sender and receiver IDs (from header bytes 1 & 2; included to ensure that IVs are not reused between different pairs of devices).
Bytes 11–14: A 32-bit timestamp (seconds since epoch; byte 14 = header byte 3).
Byte 15: Message counter (header byte 4).
Byte 16: Within-message block counter (really needs just one bit for two-block messages, but using a whole byte leaves some expansion room).

For the sender, constructing this IV is straightforward.  For the receiver, the only complication is that they'll need to reconstruct the sender's timestamp for bytes 11–14, by picking the nearest time that matches the 8-bit timestamp in the header.  (This might be either in the past or in the future, due to clock skew.)  One way to implement that is as follows:

Initialize message timestamp to current time.
Replace lowest 8 bits of message timestamp with byte 3 from message header.
If message timestamp is more than 128 seconds in the past, increment it by 256 seconds.
If message timestamp is more than 128 seconds in the future, decrement it by 256 seconds.

Optionally, if the reconstructed timestamp is off by more than 64 seconds (or so), the receiver may wish to initiate a time resynchronization protocol.  Note that, with any time resynchronization scheme that potentially involves adjusting clocks backwards by a full second, either the devide ID or the group ID should be changed to prevent IV reuse.

In cases where the clock skew is only slight, it may be preferable to use a gradual adjustment scheme (i.e. telling the skewed device to count seconds a little slower or a little faster) that doesn't involve sudden time jumps.  Or, alternatively, you could always have all the devices adjust their clocks foward to match the fastest-running clock (which might gradually shift them away from "true" time, but would keep them in sync without backwards time jumps).  One way to handle this would be to separately track "true time" and a guaranteed monotonely increasing "message time", storing an offset between these.

Of course, you can adjust this header depending on your timing, message rate and device count needs.  For example:

If you have good clock synchronization, you can increase the clock resolution (to, say, one millisecond) to allow a higher message rate.
If all your devices communicate with a single central controller (and not directly with each other), you can replace the sender and receiver IDs with a single device ID and a single direction bit indicating whether the message is to or from the controller.  (Technically, you don't even need to transmit the direction bit, since the receiver will always know what it should be; but you do still need to include it in the IV.)
If your transmissions are very bursty, you can use more bits for the message counter, and less for the truncated timestamp.  Conversely, if your messages are sent at regular intervals, you can use less bits for the message counter, or even eliminate it entirely.  (Technically, you only need one or two timestamp bits, while the rest can be part of the counter; however, the higher the resolution of the message timestamps is, the easier and safer it is to recover if, say, your device suddenly loses power and forgets the current message counter value.)

The important thing is to ensure that, no matter what happens, the same IV is never used twice.  Also, since CTR mode does not offer integrity protection, you should make sure to design your underlying protocol to be robust against both garbage messages, and messages that might have been deliberately modified by an attacker.  For certain critical messages (like time synchronization commands, or other messages that could be used to adjust encryption or other essential operation parameters), this may require the use of a MAC at a higher protocol level.


Can ECC correctness issues allow “remote attackers to spoof ECDSA signatures”?

Glancing through the Mozilla notes, it would appear that it would actually be infeasible to generate a forged signature (that is, not involving the private key) that would tickle this bug.  In fact, if someone could generate a signature that would tickle this bug, they could deduce the private key (and so wouldn't need exploit this implementation flaw).

During ECDSA signature generation, the verifier creates two EC points $u_1 G$ and $u_2 Q$, where $Q$ is the public key, and $u_1, u_2$ are two integers computed as a part of the verification problem.  The verification routine then adds these two points, apparently, the bug happens if either $u_1G = u_2Q$ (the addition is actually a point doubling), or if $u_1G = -u_2Q$ (the result of the addition is the neutral element).

However, if either is true, then $\pm u_2^{-1} u_1 G = Q$, and hence $\pm u_2^{-1} u_1$ is the private key.  Hence, if the attacker can generate a signature that satisfies either of these two conditions, he can compute $u_1, u_2$, and then directly recover the private key.  And, with the private key, the attacker can sign anything he wants.

Now, Mozilla was quite correct in fixing this bug; however it doesn't look like it's exploitable.


Does the key schedule function need to be a one-way function?

As fgrieu already pointed out, using a OWF in the way you describe would make the key schedule not efficiently invertible (or even not invertible at all), meaning you would need more memory/chip space to store the user-input key in order to efficiently encrypt more than one block.

In terms of other implications, if the key-state update function $e_n(\cdot)$ is non-surjective then the later round keys will have less entropy than the user-input key, and hence may be guessed with less effort than with the current AES key schedule.  This could make the last rounds easier to peel off.

However, if $e_n(\cdot)$ is such that every output bit is a high degree non-linear function of every input bit, then any such loss of entropy would likely be very difficult to exploit, and also would likely make related key and biclique attacks more difficult.

You should also be aware that OWFs can be used in the key schedule in a different way than you describe -- i.e. as round key extractors instead of as key-state update functions.  So you might have a permutation (perhaps even a linear one) to update the key-state between each round, but then derive each round key from the key-state using a OWF.  As a concrete (but slow) example, your key-state update function might be to add 1 (or some other constant) to the user-input key between each round, and then extract the current round key from that by hashing the key-state with a cryptographically secure hash function like SHA-256.  As a much faster example, Serpent uses a linear key-state update function, and non-linear round-key extractors (though in that case they are non-linear permutations using the Serpent s-boxes instead of OWFs).


Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible?

What the authors of the paper cited by you certainly mean by secure is "treat the hash function to $G_2$ as a random oracle". The problem is that hashing to $G_2$ can only be realized by taking some point in the group and multiplying it with a scalar (which is for instance the output of a full domain hash mapping to integers in $Z_{ord(G_2)}^*$). See for instance here for fast methods, which, however, also do not yield "secure" hashing to $G_2$.

It is best explained by an example why such simple hash functions (multiply scalar with some fixed point) can yield to insecure cryptographic protocols. In the example below, I use a type 1 setting for illustration purposes (BLS signatures in type 2 pairings are still secure under a slighly different assumption - co-CDHP instead of CDHP - since one can use a secure hash function $H$ to $G_1$).

The security of BLS essentially relies on treating the hash function $H$ as random oracle, i.e, the output of $H$ cannot be determined unless by querying $H$.

Let us take a look at the BLS setting, where we have $G, G_T$ to be prime order $p$ groups and let $P$ be a generator of $G$ and $e:G\times G\rightarrow G_T$.

Then the private key $x$ is a random element of $Z_p$ and the public key is $X=xP$.

Signing a message $m$ amounts to computing $S=H(m)$, where $H:\{0,1\}^*\rightarrow G$ is modelled as a random oracle that maps from strings to elements of $G$, and setting the signature as $\sigma=xS$.
Signature verification when given $m$ and $\sigma$ is to check if $e(H(m),X)=e(\sigma,P)$.

Note that if we would make an extremely bad choice and choose an "insecure" $H$ as $H(m):=H'(m)P$ where $H':\{0,1\}^*\rightarrow Z_p^*$ is a secure hash function, then anybody can forge signatures by computing $\sigma=H'(m)X$ for arbitrary messages (this is essentially the strategy of simulating the random oracle used in the security proof).

So, the signature scheme (and other pairing based protocols that require $H$ to be modeled as a random oracle) live from the fact that the output of $H$ is unpredictable and in particular the discrete log with respect to the generator is not known.

A type of pairings that allow to securely hash into $G_2$ and where there is also an efficiently computable homomorphism from $G_2$ to $G_1$ are so called type 4 pairings.


Help with terms: hash function and a pseudorandom function

There's two problems with your question:

The term "hash function" is not as clearly defined as you think.
The most common definition among cryptographers does not imply pseudorandomness.

Generally, you want to be very careful in distinguishing between:

Security definitions, like:

Pseudorandom function
Collision resistant hash function

Cryptographic algorithms, like:

SHA-2
HMAC
AES

Arguments that some given algorithm meets specified security definitions.

"Pseudorandom function" and "collision-resistant hash function" are security definitions:

A pseudorandom function is a keyed function that an adversary who doesn't know the key cannot efficiently distinguish from a randomly selected function over the same domain and range.
A collision-resistant hash function (CRHF) is a function that features:

Compression (turns variable-sized inputs into fixed-size outputs);
Preimage resistance
Second preimage resistance
Collision resistance

Now, you need to understand that the security definition for collision-resistant hash functions does not imply the one for pseudorandom functions:

A pseudorandom function need not compress its input.  Example: AES, or any block cipher (which are designed to be pseudorandom permutations on fixed size blocks).
A function that provides preimage, second preimage and collision resistance may nevertheless be efficiently distinguishable from a random function.

This means that if all that you assume of your hash function is that it meets the CRHF requirements, you cannot conclude that it also provides the PRF requirements.  First because CRHFs may be unkeyed; second because a keyed CRHF may be distinguishable from a random function.

In practice, however, the common hash function algorithms that we use are argued (or just assumed) to meet not just the collision-resistant hash function definition, but also:

To be suitable building blocks for a pseudorandom function, using HMAC or some other construction;
Often they're also treated as random oracles: a public function (no secret key) that produces random outputs.

Some cryptographers get nervous when you assume #2, though, because they'd like to minimize the assumptions that we make about our primitives' security.


Here's a simple Python implementation.
def anf(s):
    s = list(s)
    for i in range(n):
        for j in range(0, 2**n, 2*2**i):
            for o in range(2**i):
                s[j+o+2**i] ^= s[j+o]
    return s

def size_reduce(lst):
    res = set()
    for u in lst:
        if not any(u != v and u & v == v for v in lst):
            res.add(u)
    return sorted(res)

def expand(lst):
    res = set()
    for v in range(2**n):
        if any(v & u == u for u in lst):
            res.add(v)
    return sorted(res)

n = 4
# GIFT GS
sbox = 0x1, 0xa, 0x4, 0xc, 0x6, 0xf, 0x3, 0x9, 0x2, 0xd, 0xb, 0x7, 0x5, 0x0, 0x8, 0xe

# calculate ANFs of products
dppt = [set() for u in range(2**n)]
for v in range(2**n):
    a = anf([int(y & v == v) for y in sbox])
    for u, take in enumerate(a):
        if take:
            dppt[u].add(v)

# propagate larger monomials to smaller ones
for u1 in range(2**n):
    for u2 in range(u1):
        if u2 & u1 == u2:  # u2 \prec u1
            dppt[u2] = dppt[u2] | dppt[u1]

# remove redundant ones
dppt = [size_reduce(lst) for lst in dppt]
print("Reduced:")
for u, lst in enumerate(dppt):
    print(f"{u:04b}:", *[f"{v:04b}" for v in lst])

# or include all redundant ones
print("All:")
dppt = [expand(lst) for lst in dppt]
for u, lst in enumerate(dppt):
    print(f"{u:x}:", *[f"{v:x}" for v in lst])

Output:
Reduced:
0000: 0000
0001: 0001 0010 0100 1000
0010: 0001 0010 0100 1000
0011: 0001 0010 1100
0100: 0001 0010 0100 1000
0101: 0010 0101 1000
0110: 0011 0100 1001 1010
0111: 0101 1011 1110
1000: 0001 0010 0100 1000
1001: 0011 0100 1000
1010: 0011 0100 1000
1011: 0110 1011 1101
1100: 0011 0100 1000
1101: 0011 0101 1000
1110: 0100 1001 1010
1111: 1111
All:
0: 0 1 2 3 4 5 6 7 8 9 a b c d e f
1: 1 2 3 4 5 6 7 8 9 a b c d e f
2: 1 2 3 4 5 6 7 8 9 a b c d e f
3: 1 2 3 5 6 7 9 a b c d e f
4: 1 2 3 4 5 6 7 8 9 a b c d e f
5: 2 3 5 6 7 8 9 a b c d e f
6: 3 4 5 6 7 9 a b c d e f
7: 5 7 b d e f
8: 1 2 3 4 5 6 7 8 9 a b c d e f
9: 3 4 5 6 7 8 9 a b c d e f
a: 3 4 5 6 7 8 9 a b c d e f
b: 6 7 b d e f
c: 3 4 5 6 7 8 9 a b c d e f
d: 3 5 7 8 9 a b c d e f
e: 4 5 6 7 9 a b c d e f
f: f


How do we guarantee plaintext is coprime in RSA?

If you can efficiently find a $P$ that is not coprime to $N$, then you can easily factor $N$ (use GCD). If you know the factorization of $N$ (say $N=pq$), you can easily find a $P$ that is not coprime to $N$ ($kp$ for some constant $k$).

This established the fact that finding $P$ not coprime to $N$ and factoring are equivalent problems.

Now, how many numbers are there less than $N$ that are not coprime to $N$? Well, we know that there are $\varphi(N)=(p-1)(q-1)$ numbers less than $N$ that are coprime to $N$. So, there are $N-\varphi(N)=pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ such numbers. This is actually a fairly large number (for 2048 bit $N$, $p$ (and $q$) would each be 1024 bits). But, it is minuscule in comparison to $\varphi(N)$, which is the number of numbers that are coprime. So, a random number is, with overwhelming probability, not coprime to $N$. At the moment, the best method for finding such a $P$ is to first factor $N$.

So, to answer your question, you don't have to worry about $P$ not being coprime to $N$. If you ever find one that isn't, bad things will happen. Your odds of a $P$ not being coprime are smaller than winning the lottery and getting struck by lightning twice, all in the same day.


To prove $r \cdot f_1 +f_2 \cdot (s+1)$ is secure

First, a fact.

For some polynomial $f_x$ and some random polynomial of the same degree, say $t$, an adversary given only $f_x+t$, knows no additional information about $f_x$. Basically (due to the finite ring), this operation is the same thing as the one-time-pad.

On to the problem at hand.

Let $f_3=f_2\cdot(s+1)$. Since $f_2$ and $s$ have the same degree, we know that $f_3$ has double that degree. Say the degree of $s$ (and $f_2$ and $f_1$) is $d$, so the degree of $f_3$ is $2d$. Since $2d>d$ (when $d>0$), if you could prove that $f_3$ was a random polynomial, then clearly an attacker given the values you specified above would learn no additional information about $f_1$. Problem is, $f_3$ is not a random polynomial since the coefficients would have interdependencies. For example (using $\mathbb{Z}_{11}$), let $f_2=3x+5$ and $s=7x+2$, then $f_3=(7*3)x^7+(2*3+5*7)x+(5*2)=10x^2+8x+10$. The terms (before I reduced the multiplication) have interdependencies.

Since $f_3$ is not random, Adding $f_3$ to another non-random polynomial ($f_1$ or $r\cdot f_1$ in your case) would not be indistinguishable from a random polynomial. So, I don't think you can make an information theoretic argument.


It cannot. The AES-NI extensions add six new instructions used to accelerate AES. Whirlpool uses a Rijndael-based cipher as its round function. From a page on the hash, the cipher works as so:
The Whirlpool hash function

WHIRLPOOL uses Merkle-Damgård strengthening and the Miyaguchi-Preneel hashing scheme with a dedicated 512-bit block cipher called $W$. This consists of the following. The bit string to be hashed is padded with a '1'-bit, then with a sequence of '0'-bits, and finally with the original length (in the form of a 256-bit integer value), so that the length after padding is a multiple of 512 bits. The resulting message string is divided into a sequence of 512-bit blocks $m_1$, $m_2$, ... $m_t$ which is then used to generate a sequence of intermediate hash values $H_0$, $H_1$, $H_2$, ... $H_t$. By definition, $H_0$ is a string of 512 '0'-bits. To compute $H_i$, $W$ encrypts $m_i$ using $H_{i-1}$ as key, and XORs the resulting ciphertext with both $H_{i-1}$ and $m_i$. Finally, the WHIRLPOOL message digest is $H_t$.

This can be expressed mathematically where $\mu$ maps input to the matrix $M_{8 \times 8}[\operatorname{GF}(2^8)]$, $W$ is the 10-round, 512-bit Whirlpool block cipher, $IV$ is a string of 512 0-bits, $M$ is the full message with a length of $t$ blocks, $m_i$ is a 512-bit block from $M$ at position $i$, and $m_t$ contains up to 512-bits of Merkle-Damgård padding (a 1-bit, as many 0-bits as necessary to pad the block to an odd multiple of 256, and a 256-bit right-justified binary representation of the total length of $M$).
\begin{align}
\eta_i &= \mu(m_i)\\
H_0 &= \mu(IV)\\
H_i &= W_{H_{i-1}}(\eta_i) \oplus H_{i-1} \oplus \eta_i\\
\operatorname{Whirlpool}(M) &\equiv \mu^{−1}(H_t)
\end{align}
The $W$ cipher and the $\mu$ function are described in more detail in the Whirlpool paper.
The AES-NI extension
To see whether or not AES-NI can accelerate $W$, we have to look at the purposes of each instruction. Reading through the Intel whitepaper on AES-NI, the instructions do the following:

AESENC performs a single round of encryption using the provided round key. It performs the ShiftRows, SubBytes, and MixColumns steps on the data. The MixColumns step involves using the $\operatorname{GF}(2^8)$ polynomial $x^8 + x^4 + x^3 + x + 1$, whereas Whirlpool uses $x^8 + x^4 + x^3 + x^2 + 1$. In addition, SubBytes uses the AES S-box which Whirlpool does not use.* The different polynomial alone makes this instruction unusable for Whirlpool.

AESDEC is identical to the above, but uses the inverse steps (i.e. the steps InvShiftRows, InvSubBytes, and InvMixColumns). The Whirlpool block cipher does not involve decryption, making this instruction useless.

AESENCLAST is the same as AESENC, but it is intended for the final round of encryption. The primary difference is that it does not perform the MixColumns step. Unfortunately, it still performs SubBytes which uses the AES S-box, not the Whirlpool S-box.

AESDECLAST is identical to AESENCLAST, but runs the inverse transforms.

AESIMC passes the round keys through the InvMixColumns transformation to make them suitable for decryption. This still involves the incompatible polynomial, so it would not work even if Whirlpool could benefit from accelerated decryption.

AESKEYGENASSIST implements the AES key schedule. It takes the cipher key and generates the necessary round keys. Whirlpool does not use a dedicated key schedule. Each round function acts as the key schedule, creating the round keys for the next round.

Now, even if these instructions could be used for Whirlpool's block cipher, they only operate on 128-bit blocks (although apparently it is possible to do 256-bit blocks as well, according to section 2.1 of this paper). Whirlpool's block cipher uses 512-bit blocks. The instructions would not work.
In summary, the instructions for encrypting and decrypting rounds are completely incompatible with Whirlpool. The only other instruction performs the AES key schedule, which Whirlpool does not use. You may be able to modify Whirlpool to use the unmodified AES rounds, but then it would no longer be Whirlpool. If you do need a hardware-accelerated cryptographic hash however, you could use the new Intel SHA extensions. These are used to accelerate SHA-1 and SHA-256. Alternatively, you could use a dedicated hashing algorithm that is designed to be accelerated by AES-NI, as is shown in this paper.
* Just because a cipher uses a different S-box than AES does not automatically disqualify it from being accelerated by AES-NI's implementation of SubBytes, if the S-box is similar enough. This is the case for Camellia, for example.


Understanding certificates for public keys with subkey

The public key block is a structure that contains one public pgp key. However the structure does not only contain the public key, but more information such as public key algorithm, key expiration time and so on. Depending on what "key-id" you used with your export command, the public key block will contain the public key correponding to that "key-id".
It might be useful to see what information your pgp key contains so that you can extract your public key from it. You could use a site such as https://cirw.in/gpg-decoder/ to check all information contained inside your public gpg key block.
You could use your private key corresponding to your public key for which you created a certificate to sign a message (e.g. with OpenSSL). Then you could use the certificate, more specifically the public key inside that certificate, to check if the signature you created can be successfully verified. If so, you can be sure that the certificate matches your private gpg key.


Using last 64 bit of aes as hash of the message vs first?

Short answer: neither.

I'm going to assume the length of M is 128 bits (one AES block) so we won't be talking about block cipher modes.

A hash is useful to verify the integrity of the message. It is meant to be verifiable either without (plain hash) or with (MAC) a key. In your scenario, it is neither: only someone with the plaintext can compute the hash again (in which case: why encrypt?).

With your proposed solution (either first or last 64 bits), you cannot tell if the ciphertext or plaintext have been altered. The only way would be to decrypt the message and have some way of verifying the validity of the plaintext after decryption.

What you probably want is a message authentication code.


How can we sign a contract digitally between two parties?

No.  Cryptography alone cannot solve this problem.

Solving this problem requires a combination of technical (e.g., cryptography, systems security) and non-technical (e.g., legal, regulatory, contractual) solutions.  Even the technical part is not solely a cryptography question; it as much about systems security.


I read ECB is bad because the same plaintext outputs the same ciphertext. Isn't that a requirement of a cipher?

Indeed, ECB is such that encrypting twice the same plaintext leads to the same ciphertext. Even worse, encrypting a plaintext containing twice the same plaintext block leads to a ciphertext containing twice the same ciphertext block. Either is a disadvantage because it goes against the ideal of a cipher: depriving the adversary from any knowledge about the plaintexts, with the sole exception of length.

An example of why that's a drawback is if we encipher plaintexts consisting of votes cast in an election, with plaintext N for a no vote, Y for a yes vote. With any cipher such that encrypting twice the same plaintext leads to the same ciphertext, someone intercepting the ciphertexts will see two values, and can determine each vote (assuming a single vote is known, or it is known that Y outnumbers N).

If a cipher has the property that plaintext and ciphertext have the same size for any unconstrained plaintext, then indeed (in order for plaintext to be exactly decipherable, and by a counting argument) the cipher is bound to have said drawback. Hence modern ciphers have a ciphertext larger than the plaintext (typically for symmetric ciphers: by the Initialization Vector's size at least).

Addition per comment: an example of a cipher not bound to generate the same ciphertext when enciphering twice the same plaintext would be $\operatorname{AES}$ in counter mode with key $K$

encryption:

generate a 128-bit Initialization Vector $C$ at random, using the computer equivalent of tossing a coin 128 times, and outputs $C$ as the first 128 bits of the ciphertext
while remaining plaintext length $l>0$

output the eXclusive-OR of the next $\max(l,128)$ bits of plaintext and as many of the leftmost bits of $\operatorname{AES-ENC}_K(C)$
$C\gets C+1\bmod2^{128}$ (increment the counter)

decryption:

set $C$ as the first 128 bits of the ciphertext
while remaining ciphertext length $l>0$

output the eXclusive-OR of the next $\max(l,128)$ bits of ciphertext and as many of the leftmost bits of $\operatorname{AES-ENC}_K(C)$
$C\gets C+1\bmod2^{128}$ (increment the counter)


Can I Modified AES for enhaced security of WPA-2?

No.

AES isn't a weak point of WPA2. Modifying it would almost certainly weaken it, outside trivial stuff like adding more rounds or other things consistent with the Rijndael cipher it standardizes. And even these mods can introduce insecurity if things like hardware acceleration can no longer be used and it ceases to be constant time.

More simply both AES and WPA2 are fixed, published standards. AES is used in WPA2, modified AES isn't. Once you modify AES it's no longer AES. Once you modify WPA2 it's no longer WPA2.


How can we find Public key have only 8 or 16bits? How many messages does Eve need to know the Public key in RSA?

If the plaintext is easily recognizable, one message is sufficient. Simply brute force all 16 bit RSA keys, decrypt the ciphertext. If the result "looks" like plaintext, you have found the key. A 16 bit RSA keyspace should be easy to brute force.


TLS 1.2 is still secure or should we move to TLS 1.3?

According to who? According to NCSC (the Dutch center for cyber security) for instance, TLS 1.2 is still considered "good", but it does go on to specify which cipher suites and specific configuration options are still considered "good".
This is kind of the problem with TLS 1.2: it has become a hodgepodge of different algorithms, key agreement schemes, certificate status, signature formats, bulk ciphers, hash algorithms and whatnot. So specifying that TLS 1.2 is good enough is basically hiding all the problems that are associated with it. TLS 1.2 is as good as the options that are chosen, and making sure that all the configuration / implementation pitfalls are avoided.
TLS 1.3 has been defined to strip most if not all of these problems away, and be build upon the best practices for popular encryption algorithms. It is both very similar to TLS 1.2 and different path from 1.2 in that sense. We've come a long way, and it is likely that TLS 1.3 will be more secure for longer than TLS 1.2 in a generic sense.
Is TLS 1.3 perfect? No, problems have and will be found. But it is generally more secure, more performant it has certainly a lot fewer options compared to TLS 1.2 that are certainly not secure or that are likely to become security issues in the future. There are still things like the mentioned 0-RTT and PSK that are relatively dangerous to use. In that sense TLS 1.3 in itself is not a secure solution all by itself either; specific usage scenarios still have to be considered.
That all said, it is certainly possible to configure TLS 1.2 in such a way that the protocol is still considered secure, or at least not broken fundamentally. So in that sense I suppose you could argue that there is no pressing need to move to TLS 1.3, as long as your choices for TLS 1.2 are considered sound.
Do note that this also kind of assumes that the inherent complexity of TLS 1.2 is not a problem in itself, and that's certainly debatable as well.


MitM with regard to unauthenticated clients

but can pretend to be the client and see what the client is sending

No, the eavesdropper can't see what either side is sending except the ciphertext and size of the ciphertext.
To eavesdrop on any connection where the server is authenticated, the eavesdropper has to be able to convince the client that he is the server, which the eavesdropper cannot.

Doesn't that mean the server might be talking to an eavesdropper who inserted himself in the middle

Any internet middle box can do that.

and the eavesdropper can't decrypt server responses

True, and the eavesdropper can't decrypt client requests either since the eavesdropper doesn't have the session key.

but can pretend to be the client and see what the client is sending

Again, the eavesdropper doesn't have the session key, he can't do that.


Any efficient text-based steganographic schemes?

My understanding is that the three most popular approaches to "steganography using text as a cover" are:

1 Generate a completely new text by picking one word at a time from a dictionary, using the ciphertext bits to select which word.

Pick words in ways that, at first glance, look like real English sentences, using Markov chain algorithms.
Weihui Dai.
"Text Steganography System Using Markov Chain Source Model and DES Algorithm".
(2010).
H. Hernan Moraldo.
"An Approach for Text Steganography Based on Markov Chains".
(2012).
"Steganographic Markov Chains".
(2008).
Anna Lysyanskaya and Mira Meyerovich
"Provably Secure Steganography with Imperfect Sampling"
(2006). Etc.
For a given dictionary, picking words with uniform distribution gives you the most ciphertext bits per word,
but it's pretty obviously not real English text. Still, these schemes are very popular for sending raw bits over systems (like email, voice, etc.) designed for text: NATO phonetic alphabet, PGP word list, the S/KEY dictionary, the Diceware dictionary, etc.

2 Take some fixed text, and send exactly the same series of letters as in the original text, adding the ciphertext bits by modifying the presentation of that text in ways that we hope the warden doesn't notice.

Use two slightly different typefaces as in Bacon's cipher (1605).
Add space characters to the end of lines, where they are usually invisible, as in SNOW (1996?).
Vary the spacing between words; nudge the letters left-right (nonstandard kerning) or up-down.
Etc.

3 Take some fixed text, and slightly modify the words in ways that we hope the warden doesn't notice.

The receiver takes each word, looks it up in the agreed-on thesaurus; if the thesaurus shows 4 synonyms, the receiver decodes that word into 2 ciphertext bits. Nanhe, Kunjir, Sakdeo. “Improved Synonym Approach to Linguistic Steganography”. Shirali-Shahreza. "A New Synonym Text Steganography". Chang and Clark. "Practical Linguistic Steganography using Contextual Synonym Substitution and Vertex Colour Coding".
The receiver looks for certain "key words", ignoring all the other words.
The receiver decodes a few bits per sentence by noticing which of several ways (all with equivalent meaning) of arranging the words in that sentence were selected. Grothoff; Grothoff; Alkhutova; Stutsman; and Atallah. "Translation-Based Steganography" (2005). a
Etc.


How does the size of the prime affect Elliptic Curve Bit Security?

Elliptic curve security relies on the hardness of discrete logarithm on that curve. (Well, that's a simplification, but this will do for this answer.) When the curve contains N points, it takes an effort of roughly sqrt(N) "elementary operations" to break discrete logarithm.

A prime p of "k bits" means that p is less than 2k, but greater than 2k-1. The number of points on a curve defined over the field of integers modulo p will be close to p (that's Hasse's theorem). Thus, if the prime p has length k bits, the breaking effort will be on the order of the square root of 2k operations, i.e. about 2k/2. It is usually considered that the current, absolute barrier on that which is technologically feasible is between 280 and 2100, so a safe curve would need a prime size of at least 160 to 200 bits. The "ssc-192" curve falls in that domain, so it could be deemed "probably secure".

Cryptographers are fashion victims, and thus always want powers of 2; thus, they will usually ask for "128-bit security" which then translates to a 256-bit prime p.

See this site for a lot of pointers to information on the concept of key strength.


We currently have no way to prove that a specific PRNG is cryptographically secure.  In fact, we currently cannot prove that there exists a cryptographically secure PRNG (!).

If you scale back the requirement from "mathematical proof" to "something we generally accept", there's still no way for an automated test to verify that a specific output is cryptographically secure.  Yes, it can run a series of statistical tests, and verify that, from that perspective, it looks like what we expect a random stream to be.  However, that is not sufficient; to be cryptographically secure, we require that someone cannot devise a clever test (using knowledge of how the PRNG works internally) that distinguishes it from random.  The hard word (for an automated test) is the word "clever"; automated tests have great difficulties with "cleverness".

Here's a little thought expirement that demonstrates one of the subtleties; suppose I generate a PRNG using AES in counter mode; that is, I pick an initial 128-bit value $N$ and an AES key $k$, and produce the sequence:

  $AES_k(N), AES_k(N+1), AES_k(N+2), AES_k(N+3), ...$

If I pick $k$ and $N$ randomly, and keep them secret (and keep the number of outputs within the above sequence to significantly below $2^{64}$), then this is, as far as we know, a cryptographically secure PRNG.

However, suppose I do the same, but instead of picking $k$ randomly, I use a fixed public value.  In that case, the sequence is known not to be a CSPRNG; it is easy to test (using two adjacent outputs), whether the output is from this specific PRNG.

Here's the point: publishing $k$ or keeping it secret does not actually change the output.  However, even though it doesn't, it does change whether we have a CSPRNG or not.

So, going back to your question: we do have things that we believe are CSPRNG (such as the above AES counter mode with a secret key); why do we believe those?  Well, that's because we have clever people (that is, people that have demonstrated skill in finding clever ways to break other CSPRNGs) analyze the PRNGs.  It's not an ideal solution (it's possible that there is a way to break it, and our clever people missed it); however it's better than any other way we have.


Given a message and signature, find a public key that makes the signature valid

Actually, it does appear to be feasible to construct such a public key, with the caveats that:

the public exponent $e$ will be large.  While this is legal, most public keys have a small $e$
the modulus may be more vulnerable than usual to a specific (normally nonoptimal) factorization method.  However, how vulnerable it is can be controlled.

(Note: I'll use $N$ to designate the modulus; I want to use $n$ to mean 'the number of bits within the modulus).

Now, the problem can be summarized as: given values $S$ and $M$ (and $n$, which is the size of the representation of $S$), find a value $N$ and a value $e$ such that $Pad(M) = S^e \bmod N$ and $S < N < 2^n$

The reason for the upper bound on $N$ is how RSA signature verification works; they expect $S$ to be a bytevector the same length as the modulus; if we introduce a modulus which is larger than the signature, the verification process will fail, even if the math would happen to work out.

One obvious way to do this is to find a two primes $p, q$ and odd exponents $e_p, e_q$ such that:

$Pad(M) \equiv S^{e_p} \bmod p$
$Pad(M) \equiv S^{e_q} \bmod q$
$S < pq < 2^n$
There exists a value $e$ such that $e \equiv e_p \mod p - 1$ and $e \equiv e_q \mod q-1$

The last is a nontrivial condition, because $p-1, q-1$ are not relatively prime.  And, this generalizes in an obvious way to more than two primes; it turns out that two primes works for us.

Now, if we pick our primes $p, q$ first, we're stuck with solving discrete log problems to find $e_p, e_q$.  You might assume this is difficult; however, it turns out that discrete logs modulo a large prime can be easy, if the prime is properly chosen; in this case, we get to pick the primes.

If $p-1$ has $k$ prime factors, the largest of which is $r$, then a discrete log problem modulo $p$ can be solved in $O(k \sqrt{r})$ time.

We take advantage of this by doing the following:

Select a set of moderate sized prime values $p_1, p_2, ..., p_i$ and compute $p = 2 \prod p_i + 1$, and make sure that $p$ is prime
Also make sure that $Pad(M)$ and $S$ are either both quadratic residues, or both quadratic nonresidues modulo $p$; if they differ, then either $e_p$ will not exist, or it will be even, neither of which works for us.
Use the $O(k\sqrt{r})$ algorithm to find $e_p$
If $e_p$ happens to be even (which can happen if both $Pad(M)$ and $S$ are quadratic residues), then add $\prod p_i$ to it; this will make it odd, and also preserve the relation $Pad(M) \equiv S^{e_p} \bmod p$

We then do the same procedure to find $q, e_q$, noting that we need to look for values $q$ of the right size (to make $pq$ be within the range $S < pq < 2^N$), and that there are no common primes in the sets $p_i$ and $q_i$; this will likely prevent $e$ from existing.

If we follow these steps, then $e$ will exist, and we've solved the problem.

The only thing left to note is the size of the subprimes $p_i, q_i$.  That turns out to be a bit of a balancing act; if these subprimes are $m$ bits long, then the above procedure takes around $O(2^{m/2})$ time; however, it turns out that the Pollard's p-1 method can factor modulii of this form in $O(2^m)$ time. If we are concerned about someone applying this specific factorization method, then we need to select $m$ carefully.  If we select $m=80$ (that is, our subprimes are 80 bits), then we'll be taking around $2^{40}$ computations, which is probably on the hairy edge of "feasible", while Pollard's method would take around $2^{80}$ time (and it appears unlikely to me that anyone would invest that kind of time).


Verify partial message given hash of full message

You've asked for a way to hash a file into a short string $h$ so that given a partial download $c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1}$ of the file that should start with $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{i-1}$ but may have been modified in transit, you can compute some verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1})$ to tell you whether this partial download is good or not.

You haven't specified what security properties you want, but let's say it's random oracle indifferentiability of the hash function given an underlying short-input hash function $H$ like SHAKE128-256, which serves for preimage resistance, second-preimage resistance, and collision resistance (and therefore forgery detection).  This also works if you randomize $H$ and use $H_r$ instead, like KMAC128, which obviates the need for collision resistance.

Here is a slight variation:

The client will download, alongside each chunk $c_i$, a small set of additional hashes $a_i$ that can be used together with $h$ to verify that $c_i$ is correct.

The adversary may tamper with the chunk $c_i$ and the additional hashes $a_i$, replacing them by $c'_i$ and $a'_i$; we assume only that the client is given a hash of the complete download, $h$, that is known to be good.

We will define a verification function $F(h, c'_i, a'_i)$ which returns 1 if $c'_i = c_i$ and $a'_i = a_i$, that is if the data were unmodified in transit, and 0 with high probability under any forgery attempt.  ($F$ is defined on chunks, not on prefixes of the file, so it doesn't actually matter which order you download them in.)

In this slight variation, the original verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| \cdots \mathbin\| c'_{i-1})$ will be replaced by

\begin{multline}
  f\bigl(h, (c'_0, a'_0) \mathbin\| (c'_1, a'_1) \mathbin\| \cdots \mathbin\| (c'_{i-1}, a'_{i-1})\bigr) \\
= F(h, c'_0, a'_0) \mathbin\& F(h, c'_1, a'_1) \mathbin\& \cdots \mathbin\& F(h, c'_{i-1}, a'_{i-1}).
\end{multline}

Transmitting the additional hashes is not likely to be an onerous burden:  The number of additional hashes for each chunk is logarithmic in the length of the file, the size of the hash can be a tiny fraction of the size of a chunk (say, 32 bytes vs. a megabyte), and most likely, the client will be downloading, e.g., an HTTP header alongside the chunk $c'_i$ anyway, not to mention TCP and IP headers and ethernet frames and any other encapsulation, like tunnels and VPNs, that may happen on the network anyway.

Similarly, storing the additional hashes on the server is not likely to be an onerous burden either:  Your file system almost certainly stores various metadata alongside each file anyway, including its modification times, the locations on disk where its data are stored, directory entries pointing to it, etc.

How does this work?

Hash computation.  Before anyone can download the file:

On the server, split the full file up into chunks $c_0, c_1, c_2, \dots, c_{2^\ell - 1}$.
On the server, compute the hashes
\begin{align}
 h_{0,0} &:= H(0, 0, c_0), \\
 h_{0,1} &:= H(0, 1, c_1), \\
 h_{0,2} &:= H(0, 2, c_2), \\
 \vdots \\
 h_{0,2^\ell - 1} &:= H(0, 2^\ell - 1, c_{2^\ell - 1}).
   \end{align}
These are the leaves of a Merkle tree.
On the server, compute the hashes
\begin{align}
 h_{1,0} &:= H(1, 0, h_{0,0}, h_{0,1}), \\
 h_{1,1} &:= H(1, 1, h_{0,2}, h_{0,3}), \\
 h_{1,2} &:= H(1, 2, h_{0,4}, h_{0,5}), \\
 \vdots \\
 h_{1, 2^{\ell-1} - 1} &:= H(1, 2^{\ell-1} - 1, h_{0, 2^\ell - 2}, h_{0, 2^\ell - 1}).
   \end{align}
These are the first level of the Merkle tree above the leaves.
On the server, compute the hashes
\begin{align}
 h_{2,0} &:= H(2, 0, h_{1,0}, h_{1,1}), \\
 h_{2,1} &:= H(2, 1, h_{1,2}, h_{1,3}), \\
 h_{2,2} &:= H(2, 2, h_{1,4}, h_{1,5}), \\
 \vdots \\
 h_{2,2^{\ell-2} - 1} &:= H(2, 2^{\ell-2} - 1, h_{1,2^{\ell-1} - 2}, h_{2,2^{\ell-1} - 1}).
   \end{align}
Repeat, combining two hashes at a time.
At the end of this process, the server will have a hash $h := h_{\ell,0}$.  This is the root of a Merkle tree, which is also a hash of the original data $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{2^\ell - 1}$.  Share the root hash $h = h_{\ell,0}$ of the Merkle tree first.  For example, you might transmit it on another channel (like how a .torrent file is shared separately from the pieces), or the server might digitally sign it with a long-term key pair whose public key the client knows a priori.

Download process.  When the client wants to download the $i^{\mathit{th}}$ chunk $c_i$, after getting the known-good hash $h$ of the file:

The server sends a set $a_i$ of additional hashes alongside $c_i$, $$a_i := (h_{0,i \oplus 1}, h_{1,\lfloor i/2\rfloor \oplus 1}, h_{2,\lfloor i/2^2\rfloor \oplus 1}, \ldots, h_{\ell - 1, \lfloor i/2^{\ell - 1}\rfloor \oplus 1}).$$  These are the sibling hashes of a path down the Merkle tree—for the subtrees that do not have $c_i$ in them.  Here $\oplus$ means xor; that is, we are toggling between the even- and odd-numbered hash indices.
The client receives a putative chunk $c'_i$ and the putative hashes $a'_i := (h'_{0,i \oplus 1}, \ldots)$, which may be the correct chunk $c_i$ and the correct hashes $a_i = (h_{0,i\oplus 1},\ldots)$ or may have been modified in transit by an adversary.  The client can now compute
\begin{align}
 h'_{0,i} &:= H(0, i, c'_i), \\
 h'_{1,\lfloor i/2\rfloor} &:= H(1, \lfloor i/2\rfloor, h'_{0,2\lfloor i/2\rfloor}, h'_{0,2\lfloor i/2\rfloor + 1}), \\
 h'_{2,\lfloor i/2^2\rfloor} &:= H(2, \lfloor i/2^2\rfloor, h'_{1,2\lfloor i/2^2\rfloor}, h'_{1,2\lfloor i/2^2\rfloor + 1}), \\
 \vdots \\
 h'_{\ell,0} &:= H(\ell, 0, h'_{\ell - 1, 0}, h'_{\ell - 1, 1}).
   \end{align}
To ensure the data were not modified in transit, the client then checks $h'_{\ell,0} \stackrel?= h_{\ell,0}$ and drops the data on the floor if it fails.  In other words, we have the chunk verification function $$F(h, c'_i, a'_i) := \begin{cases} 1, & \text{if $h'_{\ell,0} = h$;} \\ 0, & \text{otherwise,} \end{cases}$$ with $h'_{\ell,0}$ computed from $c'_i$ and $a'_i = (h'_{0,i \oplus 1}, \ldots)$ as above.  Note that the computation of $F$, the verification function, involves only the root hash $h$, the chunk $c'_i$ itself, and the $\ell$ hashes included in $a'_i$; verifying a chunk does not require knowing anything else about any other chunk in the file.

For example, in an eight-chunk file, when you transmit chunk $c_6$, send it alongside $h_{0,7}$, $h_{1,2}$, and $h_{2,0}$; the client, given the possibly modified $(c'_6, h'_{0,7}, h'_{1,2}, h'_{2,0})$, computes $h'_{0,6} = H(0, 6, c'_6)$, $h'_{1,3} = H(1, 3, h'_{0,6}, h'_{0,7})$, $h'_{2,1} = H(2, 1, h'_{1,2}, h'_{1,3})$, and $h'_{3,0} = H(3, 0, h'_{2,0}, h'_{2,1})$, and then verifies $h'_{3,0} \stackrel?= h_{3,0}$ before accepting the chunk $c'_6$ as genuine.  The information needed to download and verify $c_6$ is illustrated in the diagram below:

The red solid boxes are data transmitted.  Note that there is no need to download any other chunk to verify $c_6$—only three hashes are needed.
The blue dashed boxes are recomputed by the receiver.
The red solid circle is the root of the Merkle tree, i.e. the hash $h$ of the whole file, which is sent first on some channel assumed not to be corrupted, and which the receiver uses to verify each chunk.

What does this cost?  Let $|c|$ be the maximum chunk size, say 64 KB or 1 MB, $|H|$ be the hash size, typically 256 bits, and $n = 2^\ell$ be the total number of chunks.

The overhead you must store is a total of $2n$ hashes (one for each chunk, and an additional one for each node in the tree) costing $2 |H| n$ bits of storage.
The overhead you must transmit alongside each chunk is $\ell = \log_2 n$ hashes, if the server does nothing to avoid resending hashes the client already has, so the total number of additional bits transmitted for hashes alongside the $n$ chunks is at most $|H| n \log_2 n$.

Thus, the total number of bits stored is $|c| n + 2 |H| n$ and the total number of bits transmitted is $|c| n + |H| n \log_2 n$.

Here are some example data volumes to get some perspective for how much this costs:

\begin{equation}
\begin{array}{rrrrrr}
\text{file size} &
\text{$|c|$} &
\text{$|H|$} &
\text{hash storage} &
\text{hash tx} &
\text{tx overhead} \\
1\,\text{MB} & 1\,\text{KB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 31.25\% \\
1\,\text{MB} & 64\,\text{KB} & 32\,\text{B} & 1\,\text{KB} & 2\,\text{KB} & 0.20\% \\
1\,\text{GB} & 64\,\text{KB} & 32\,\text{B} & 1024\,\text{KB} & 7168\,\text{KB} & 0.68\% \\
1\,\text{GB} & 256\,\text{KB} & 32\,\text{B} & 256\,\text{KB} & 1536\,\text{KB} & 0.15\% \\
1\,\text{GB} & 1\,\text{MB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 0.031\%
\end{array}
\end{equation}

Exercises for the reader.

Handle all the fenceposts in non-power-of-two lengths.
Extend to radix $r > 2$ with total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits.
Generalize to unbalanced Merkle trees, e.g. backwards SHA-256 if you want to download only in start-to-end order.  What costs does this restriction on order save?


What is the need of having a key schedule before executing AES

Not using separate keys for each AES round would make your cipher vulnerable to slide attacks.
Using two plaintexts M and M' with M' being the result of an AES round after calculating M as input, you can differentiate between those plaintexts by calculating the output of an AES round which takes the ciphertext C as input.

Due to the birthday problem, this attack schould reduce the complexity of breaking the AES to $\mathcal{O}(2^{n/2})$.

Source: Silde attack


Needham–Schroeder fix by adding opponent's identity to the first message

It's easy to see that the man-in-the-middle attack you describe still applies to the modified protocol.

$A \rightarrow C(A) :   \{A, C, N_a\}_{pk_C}$
$C(A)\rightarrow B     :   \{A, B, N_a\}_{pk_B}$
$B \rightarrow C(A) :   \{N_a,N_b\}_{pk_A}$
$C(A)\rightarrow  A       :   \{N_a,N_b\}_{pk_A}$
$A   \rightarrow  C(A)    :   \{N_b\}_{pk_C}$
$C(A)\rightarrow  B       :   \{N_b\}_{pk_B}$

The idea why adding $B$'s identity to the second message might be helpful is that $B$ is telling the receiver who they are. So if $A$ sees that message they will realize that something is afoot, since they wanted to talk to $C$ but received a reply from $B$.¹

Whereas in your solution Alice tells the receiver who $A$ thinks they are. But since the man in the middle does not forward this message blindly, but in fact decrypts it and uses it to construct an entirely new message, this doesn't help in any way.

¹This only really helps if the public key encryption scheme used does not have malleable ciphertexts. Using encryption for authentication is just not a good idea and does not lead to robust solutions.


In Paillier homomorphism how do you substract?

Let $c_a$ be the encrypted version of $a$, and $c_b$ be the encrypted version of $b$. What you want to compute is $c_c$ which is the encrypted version of $a-b$, so that when you decrypt $c_c$ you get $c=a-b$.

Paillier supports a homomomorphic addtion of ciphertexts to get an encrypted version of the sum. The actual mathematical operation it takes to get this is modular multiplication. In otherwords, multiplication in the ciphertext domain results in addition in the plaintext domain.

Paillier also supports multiplication of a ciphertext value and a plaintext value. This is achieved by modular exponentiation.

To achieve what you want here, you need to negate $c_b$ by multiplying by $-1$ in the ciphertext domain. To achieve this operation (an encrypted negation of $b$, given only the encryption of $b$, $c_b$), you would do $c_b^{-1}\bmod{n^2}$. That would given you an encryption of $-b$. You homomorphically add that value to $c_a$ (which is achieved via modular multiplication on the ciphertexts) to get $c_c$.

I have an example of subtraction in Paillier in the library I wrote. I also had a writeup about negative numbers in Paillier you may find interesting at the old Google Code host.


Given a hash function how to find all/some inputs that hash to 0?

Select $x=(x_1,...,x_{n-1})$ at random and then compute:

  $$x_n=({a_n}^{-1}\cdot(0-\sum_{i=1}^{n-1}a_i\cdot x_i)) \bmod N$$

Now, select $x'=(x_1',...,x_{n-2}',x_n')$ at random and then compute:

  $$x_{n-1}'=({a_{n-1}}^{-1}\cdot(0-a_n\cdot x_n'-\sum_{i=1}^{n-2}a_i\cdot x_i')) \bmod N$$

Now we have  $h(x)=h(x')=0$.

Note that this question was a special case ($k=0$) of your question at here


Nonce for AES GCM to prevent replay attacks

Any of the ways you listed would work.

If you're collecting alternatives, yet another one (which I have seen in practice) is to include the message counter as the AAD (additional authenticated data), which is another input to GCM.

When we consider which one would be the best, we note that GCM has absolutely no requirement that the nonce be "random", or for that matter, unpredictable.  So, there is no particular reason you couldn't use 4 of the bytes (or, for that matter, all 12 bytes) as a counter; given that all the options on the table are secure, this option (which is the cheapest) would appear to be the best.


Use signed email as method for deriving encryption key

The email signature would not do exactly what you want, but should prevent a man-in-the-middle attack on performing a Diffie Hellman key exchange through email content.

Client requesting decryption:

Generate random private key $CK_a$
Generate public key $CK_b$
Email $CK_b$ to server along with information on file needing decryption

Server:

Generate random private key $SK_a$
Generate private key $SK_b$
Generate session key $X$ from $SK_a$ and $CK_b$
Encrypt information needed to decrypt using $X$
Email $SK_b$ and encrypted payload to client

Client:
Generate session key $X$ from $SK_b$ and $CK_a$
Decrypt payload with session key, decrypt file

In this example the server is the one with the key to the file, swap server and client if you want the client to have the information for decryption, and the server to not. Other variants of this exchange exist, depending on where the file is located, and who should have access to the file, but since the file is at rest, it is already encrypted with a key that is not going to change.


Why does the key for a one-time pad have to be uniformly distributed?

Intuitively, each key decrypts the ciphertext to a different plaintext.  So if some keys are more likely than others, then some plaintexts will also be more likely than others.  Thus, unless all possible keys (and thus all possible plaintexts) are equally likely, observing the ciphertext will reveal information about the plaintext.

(Note that I'm implicitly assuming above that the attacker has no prior knowledge of what the plaintext might be before observing the ciphertext.  That's fine for a counterexample, since a cipher that provides perfect secrecy must by definition reveal no new information about the plaintext to any attacker.  So if we want to show that a cipher does not provide perfect secrecy, it's enough to show that it can reveal some information about the plaintext to some attacker.)


PRF and pairwise independent hash function

You are right; these are the properties of a PRF. In fact, a $k$-wise independent hash function has exactly the same distribution as a truly random function, as long as you only see up to $k$ points. This is the difference: a pseudorandom function has to be indistinguishable from random for any polynomial number of samples viewed. This is both weaker and stronger than $k$-wise independence: a PRF is only computationally indistinguishable from random (weaker), but maintains this property for any polynomial number of samples.

Note also that $k$-wise independent hash functions become very inefficient when you look at large $k$. So typically they are very useful when you only need pairwise independence or a small $k$.


How to implement a Cryptographic Pseudo Random Function

$f_s: d \rightarrow d$ bits is a Pseudorandom Permutation  (see Luby-Rackoff Constructions)
$f_s: d \rightarrow 1$ bit is a Hardcore bit (see Goldreich Levin Theorem)
$f_s: d \rightarrow t$ bits is a Pseudorandom Generator. (assuming $t$ is a function of $d$)  (see Goldreich Goldwasser Micali)

(All these topics are coved in the Katz-Lindell book.)

With these constructions known, you'll be writing provably secure constructions for the crypto primitives.

Also, please forgive my abuse of notation here, when i write $f_s: x \rightarrow y$, what I really mean is $f: x \times s \rightarrow y$


How Will Quantum Computing Change Cryptography's Future?

It depends on the kind of quantum computer and how many logical qubits it has. Not all quantum computer designs are capable of breaking cryptographic systems. The popular adiabatic quantum computers, while very useful for certain tasks, have no cryptanalytic utility. Designs that are capable of running, say, Shor's algorithm are currently in their infancy. It isn't known how well they'll scale.
Realistically, when/if such quantum computers become mainstay, we will need to have moved from algorithms based on factorization or the discrete log problem (or any other hardness problem in the BQP complexity class) to a post-quantum variant. Key exchange algorithms must be upgraded sooner. If you need 25 years of protection, you have to discontinue vulnerable algorithms 25 years before quantum computers can attack it, because they are vulnerable to retroactive cryptanalysis.
It's not as important to upgrade to post-quantum signature schemes. You can delay upgrading a digital signature algorithm until the very day a cryptanalytic quantum computer becomes available. This is because breaking a signature must be done at the time of the attack, not after. This isn't unique to quantum computers. Someone who used PGP in the 90s with a 512-bit key doesn't need to worry about someone forging their signatures because that key has long-since expired or been revoked, so obtaining such an old private signing key is useless.
NIST is currently working on standardizing post-quantum key exchange and signature algorithms for this very reason. They have set a tentative completion date for 2024.


Increasing rounds in DES, increases or decreases the security?

Short answer, it increases the security.

The fundamental problem with regular DES is the number of bytes used for the key. It is too low to be considered secure* (with the level of computational power it currently exist, it is feasible to brute force through DES encryption).

Try checking out 3DES article on wikipedia for more info on a better implementation of DES:

https://en.wikipedia.org/wiki/Triple_DES


Key generation in Digital Signature Algorithm

As the comments are quite spot-on, I shall just reproduce them and say that you should just follow the relevant standard which is FIPS 186-4 appendix A.1, which expands upon your intuition.

  The exact algorithm for generating the primes is specified in the DSS
  NIST FIPS 186-4 [(PDF)]  –
  Henrick Hellström

and

  One issue with the proposed algorithm is that the p generated will
  often be 3071- bit rather than 3072-bit, a stated requirement. Also,
  as pointed by Henrick Hellström, if you want DSA per the U.S.
  Department of Commerce's book, then appendix A.1 [(PDF)] is a
  must; also, following that procedure ensures the parameters are not
  cooked in some way; p and q essentially become
  nothing-up-my-sleeve. – fgrieu


Salsa20 Implementation: Sum of 2 Words with Carries Suppressed

The sum of two words with carries suppressed is just a convoluted way of saying XOR. You don't need to implement any kind of complicated summation operation. Just perform a bitwise-exclusive OR. I have no idea why Bernstein is being so abstruse. No cryptographer who would possibly be reading his paper would need a refresher on something as ubiquitous in that field as a disjunction.

If you're performing modular addition, just like with paper-and-pen arithmetic, you need to use carries. When adding binary you're doing the same but each digit is taken modulo 2 instead of modulo 10.
  1 1   ⟵ carries
0 0 0 1
0 0 1 1 +
⸻⸻
0 1 0 0

We see that  decimal 1 (binary 0001) added to decimal 3 (binary 0011) equals decimal 4 (binary 0100). That is, 1 + 3 = 4. So, what happens if we drop the carries, i.e. perform carryless addition in binary?
0 0 0 1
0 0 1 1 ⊕
⸻⸻
0 0 1 0

This is the same as decimal 1 XORed with decimal 3, and the result is decimal 2 (0010)! So 1 ⊕ 3 = 2. Salsa20 does the same thing, but with 32-bit words instead of 4-bit words. Because the addition is modulo 232, the leftmost carry, if there is one, is always suppressed (there isn't space for a 33rd bit).


There's simply no way to know. I find it very unlikely that AES will be vulnerable to a ciphertext-only attack in the next 20 years (remember, it has been around for over 20 years already and attacks haven't gotten very far). There's no reason to believe the same won't be true for ChaCha20. If you use a good cipher with 256-bit keys (to avoid potential speedups from quantum computers running Grover's algorithm which halves the effective key size of a symmetric cipher), you should be fine.
If you really, really want, you could use something like VeraCrypt which provides you with the option to use three ciphers in a row: AES, Serpent, and Twofish, all of which are extremely secure.
We can say with some level of confidence that it will remain secure for your purposes.


What is the best encryption protocol to encrypt streaming video?

I am building a SoC to capture and encrypt video at once. I would like to understand what encryption protocols are available to encrypt the video stream.

Building tiny SoC? Are you sure you're not using a SoC on a larger board like a pi? Do you have video compression acceleration?

  The video stream will be coming from a camera sensor, like a CCD. If necessary it can be pre-processed on the SoC into a particular format (for example to compress it) before being encrypted. It can also be encrypted from its RAW format if possible. The encryption protocol should have an efficient hardware implementation that can be implemented on SoC.

For performance, you'll want hardware AES. Although you could use AES-GCM, this will require GHASH in hardware for performance; instead you can ignore GHASH and use a parallel block cipher based MAC instead, such as PMAC.

  The goal of this embedded system is to achieve the highest possible security by reducing potential hardware or software attacks on the Soc that might expose the clear video stream to the attacker.

So far we have AES-PMAC; which makes a fine AEAD, although you ask for higher security so lets add nonce-misuse resistance. Accidental nonce-misuse may occur in many ways, including but not limited to: power faults, wrapping the counter, or incorrectly handling backup and recovery. I recommend you use AES-PMAC-SIV.

Encrypting raw uncompressed video does not leak anything assuming the raw size is constant. Encrypting compressed data can leak for instance the presence of motion in the video stream.

In either case, you should chop the video stream on segment borders such that no segment crosses multiple ciphertext messages. We now have an unbounded stream of variable-length messages to encrypt. You may use the OAE2 construction family to maximize nonce-misuse resistance. Use CHAIN to force sequential decryption, or STREAM to enable out-of-order decryption. The latter is ideal for video, as it enables seeking and does not rely on previous blocks (critical if you want to use the disk as a ring-buffer).

  Note that this is a self contained chip, and the video data will not be sent over WiFi or network. It stays inside the chip.

If the data never leaves the disk, why are you encrypting the video stream instead of using full disk encryption (LUKS, LUKS2)?

If you'd like to restrict the lifetime of the video stream you can rotate the keys and treat your storage device as a large ring-buffer. This way you never need to waste time zeroing out the disk, which doesn't work well because the HDD or SSD is making sectors inaccessible while managing hardware errors and wear leveling.

Keys should only exist in memory and/or on a HSM.

Miscreant is the only library I've seen to offer AES-PMAC-SIV and OAE2 so far.

Pseudocode in Rust:

let mut file = File::open("video-dump", append);
let mut segments = record_camera();

let key = random();
let mut stream = Stream::new(key, nonce);

for seg in segments {
    file.write_all(stream.encrypt(seg, authenticated associated data))?
}

Notice the safe and simple interface. You do not need to mess with any raw ciphers. However, you'll want a header per message with the length of the segment and a flag for the start of a new stream and a flag for the end of a stream (if it ends peacefully).


Is McEliece secure with non-binary Goppa codes?

The problem is that you're only referring to plain information set decoding.  Indeed, for plain ISD, the complexity of attacking a Goppa code over $\mathbb F_q$ would scale as one would expect with $q$.

However, Stern's algorithm for ISD does not scale purely with the code size.

Following a geometric distribution, we can express the expected cost of an ISD algorithm as

$$
\mathbb E [\text{cost}] = \frac{\text{cost of one iteration}}{\mathbb P [\text{successful iteration}]}\text.
$$

For Stern's algorithm, given parameters $p$ with $0 \le p \le w$ (where $w$ is the weight of the error vector) and $l$ with $0 \le l \le n - k$,

The probability of a successful iteration does not depend directly on $q$ and can be expressed as a function of $n$, $k$, $w$, $l$ and $p$.
The cost for one iteration is
$$
(n - k)^2 (n + k) + ((\kappa - p + 1) + 2 N {(q - 1)}^p)l + \frac{q}{q - 1} (w - 2p + 1) 2p (1 + \frac{q - 2}{q - 1}) \frac{N^2 {(q - 1)}^{2p}}{q^l}\text,
$$
where $\kappa = k / {2}$ and $N = \binom{k / {2}}{p}$.

As you can see, the way the algorithm scales with $q$ depends a lot on the parameters $p$ and $l$.  Therefore, $p$ is usually chosen to be quite small in order to minimize the effect of going through too many subsets (the ${(q - 1)}^p$ and ${(q - 1)}^{2p}$ terms).

Please see Christiane Peters' thesis, which has an entire chapter devoted to this.  It also discusses additional improvements and proposes exact values for $p$ and $l$.

Of course, there are also Goppa codes over $\mathbb F_q$ for which such a cryptosystem would be secure.  You can find some proposals and analyses in the thesis, too.


Decryption formula of Plaintext Block Chaining (PBC) mode of a block cipher

let $$C_n = E_k(M_n) \oplus M_{n-1}$$ be the encrytion of the PBC mode with $M_0 = IV$
Then use the property of $\oplus$ and the correctness requirement of the encryption; for any key $k$ and every message $m$ in the message space it mus hold;
$$m = D_k(E_k(m))$$
\begin{align}
C_n &= E_k(M_n) \oplus M_{n-1}\\
C_n \oplus M_{n-1} &= E_k(M_n) \oplus M_{n-1} \oplus M_{n-1} & &;\text {x-or both sides with } M_{n-1} \\
C_n \oplus M_{n-1} &= E_k(M_n) & &;\text{cancel}\\
D_k(C_n \oplus M_{n-1}) &= D_k(E_k(M_n)) & &;\text{decrypt both sides} \\
D_k(C_n \oplus M_{n-1}) &= M_n\\
\end{align}
Therefor to decrypt you need $M_n = D_k(C_n \oplus M_{n-1})$


A simple attack on DESX in time $2^{120}$

It is vulnerable to a sort of meet-in-the-middle attack since you don't really have to brute force $k_1$.  Given a plaintext-ciphertext pair, $P$ and $C$, you can calculate $C' = E(k_2', P \oplus k_3')$ for candidate values $k_2'$ and $k_3'$.  Then, you can determine $k_1' = C' \oplus C$.  So, you only need to brute force the two keys $k_2$ and $k_3$, making the complexity $2^{|\mathcal{K}\cdot\mathcal{M}|}$.

Equivalently, you could attack it from the other side by trying all possible values for $k_1$ and $k_2$, decrypting $C$, and using XOR with the plaintext to determine $k_3$.


Pure, raw DES has a key length of 56 bits, which makes it trivially vulnerable to a brute-force attack. Just try all $2^{56}$ possible keys to decrypt the message and stop when you find an English message. On average, this will happen after $2^{55}$ trial decryptions. See the Brute Force Attack section on the DES Wikipedia page for more information on how this has been done historically.

Detection of English text can be automated in several different ways, mostly using metrics that have been computed for large English corpora. Examples are the index of coincidence, letter frequency, and (more generally) n-gram frequency. Counting the number of spaces in the putative plaintext also works surprisingly well; textual documents tend to have quite a few of them.

Attacks under this model are called known-plaintext attacks. Secure ciphers are not vulnerable to known-plaintext attacks: if you replace DES with 3DES, AES, Salsa20, ... in your question, then the answer is "there is no known attack." But DES's key length is short enough to enable brute-force attacks. Note that the only attacks on DES faster than brute-force are not practical: they require an obscene amount of known (or even worse, chosen) plaintexts.


Here is the deal. You can do this pretty easily in SQL. Exactly how is off-topic on this site. I'd suggest one of the other SE sites. Maybe StackOverflow or DBA.

That said, I am writing this as an answer for a reason. My reason is to persuade you to not do it. Here is why, it gives your customers a false sense of security. Your approach to doing the join is to use deterministic crypto, AES in ECB mode or a SHA2 hash of the values in the column. The problem is, there is a one-to-one mapping from original plaintext to ciphertext. So, anyone who knows that mapping will be able to reverse the mapping.

So then the question is, who knows the mapping. Well, you do (and by you I mean your company). So it isn't really doing much to anonymize the data from your prospective. Also,
if you are giving your encryption software to your customers so they can run it on their machines, they can easily figure out the one-to-one mapping by reverse engineering your code (this is especially true if you use something like AES with a fixed key).

So, in short, I would suggest you don't do what you are planning on doing. As to what a better solution to the problem is, I'd suggest asking that as a separate question on here. Start by defining the problem with some examples and make sure you specify exactly what you want to protect and from whom you are protecting it.


Camellia cipher - is it a symmetric or asymmetric cipher?

Camellia is a symmetric block cipher; the same key is used for both encryption and decryption.  And, as a block cipher, it can be used in any of the standard modes (CBC, CTR, CFB, GCM, even ECB, although use of ECB for any block cipher is not encouraged).


What if an attacker knows 1 bit of a OTP ciphertext

No, this wouldn't cause problems.
The reason for this is the way how perfect secrecy is defined.
The definition says that a scheme is perfectly secret if an attacker doesn't learn anything new about the message when giving a cipher text, also see my other answer for a more "mathy" formulation.

So an attacker knows a certain bit is fixed, thus he can't ever learn anything new about it from the cipher text. And he also can't learn anything new about the rest of the message because only the corresponding key bit is fixed and the rest of the key stream is still uniformly and independently random and is thus still an OTP.


Why use PBKDF2 over SHA-512 to derive AES encryption key?

The problem with passwords or, more succinctly pass phrases, is that they are often relatively easy to guess. Password strength - or rather the lack of it - is a common problem. The strength of a password is not such a big deal if there is some kind of control over how the password can be used (e.g. a PIN is relatively easy, but you are only allowed 3 tries). However, if they are used to generate the key then the ciphertext is commonly believed to be accessible by an adversary, leaving the password guessing vulnerable to an uncontrolled offline attack.

Cryptographic hashes have been designed to be not just one way, but also to be rather fast. That simply means that for an adversary it is easy to test many inputs to derive the correct key. Generally it only takes very little time to test a key as well, since it is not required to decrypt a large amount of data with it; if the ciphertext is large then the adversary can still just decrypt a small part of it. So an adversary has to do a limited amount of work to find a key.

The iteration count - or more generally - the work factor is there to slow the adversary down. Any work that you do once for each password, the adversary has to do for each guess. That still only provides an additional amount of work compared to the situation with a cryptographic hash, but beggars cannot be choosers. So this is what passwords hashes or Password Based Key Derivation Functions have been designed to do: "strengthen" or "stretch" the password in such a way that they are relatively harder to guess.

As said, PBKDF's only provide limited protection against adversaries. Moreover, since ciphertext can be stored, the protection diminishes when faster computers become available. Attacks can also be very easily parallelized. So I would very much try and avoid password based encryption all together.

There are some ways of mitigating the problem of course. For one, you can use a password manager and a very complex password that has a similar strength of a secret key (say 96 bits or higher). That way you may not need a PBKDF to strengthen the password (although entering the password may become more cumbersome).

An other way of mitigating this is to encrypt a private key instead. Now you access to the private key to decrypt the ciphertext. You don't need access to it during encryption.


Blind signature works as follows:

(1) User blinds a message $M$ with blinding factor $b$ raise to the public key of the signer $e$ as $ b^e \cdot M $

(2) the signer will blindly sign the value by raising it to its private key $d$, as $ \sigma'^d = b \cdot M^d $

(3) the user will compute the signature $\sigma$ by multiplying $\sigma'$ by $b^{-1}$ as $\sigma = M^d$.

To forge a valid signature without needing the signer, you can start by an inverse process i.e. create a garbage message and signature pair $<\sigma=M,message=M^e>$.

This will work because when the verifier wants to check the validity of the message, signature pair it will raise the signature $\sigma$ to the public exponent $e$ and it will match. The down point for this is that the adversary will have rubbish message.


Using a single key pair for man-in-the-middle attack on Diffie-Hellman

For the attack to work the attacker - say Malory - needs to establish a secret with the party that starts the key agreement, say Alice. After that Malory needs to establish a secret with the party providing the intended service, say Bob.

Assuming that we are talking about ephemeral (non-static) keys then there is nothing preventing Malory to use the same Diffie-Hellman key pair for both Alice and Bob. The established secrets will still differ of course, as the secret also depends on the key pairs generated by Alice and Bob.

Alice was already expecting to use the same domain parameters and key size as Bob. Otherwise she would not be able to establish a secret with Bob directly.

So yes, Malory - the man-in-the-middle - can use a single key pair for this. Malory could even use a single static key pair for all the connections to Bob (assuming that Bob accepts the same public value for multiple connections and doesn't keep a log).

Note that we presume here that the key pair of Alice or Bob is not also used for authentication, because that would prevent man-in-the-middle attacks in the first place.


Which tamper-protection algorithm provides the shortest output?

You are writing out data and reading it back on the same server. You want to ensure that the data that you read back is the same as the data that was written out.

For this use case, symmetric cryptography seems appropriate. Have a single symmetric key that doesn't leave the server. You need to rotate the key only if the server is compromised; this will invalidate sessions in progress, which is likely to happen for other reasons in case of a server compromise as well.

You can take add an HMAC checksum of the data; with HMAC-SHA-256 (a strong, recommended choice), this adds 64 bytes if you encode the checksum in hexadecimal or 44 if you encode it in base64 (or 32 if you include it in binary form but that tends to be hard to parse). There'll probably be a few more bytes' overhead to put the string somewhere. Given the context — a web page — I don't see any point in weakening the cryptographic strength to save a few more bytes.

If you want to encrypt the data as well, use AES-128 with an authenticated encryption mode (CCM or GCM are common choices). There will be an overhead of 16 bytes of IV, up to 16 bytes of padding, 16 bytes of MAC, and a multiplication factor due to the encoding requirement since the encrypted data can use all byte values (4/3 factor for base64). You'll need to decrypt the data before doing any processing with it; in particular, if some of that data is used on the client side, you'll either need to duplicate it or to combine authenticated encryption with a MAC of that plus the client-readable data.

Note that protecting the data in this way only authenticates it — it proves that the data was produced by your server. An attacker can still take the data from one page and send it with another page, or a later version of that page. How to avoid this depends on when the data is legitimate. You may want to include the URL or the user ID in the hashed data, for example, to avoid the data being used out of context.


AES CBC mode is good for encrypting 15-20mb files and then sending it in parts?

CBC can be used to make messages confidential even in transport security. After all, TLS often still uses CBC mode to encrypt the data frames. I'd say however that CBC is not the perfect mode for the job:

there are certain issues with using the last ciphertext block as IV for separate messages - so you would normally have to use the random number generator to generate a fresh IV and send it with the encrypted block of data;
you need to figure out if you want to use padding or not, CBC can only handle data that is precisely N times the block size, padding also introduces overhead;
CBC with a padding mode is vulnerable against padding oracle attacks, i.e. you should avoid communicating decryption errors to the sender now and in the future; if you do not do this then an attacker can decrypt your blocks and therefore your files.

For this kind of encryption counter (CTR) mode is much easier to get right. It doesn't require padding and you can simply keep counting for the next blocks. The only thing that is really a negative is that reusing a counter (initiated using the the nonce/IV) may completely destroy confidentiality. You can skip to an offset in the stream as a bonus.

If you also want protection against changes of the files you could use an authenticated mode of encryption such as GCM. In general authenticated modes use CTR mode under the hood. Of course using GCM and skipping together may be harder to get right.

Note that ciphertext size may be used to guess which files have been send. You could easily fingerprint collections of files by just monitoring the file sizes, if those file sizes are known in advance.

CBC makes this slightly more difficult as you don't know what part of the last ciphertext block contains plaintext / padding. Relying on such a small change for security doesn't seem to be a good idea though. But it is an advantage of CBC over CTR, even if it is a small one.


We can attack the MAC defined by: MAC(k,m)=MD5(m||k), in a chosen-messages setup, basically because MD5's collision-resistance is broken.

The adversary chooses m and m' of the same length $b\ge64$ bytes, differing only in their first $\lfloor b/64\rfloor$ 64-byte blocks, such that there is a collision after hashing these blocks of m and m'. If follows that MAC(k,m)=MAC(k,m'), and also MAC(k,m||m")=MAC(k,m'||m") for any m". We know various efficient techniques to create such m and m', with $b$ down to 128 or even 64 bytes, including with a moderate degree of constraints:

Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (rump session of Crypto 2004, and in Cryptology ePrint Archive)
Xiaoyun Wang, Hongbo Yu: How to Break MD5 and Other Hash Functions (in proceedings of Eurocrypt 2005)
Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute (in Cryptology ePrint Archive, 2006)
Marc Stevens: Single-block collision attack on MD5 (in Cryptology ePrint Archive, 2012, and here with code and example)
Tao Xie, Fanbao Liu and Dengguo Feng: Fast Collision Attack on MD5 (in Cryptology ePrint Archive, 2013)

If instead of MD5 we had an unbroken Merkle-Damgård hash like SHA-256, or a hash secure in the random oracle model (which SHA-256 is not quite, for it has the length-extension property), then we'd basically have no known attack, as discussed in this question.


Software implementation of symmetric and asymmetric bilinear pairings

Take a look to MAGMA. To evaluate MAGMA scripts, in their website go to the tab Calculator. Craige Costello has a free tutorial titled Pairings for Beginners with examples of the Weil and Tate pairings in MAGMA.


What is the difference between PKCS#5 padding and PKCS#7 padding

The difference between the PKCS#5 and PKCS#7 padding mechanisms is the block size; PKCS#5 padding is defined for 8-byte block sizes, PKCS#7 padding would work for any block size from 1 to 255 bytes.

This is the definition of PKCS#5 padding (6.2) as defined in the RFC:

  The padding string PS shall consist of 8 - (||M|| mod 8) octets all
  having value 8 - (||M|| mod 8).

The RFC that contains the PKCS#7 standard is the same except that it allows block sizes up to 255 bytes in size (10.3 note 2):

  For such algorithms, the method shall be to pad the input at the
  trailing end with k - (l mod k) octets all having value k -
  (l mod k), where l is the length of the input.

So fundamentally PKCS#5 padding is a subset of PKCS#7 padding for 8 byte block sizes. Hence, PKCS#5 padding can not be used for AES. PKCS#5 padding was only defined with RC2/RC5 and (triple) DES operation in mind.

Many cryptographic libraries use an identifier indicating PKCS#5 or PKCS#7 to define the same padding mechanism. The identifier should indicate PKCS#7 if block sizes other than 8 are used within the calculation. Some cryptographic libraries such as the SUN provider in Java indicate PKCS#5 where PKCS#7 should be used - "PKCS5Padding" should have been "PKCS7Padding". This is - with high probability - a legacy from the time that only 8 byte block ciphers such as (triple) DES symmetric cipher were available.

Note that neither PKCS#5 nor PKCS#7 is a standard created to describe a padding mechanism. The padding part is only a small subset of the defined functionality. PKCS#5 is a standard for Password Based Encryption or PBE, and PKCS#7 defines the Cryptographic Message Syntax or CMS. In that sense you could say that ECB and CBC mode can use PKCS#5 or PKCS#7 compatible padding. Later PKCS#5 standards simply refer to successors of the PKCS#7 CMS standard for 16 byte block ciphers such as AES.


Actually, the strength of the derived key is likely to be limited by the strength of the password; for example, if the user selects the password "password", well, that's likely be to within the first couple that an attacker checks.

However, if we assume that the password is stronger than what most people select, then the next limiting factor is $n$.  The birthday paradox doesn't help the attacker; he's not looking for two different passwords that derive the same key.  Instead, he's trying to find a password that generates the derived key; a guess at the password has a probability $2^{-n}$ of mapping to the right value (remember, we assumed above that the probability of him happening to guess the original password is even smaller), and so that's the probability per guess of him being able to break the system.


After Google's collision attack, is RSA-SHA1 signature still safe?

The answer is "not safe".

But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.

Google found one collision based on some existing, publicly known collision
attacks on SHA-1. Sees the introduction of Google's paper for a complete list of prior work.

First, let me briefly explain how RSA-SHA1 signature works. The explanation below is adapted from a W3C's page introducing RSA-SHA1.

The message $m$ is compressed via SHA-1 into a fixed-length string $h=\mathsf{SHA1}(m)$.
The RSA signature scheme (with padding via PKCS#1) creates a signature on $h$ rather than $m$. $\sigma=\mathsf{RSASignPKCS\#1}_\mathsf{sk}(h)$.

If SHA-1 is fully broken, we expect that we can find $m_1$ and $m_2$ with the same hash value under possible resource constriant: $\mathsf{SHA1}(m_1)=\mathsf{SHA1}(m_2)$.

In this case, they have the same $h$. A RSA-SHA1 signature for $m_1$ is also a RSA-SHA1 signature for $m_2$.

Now I give an example of why it fails. (corrected example, thanks to @peter-green)

I am the website owner of randomwebsite.com.
I want to have VeriSign sign a certificate for cvs.com.

So, I use the collision attack to generate two certificates.

A certificate for randomwebsite.com.
A certificate for cvs.com.

These two certificates have the same hash.

I have a CA to sign the certificate for randomwebsite.com.

Now, if you have randomwebsite.com's certificate signed by CA via RSA-SHA1, which has a signature for that hash. This signature can also be used in the certificate of cvs.com.

You can apply the signature to the fake cvs.com certificate. Different from the real cvs.com certificate, for this one, you have the private key associated with the public key in the certificate.

A more detailed discussion can be found in another post.

A lesson from the SHA-1 story:

Always use the MOST advanced cryptography. We know SHA-1 has some problems and there is SHA-256, SHA-512 and others to replace it. There is no reason to sit in front of a tiger.

Some comments to this post are of great help.
Thanks to Joshua, Squeamish Ossifrage, and Peter Green.


I assume you're talking about SSL/TLS or a similar protocol. In these protocols there are two reasons to use Diffie-Hellman:

Your certificate only supports signing
Either it is an RSA certificate restricted to signing, or it uses an algorithm that doesn't support encryption, such as DSA or ECDSA.
Forward security - What happens if the server's private key gets leaked somehow?
If you simply encrypted the session key to the server's public key, all past communication with that server can be decrypted. Which is very bad.
If an ephemeral Diffie-Hellman key-exchange was used, a private key leak won't compromize past communications, since the keys used for the key exchange are long gone, and the leaked long term key was only used for authentication and not for confidentiality.
You don't know the public key of the other side
There are situations where you don't know the other side's public key, but you have a different way to authenticate them. In that case you can use anonymous Diffie-Hellman together with that other way. For example TLS supports authentication based on a symmetric shared secret in a way that's secure against MitM.

Some other protocols such as CurveCP use EC Diffie-Hellman for both authentication and key-exchange. In this case they profit from the performance advantage elliptic curves have over RSA.


Why is symmetric lightweight crypto only about block ciphers and not about stream ciphers?

Why is symmetric lightweight cryptography only about block ciphers and not
  about stream ciphers?

Why that assumption? There is a lot of work concerning stream ciphers for lightweight cryptography (LWC). You can find a relevant list here.

Plus, last week the ChaCha20-Poly1305 cipher suites (which are considered as lightweight) have been standardized in this RFC.


In case M is small is it possible to recover the message

No its not secure. As this is homework my hint is: Textbook (plain) RSA encryption is deterministic, and so encrypting the same message always gives the same...


How rare are 1024-bit $B$-smooth numbers?