autocorrelation of non-linear shift register with the period of $2^n$ (full period)

You have misunderstood Sol Golomb. A pure cycling register (PCR) of length $n$ generates a sequence of period $n$ and no longer period. It is physically impossible. It just cycles the loaded sequence of length $n$.
The sequence it generates may have shorter minimal period, a divisor of $n.$

Take $n=3$ and keep shifting left as in a PCR.

$000\rightarrow 000 \rightarrow 000$ actually has minimal period 1. The same for the loading $111.$

$001\rightarrow 010\rightarrow 100\rightarrow 001$ has minimal period 3. Same with the loading $011.$

The PCR of length 3 has decomposed the space
 $\{0,1\}^3$ into four cycles. This is because the minimal periods add to the size of the state space: $3+3+1+1=2^3$

Now, he proves this is always the case for a PCR of length $n$ with respect to the state space $\{0,1\}^n,$ and since all this has to do with divisibility relates the number of cycles in the PCR decomposition of length $n,$ which he calls $Z(n)$ to the Euler totient $\phi(n):$
$$
Z(n)=\sum_{d|n} \phi(d)2^{n/d}.
$$

Now if you take a maximal length sequence of minimal period $2^n-1$ in the $\pm 1$ formulation and insert a +1, next to the unique run of +1 of length $n-1$ (remember +1 corresponds to 0 mod 2) this PCR decomposition applies. So your statement about $C(\tau)$ is I believe his Theorem 4, p.124, in the reprinted edition of the Aegean Park original.

The autocorrelations of the augmented sequence of period $2^n$  now have an extra term in the sum, and the peak $C(0)=2^n,$ is clear.

Since the way to augment this period is to add a degree $n$ term into the feedback function, and that term is active only once in the period, the autocorrelations at nonzero shifts where $\tau \neq 0\pmod n$ are now 0 instead of -1 for the $2^n-1$ period sequence due to this extra term.

What about when $\tau=n$? Well this won't be zero and getting a hold on its exact value is difficult for a general sequence of period $2^n$, the sequence of theorems 5 through 10 are used here to obtain it for the case that we have an augmented maximal length sequence.


How close is homomorphic encryption to handling regular expressions?

In general, it seems that right now, searching on encrypted data is still quite limited. Besides CryptDB, SADS is another that I have seen. Without knowing more about your security requirements, however, it will be hard to say exactly (e.g., is the regex kept private or is only the data that it is being matched against kept private? Is there a trusted third party? and so on).

Personally, I have never seen a system which allows full regex searching of a dataset where either query or data is kept private. The best I have seen is keyword matching with AND and OR boolean logic (see SADS). Phase II of the DARPA PROCEED program looks to some sort of regex searching capability. Depending on how successful that phase is, we might have something a year from now.

As a side note, from the little I actually understand about fully homomorphic encryption (FHE), it would seem that a fully homomorphic system could perform this type of search. FHE systems are currently not that mature, however, as researchers are still trying to figure out how to make them practical.


Is SHA256 resistant to second preimage attack?

SHA-256 has no known collision attack and has no known second pre-image attack and has no known pre-image attack.

There was a claim Has SHA256 been broken by Treadwell Stanton DuPont? but is has already debunked.

Currently, we have generic attacks: $2^{256}$ pre-image resistance, $2^{256}$ secondary pre-image resistance and $2^{128}$ collision resistance. Collision resistance is lower due to the birthday attack. The academical attacks are on reduced rounds, therefore not practical, yet.

Note per comment:  It is not SHA-256 or any other Cryptographic hash's weakness. It is a problem with hash trees that enables to find secondary pre-images and it can be mitigated with domain separation as mentioned in rfc6992. You can also see this problem in this post;

What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?


Can we construct a simulation sound NIZK (Non Interactive Zero-Knowledge) proof?

Yes.

If there exists a single-theorem adaptive NIZK proof system for NP, then there exists a multi-theorem adaptive NIZK proof system for NP. This was proven in the seminal paper of Feige, Lapidot, and Shamir.

The idea is the following: if you have a single-theorem NIZK proof system for NP, then you have a single theorem NIWI proof system for NP. NIWI (non-interactive witness indistinguishable proofs) are strictly weaker than NIZKs, so this is immediate: the WI property states that the verifier cannot distinguish which witness is used by the prover, when there is more than one witness, and this is trivially implied by zero-knowledge, which states that a simulator can simulate the proof without knowing any witness. Now, if you have a single-theorem NIWI, you have a multi-theorem NIWI. This is because unlike ZK, WI is an indistinguishability notion, and therefore we can use an hybrid argument: suppose a prover performs $n$ sequential NIWI proofs (with the same CRS), either all with witness $w_0$, or all with witness $w_1$. Suppose also that an adversary can distinguish whether $w_0$ or $w_1$ was used in these $n$ proofs, with non-negligible probability. Then there must be one of the proofs for which the distinguishing advantage of the adversary was non-negligible (otherwise, a sum of $n$ negligible advantages would still be negligible), hence this adversary already breaks single-theorem NIWI. This shows that single-theorem NIWI implies multi-theorem NIWI.

Now, if there exists a multi-theorem NIWI and one-way functions (which are implied by single-theorem NIZKs for NP anyway), then there exists a multi-theorem NIZK. The idea is to artificially add a second witness that can be used to perform the proof honestly; this second witness will only be used by the simulator. Namely, add to the CRS a random bitstring $y$ of length $2k$, for some security parameter $k$, and instead of proving a statement $S$, prove "either $S$ is true, or I know a string $x$ of length $k$ such that $y = \mathsf{PRG}(x)$" (PRG is a pseudorandom generator, whose existence is implied by any one-way function). In any real run of the protocol, no such $x$ exists, so the proof remains the same (it shows that $S$ is true); but to simulate the protocol, the value $y$ added to the CRS is computed as $y = \mathsf{PRG}(x)$ for a short $x$, and $x$ is given to the simulator (by the security of the PRG, this is indistinguishable from the real CRS). The simulator can then use $x$ to simulate the proof, and it cannot be distinguished from the honest prover by the witness-indistinguishable property of the proof system. Hence, the protocol is zero-knowledge.

If there exists a multi-theorem adaptive NIZK proof system for NP, then there exists a simulation-sound NIZK proof system for NP. This was shown in the seminal paper on simulation-sound NIZKs.

This is a bit more complex (and in fact, the above paper directly shows that single-theorem NIZK implies simulation sound NIZK). In the simplified scenario of one-time simulation sound NIZKs, however, there is a very simple construction given in Appendix B of this paper: given a word $x$, to prove that there exists $w$ such that $R(x,w) = 1$, prove instead the following: either $\exists w, R(x,w) = 1$, or $\exists r, c = \mathsf{Com}(x;r)$. Here, $c$ is a commitment to $0$ added to the CRS; in honest runs of the protocol, therefore, this proof is equivalent to just showing $\exists w, R(x,w) = 1$. In a simulated proof, however, the simulator will instead generate $c$ as a commitment to $x$. This way, $c$ allows to cheat in the proof for the word $x$, but cannot help with cheating in the proof for any other word, hence it is easy to see that the proof system remains sound even if the adversary can see a simulated proof for the word $x$. From there, techniques exist to boost one-time simulation soundness to unbounded simulation soundness, but that would bring us a bit too far.


In practice, CRC operations are often started with a nonzero state.  Because of this, the actual equation is usually of the form:

$$crc(a) \oplus crc(b) = crc( a \oplus b ) \oplus c$$

for some constant $c$ (which depends on the length of $a$, $b$).

An alternative way of expressing this is, for three any equal-length bitstrings $a, b, c$, we have:

$$crc(a) \oplus crc(b) \oplus crc(c) = crc( a \oplus b \oplus c ) $$

The technical term for this relationship is affine; in cryptography, we treat it as linear because, for attacks that assume linearity, affine works just as well.


DES uses a 56-bit key (formally, a 64-bit key, out of which 8 bits are simply ignored), so it represents a family of exactly $2^{56}$ permutations(*).

If you were to select a permutation at random among all the permutations of a space of 64-bit blocks, then there are $2^{64}!$ such permutations, a truly huge number, and you would need, on average, $\log 2^{64}!$ bits to simply represent such a permutation, i.e. about 144 billions of gigabytes. Now, DES for a given key can be represented in a much more compact way (the code that executes DES fits in a couple of kilobytes, and an extra 56 bits for the key). In that sense, DES selects permutations out of the very very few (relatively speaking) that can be represented in a few kilobytes of code.

If you prefer, if you have a computer with a budget of 2048 bytes for code and data, then there are at most $2^{16384}$ possible programs for that computer, that can thus represent only $2^{16384}$ different functions (most of them won't actually run or do anything useful, and even for those whose execution terminates, most won't be permutations of a given space of 64-bit blocks). $2^{16384}$ is already a mind-bogglingly large number, but it is insignificantly small compared to the number of permutations over 64-bit blocks, which is about $2^{1153978594521722658473.7}$ (I computed that with Stirling's formula).

An "ideal cipher" is supposed to be a family of permutations, such as each key represents a random choice among the whole set of possible permutations. That set is immense. Concrete block ciphers, in order to be actually implementable, must necessarily be restricted to a very small subset of such permutations, i.e. the one for which there can exist some code that implements them within a given budget. In that sense, no concrete block cipher can be "ideal".

(*) To my knowledge, it is not proven that all of them are distinct; however, it seems improbable that any two match exactly.


Number of possible access structure with $n$ person

An access structure is just a function $f:\{0,1\} ^n\to \{0,1\}$. It takes a subset of $\{1,\ldots,n\}$ as input (represented as it's characteristic vector) and returns 1 if authorized and 0 if unauthorized. Additionally, the function must be monotone, meaning that $A\subseteq B \implies f(A) \le f(B)$.

The number of monotone Boolean functions over $n$ variables is given by the Dedekind numbers (OEIS). It is a nontrivial formula!

Edit: You are interested in $f$ which are sensitive to all $n$ inputs. Let's call $f$ insensitive to input $i$ if there is a function $g$ (defined on subsets of $\{1,\ldots, i-1,i+1,\ldots,n\}$) such that $f(A) = g(A \setminus \{i\})$ for all $A$. If this is not the case then we say that $f$ is sensitive to $i$. Now say that $f$ is $k$-sensitive if it is sensitive to $k$ of its inputs. You can count the number of $n$-sensitive monotone functions using the inclusion-exclusion principle.

The idea is that $M(n)$ ($n$th Dedekind number) includes things you don't care about like $(n-1)$-sensitive functions. There are ${n \choose 1} M(n-1)$ Monotone functions of $n$ variables that are (at most) $(n-1)$-sensitive, so subtract them off. But since $M(n-1)$ also "overcounts" all the $(n-2)$-sensitive functions, you've subtracted them off too much and need to add them back. There are ${n \choose 2} M(n-2)$ of these. Etc etc etc. You finally get the thing you want as $\sum_{i=0}^n (-1)^i {n \choose i}M(n-i)$.


Euler's totient function and Carmichael's totient function in RSA

Am I right in thinking that Euler's and Carmichael's can be used interchangeably to generate the public key in RSA?

Yes.  The requirement is that the public exponent $e$ have an inverse modulo $\phi(n)$ or $\lambda(n)$, whichever you use—and the two numbers share prime factorization, differing only in multiplicity, so $e$ is coprime with $\phi(n)$ iff $e$ is coprime with $\lambda(n)$.

  To compare their 'effectiveness' I will first compare the amount of time it takes to generate a public key using each function based on time complexity. Secondly, I want to compare the security of the public key (meaning 'how difficult it is to guess the private key given the public key'). But how? Is there an algorithm to use to test the security of an encryption key?

There is no algorithm to test the security of a particular key.  There is literature on the security of systems for generating keys, though—and for RSA keys there are many such systems[1], with some pitfalls if you're not careful about using the fancy ones[2].

However, this is all about generation of the prime factors.  The public exponent $e$ should be a fixed constant like 3 or 65537; then the private exponent $d$ solves either $e\cdot d \equiv 1 \pmod{\phi(n)}$ or $e\cdot d \equiv 1 \pmod{\lambda(n)}$.  If you use $\phi(n)$, $d$ might be larger, so the private key operation costs more to do the same thing.  That is, the only difference the choice of $\phi(n)$ vs. $\lambda(n)$ makes is efficiency of the private key operation.


How can I attack a Triple-Block cipher with 2 keys (like 3DES) with a cost of ≤ 2⁵⁶

As far as I know your attack is the best attack known, unless something better has very recently been published.

Please note that for DES as the basic cipher the chosen $A$ may not work, but you can choose another $A$ and try again

Also, for a generic cipher with $k$ bit key, the complexity is $$2^{k+1}=2\times 2^k=O(2^k),$$
as $k$ increases.


Reverse MD5 of a 76 character string when the first 44 characters are known

You have two problems, the first is the computational complexity of preimage attack on MD5. It is currently around 2^123 Pre-image attack on MD5 hash
This is technically better than brute force but way outside what is feasible in the forseeabile future.
But perhaps worse than that is the information theory limit. A preimage attack will find a pre-image, not the pre-image which was originally used. With 32 chars you get a space of 256 bi,  far more than 128 bits of MD5. This means there are expected to be many preimages of the required form.
This means if you want to find the original as opposed to just any value with the correct form and correct hash it is impossible even with infinite computing power.
The same thing also shows us that requiring a pre image of such a form can't improve the pre image attack complexity as we could have picked any prefix and still expect many solutions.
If you could have limited to a small preimage space you could brute force it. And if the space had some special form  the knowledge that a solution of a special form exist could theoretically make the attack even faster.


Why would it be risky to let Huawei build 5G networks?

There is a political and economic question here:  Who should be granted the power (via economic might or monopoly, via government contracts for building infrastructure, via government endorsement of standards that prefer the technology already in production by one company but not another, etc.) to determine the technology used by the ubiquitous communications infrastructure of telephony?  That question involves issues of consent of the governed, international diplomacy, social rules for power plays, economic theory around monopoly and concentration of power, and so on, and as such is off-topic for crypto.se or security.se, but maybe not for politics.se.

There is a security question here:  What powers does the party in control of the infrastructure has to wreak havoc if their handlers should so request?  If, hypothetically, under pressure by the NSA, Juniper put a remote management back door into all of their firewalls, and if the Chinese power grid's industrial control network or the Chinese agricultural control network were built out of Juniper routers, would that give the United States of Armed Forces a strategic advantage in warfare against China?  That question involves issues of coercion by threat of economic devastation and famine, international diplomacy, and so on, and as such is off-topic for crypto.se, but maybe not for security.se or politics.se.

Finally, there is also a cryptography-related question here: What is the problem with a malicious adversary controlling all the world's networking infrastructure, if all the world's cryptography is designed under the premise of a malicious MITM with the power to intercept, eavesdrop, and forges all the world's traffic?

There are two broad categories of problems that could threaten most applications of crypotgraphy:

A global passive adversary (GPA), who only eavesdrops and never interferes with traffic, enables efficient collection of mass surveillance of metadata in interpersonal communication like Signal.  Most cryptography is designed to conceal the content of conversations, but not the event that conversations happened or when or between whom—as you note, metadata is much harder to conceal.  And metadata collection is invisible to the outside: operationally, the network is still allowing communication to happen.

There are anonymity networks like Tor that aim to conceal metadata with the help of cryptography and a diverse network of operators, but a global passive adversary would also threaten anonymity in low-latency networks like Tor, if the government in control of the GPA is in your threat model.  Of course, we're talking about 5G, not the entire internet, but this is already a problem with the Five Eyes network, which is why you should run Tor nodes in as many different jurisdictions and on as many different networks as you can to diffuse the power to monitor the Tor network.

(Doing this is much easier than persuading everyone to browse the web through high-latency mixnets by email like Richard Stallman does.  And the FVEY or hypothetical Huawei threat doesn't mean Tor is useless: there are many threat models other than the US or Chinese governments against which Tor is useful, like abusive spouses, corporate competitors, puritanical parents, etc.)
A global active adversary like this may have the power to unilaterally deny service to whatever parts of the network they don't like.  See this question for some examples of how availability can be related to cryptography.  Cryptography can detect forgeries or other active attacks, but it can't prevent them.

There are many past examples of internet censorship all over the world.  Most of them are limited in scope essentially to a single geographical region, like the Great Firewall of China, or like when Mubarak cut off the internet in Egypt in a failed attempt to persuade the people how responsibly he wielded power, or like when the United States Senate discusses an internet kill switch for the sake of freedom—except in cases where like when the Pakistani government decided to block YouTube in Pakistan but accidentally the whole world, but a large-scale block that was quickly reversed.

Governments are getting better at making censorship unobtrusive, like asking Baidu to quietly discard politically inconvenient search results for Tianenman Square but otherwise function as desired for the vast majority of queries.  This happens above the level of mere networking gear, but what if you had the power to just make some things unreliable for parts of the world, like making Vkontakte slower than Facebook—or cut off access to a power substation's 5G-connected remote control system at a convenient moment?  Nothing in cryptography can detect these latent powers, nor prevent the consequences of exercising it.
And, of course, cryptography engineering for end-to-end authenticated encryption in applications takes work and a lot of systems just don't have that work put into them because the economic incentives aren't there.  We've made enormous strides in getting billions of people to use more or less end-to-end authenticated encryption for personal messaging in systems like WhatsApp and Signal.  What about other applications, like banking, like document management for corporate secrets, like personnel files?

At resourceful companies where security engineers have clout like Google the premise of a secure network may have been discarded in favor of pervasive end-to-end authenticated encryption, but there is no shortage of corporate environments today that rely on a corporate VPN for access control.  If Cisco, or Huawei, or whoever it is, gets essentially exclusive access to the market for 5G, it would be awfully convenient for these corporate networks to be built out of a nice integrated product with 5G and VPN support—and it would be an awfully convenient vector for nationalist industrial espionage or sabotage.


Importance of salt when deriving an encryption key

There are two ways to attack encryption that uses a derived key:

You can attack the encryption algorithm. In the case of correctly used* 128-bit AES, that essentially amounts to a brute force attack on the 128-bit keyspace.

This would succeed after on average $2^{127}$ tries (if it were practical). If you knew that two files had used the same password salt, you could brute force the key of one, then check if it also decrypts the other, meaning you'd find both with about $2^{127}$ tries when they share a password. If they had a different salt, there would be nothing special about the first key with respect to the other file – you would need a total of $2 \cdot 2^{127}$ tries.

The difference here is fairly meaningless, since both are impossible to break if AES is secure.
You can try to derive the same key. This means guessing the original password, deriving your own key, then trying whether it's the correct key by using it to decrypt.

The time the latter takes depends on the chosen password. Most ways humans generate passwords have much less than 128 bits of entropy, so a dictionary type attack could be faster than breaking the encryption. RFC 2898, i.e. PBKDF2 adds computational complexity to each password guess, by default making you use 1000 HMAC (2000 hash function) iterations in addition to the AES decryption. Call it $2^{b+11}$, where b is the entropy of the password.

Here, if you could find one password, you could try the same password with other files regardless of the salt. So if you knew the the same password was used for all files, salts would add ~no extra protection (just one extra key derivation per file at the end).

The situation where salts do matter is where each key is derived from a separate password. Finding one password (2. above) doesn't give you significantly more information to break others in that case. The best attack is to try the most common password for each, then the next most common password, etc. However, you need to only derive a key-guess once for any number of files that share a salt, meaning the complexity is related to the number of files with unique salts rather than all files.

* Per file AES keys do make correct implementation a bit simpler, since you don't have to worry about IV collisions or e.g. running into a per key data cap, but the fact that you then have to worry about salt collisions may outweigh any benefit.


Well, you can't.

In standard ElGamal the message space is defined as the elements of the group $\mathbb{Z}_q^*=\{1,\ldots,q-1\}$. So $0$ is not in your message space.

You could take exponential ElGamal, i.e., encode messages in the exponent of $g$. So instead of computing $$c_2=mh^r \mod q$$ you compute $$c_2=g^mh^r \mod q.$$ Note however, that firstly your message space must be that small that discrete logs can be efficiently computed (as decrypting requires computing discrete logs). Secondly, this gives you an additively homomorphic scheme and no longer a multiplicatively homomorphic scheme.

Or as @Guut Boy correctly mentions in his comment, you may also use a simpler mapping as the above. For instance you may simply map the message space $\{0,\ldots,q-2\}$ to $\{1,\ldots,q-1\}$, i.e., adding 1 to your message before encryption and subtracting 1 after decryption, such that $0$ maps to $1$ and thus avoids the problem.

Which approach is more suitable for you depends on your application (which, however, is not clear from your question).


How is RSA able to prevent brute forcing using the public key?

If Jeff has the public key and an encrypted message, why can't he guess the message, encrypt it with the public key, and see if he gets the encrypted message.

Well, that particular attack is foiled by the RSA padding method.  All RSA encryption padding methods include randomness in the padding (specifically to foil this attack).  Whenever John encrypts a message, he (actually, his crypto library) selects a number of random bits, and pads the message (that is, prepares the message for the core RSA operation) using those random bits. Hence the encrypted message is a function of both the plaintext message and those random bits.

Jeff can certainly take the public key, and encrypt a guess of the message with it; however unless he happens to pick the same random bits that John used, his encrypted message will look different, and so comparing the actual ciphertext to his test one (with high probability) tells him nothing.  And, we use enough random bits so that Jeff can't brute force those.


A Construction of a Cipher from a Single Pseudorandom Permutation

Even-Mansour is not as severely limited as you make it sound. The success probability for an attacker of Even-Mansour has been shown in various papers to be at best
$$
\text{Adv}^{SPRP}_{EM_{K_1, K_2}}(q, p) \le \frac{2qp}{2^n}\,,
$$
where $q$ is the amount of black-box queries you make to the cipher (read: known or chosen plaintexts), $p$ the number of queries you make to the permutation (read: bruteforce), and $n$ the bit width of the permutation. The same security bound applies to the single-key variant
$$
\text{SEK}_K(x) = P(x \oplus K) \oplus K.
$$
Now, this means that, unlike an optimal block cipher, in which no matter how much data you collect you still expect around $2^n$ computational effort to break it, here by collecting $q$ plaintexts the effort goes down to $2^n/q$.

Now, to answer your questions:

Even-Mansour is already secure, as long as you adequately deal with the above caveats. For example, if you choose your permutation to be, say, 512 bits wide, you have nothing to fear from any realistic attacker.
Yes, iterating several permutations does give you better security. For example, the key-alternating cipher (or iterated Even-Mansour)
$$
\text{KAC}_{K_0, K_1, K_2,\dots,K_t}(x) = P_t(P_1(x \oplus K_0) \oplus K_1) \dots) \oplus K_t
$$
achieves better security $$\text{Adv}^{SPRP}_{\text{KAC}_{K_0, K_1, K_2,\dots,K_t}}(q,p_1,p_2,\dots,p_t) \le \frac{4^tqp_1p_2\dots p_t}{2^{nt}}\,,
$$
which quickly converges to optimal as $t$ grows.
As seen above, iterating Even-Mansour is an effective way to strengthen the cipher. In practice, however, having several independent permutations and keys is inconvenient, and so you see designs that use a single permutation along with multiple round keys, each derived from a single master key. The AES is one such design, with the public permutation—the round function—being weaker than a random permutation but efficient to compute. This is a very successful design principle, and you will find many other ciphers following the same strategy.


TLS: Risks of using a NULL cipher with encryption implemented in application?

The problem is that the session keys within TLS are bound to the TLS session. If you just generate your own keys then that particular binding is lost. You might be able to hack or retrieve information from the TLS session to bind it again, but that would be rather like hacking.

Establishing the keys yourself will very likely lead to a significantly worse protocol than using TLS itself; you'll be bound to make all mistakes in SSL 1.0 to TLS 1.2 all over again.

Instead I propose that you keep to the current TLS to the server. However, that TLS session itself can be tunneled though a much more secure TLS session, possibly using an intermediate node on the server side. Some networking tricks may be necessary of course (e.g. to allow for reverse DNS checking by the original server).


How do I encrypt a long message using ElGamal encryption correctly?

As I mentioned in my comment, how you are proposing to use El Gamal has little to do with how we use it (or any public key encryption system) in practice.  However, I can modify the question slightly in a way to make it relevant:

But what if have multiple messages I want to encrypt?

Would it be correct to use the same shared secret for all these messages?
Or I have to generate separate shared secrets for each message?

In your question, you were splitting up one message into several; however, someone could equally well want to encrypt several independent messages to the same public key.
Now, if we were to use the same shared secret, we'd give (for the messages $M_1, M_2, ,,., M_n$), we'd give the adversary the values $S \cdot M_1, S \cdot M_2, …, S \cdot M_n$).
Now, with encryption, we want to limit any information the attacker can obtain from the ciphertexts to what he already knows.  Now, this is an issue with reusing the same shared secret; for example, if the attacker already happens to know (or guess) $M_1$ (or in the split-up message case, he already knows a part of the original message), we'd like him not to be able to leverage that to learn anything else.  However, with knowledge of $M_1$, he could recover $S$; with that, he could recover the plaintexts of all the other messages (or in the split-case, the entire long message), and so he does learn far more than what he started with (which was knowledge of $M_1$).
Because of this (and other attacks that allow the adversary to recover $M_1 \cdot M_2^{-1}$, also more information than we'd like him to have), we really need an independent shared secret for each message.


There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.


How does a certificate authority issue a digital certificate?

Great question. I'll answer it in several parts.
Which Keys does Alice send?
There are two cryptographic operations that Alice may want to do: encryption/decryption, and signing/validation. You can either use the same keypair for both, or have two separate pairs of keys.
1 keypair method:
Here Alice would sign outgoing messages, and decrypt incoming messages with the same private key. Bob would validate the signature on her outgoing messages, and encrypt messages for her using the same public key.
2 keypair method:
Here Alice would have a (signing_private_key, validation_public_key) keypair, and a separate (decryption_private_key, encryption_public_key) keypair.
In both cases she only sends the public keys to the Certificate Authority (CA) to be made into certificates. The private keys are private, she never shares them, they never leave her machine, they never become certificates.
How does the Certificate Authority (CA) trust Alice?
There are several trust models that different organizations use. Many large companies / government departments operate their own CAs for internal email, file storage, etc. In these cases when someone is hired they are issued digital certificates along with their ID badge, parking permit, etc. We trust that Alice is who she claims to be because she's sitting right in front of the Security Officer issuing the ID.
For web certificates like SSL establishing trust is little more complicated. The CA/Browser Forum has guidelines for CAs on how to verify the identity of applicants. Here is a long list of guidelines. The common forms that most CAs offer are Domain Validated (DV) and Extended Validation (EV) SSL certificates.
Domain Validated (DV) certs
This basically asks you for an email address and a person's name along with the web domain that you want a cert for. It does a whois lookup on the domain to make sure that the name and email you provided matched the domain's registration information. Additionally they can send a confirmation to the email address to make sure that you control it. DV certs can be completely automated, and in fact, "On November 18, 2014, a group of companies and nonprofit organizations, including the Electronic Frontier Foundation, Mozilla, Cisco, and Akamai, announced "Let's Encrypt", a new nonprofit certificate authority that plans to provide free TLS certificates" (wikipedia).
Extended Validation (EV)
The CA/Browser Forum specifies criteria for issuing EV certs, these all require a human in the loop, and relate to how stringently the identity of the applicant organization is researched. Having a phone call between the CA and the applicant is a basic requirement. Often documents are signed, and a face-to-face meeting can even be required before the CA will issue an EV cert. The level of validation that was performed will be included in the certificate to increase its public trustworthiness, consequently issuing CAs charge more for higher quality EV certs.
Many issuers also offer variations on the SSL cert wich don't fall into either the DV or EV categories. For example GlobalSign also offers Organization Validation (OV) as an intermediate category. Entrust offers many different types of certs depending on the network structure and software systems being used by the applicant.


Is (1 bit HW signal) XOR (8 bits PRNG output) sufficient for a HWRNG?

No, this is not a good way to whiten an HWRNG, and it definitely won't give you anything like true randomness.

It is true that the XOR of two independent bitstreams will, indeed, be at least as random as either of the original bitstreams.
However by XORing only one bit of hardware randomness into each byte of output, you're effectively padding each bit in the hardware RNG stream with 7 zero bits, making it very non-random even if the original unpadded hardware RNG was perfectly random.  You're also not doing anything to fix any possible biases in the hardware randomness except for XORing it with the pseudorandom bits.

In particular, this means that, if an attacker manages to discover the internal state of your PRNG (e.g. via statistical observation of the output, seven eighths of which is completely unaffected by the XOR), then they can trivially predict all but the lowest bit of each byte in the XORed output — and may even be able to guess the last bit with better-than-even probability, if the HWRNG output has less than 100% entropy.

(That last part would still apply even if you fixed your scheme to XOR each bit of the PRNG output with a separate HWRNG bit.  To actually achieve proper whitening, you really need to mix multiple HWRNG bits into each single output bit (preferably non-linearly), or at least feed them through a properly designed entropy pool.)


Encrypting a short phrase into two keys. both with length of 32letters

As Ricky Demer mentioned, the Shamir Secret Sharing Scheme is information-theoretically secure ("crazy secure") and also, for the "trivial case" of "all shares are necessary to recover the secret", very simple.

We add all the shares together with "non-carrying addition", and the sum is decoded into the decrypted message.
There are a huge variety of ways to "add" the shares, all of which are information-theoretically secure.
The most popular seem to be

non-carrying base 26 sum, aka Vigenère cipher variant Beaufort
non-carrying base ten sum
non-carrying base 2 sum, aka XOR, aka Vernam cipher

One example: Sum three shares using using Vigenere sum, with A:=0, B:=1, C:=2, D:=3, etc.:

ymunl buxee -- share 1 from Alice
htous qrgph -- share 2 from Bob
czdel fdoss -- share 3 from Trent
-----------
HELLO WORLD -- total

(If your phrase was less than 32 letters long, perhaps you could pad it out to 32 characters with Xs or Zs).

Another example: Sum three shares using non-carrying base sixteen, with A:=ten, B:=eleven, etc.:
(using /dev/urandom and some other random number generator)

f 8 1 2  6 4 4 0  0 2 9 7  d 7 1 6  9 a e b  6 5 5 e -- share 1 from Alice
0 1 2 3  4 5 6 7  8 9 9 9  9 9 9 9  9 9 9 9  9 9 9 9 -- share 2 from Bob
5 f 3 0  c 3 c 5  e 4 0 0  f 7 c 0  5 f f 8  7 6 4 a -- share 3 from Trent
----------------------------------------------------
4 8 6 5  6 c 6 c  6 f 2 0  5 7 6 f  7 2 6 c  6 4 2 1 -- total

48  65   6c  6c   6f  20   57  6f   72  6c   64  21 (paired up)
 H   e    l   l    o        W   o    r   l    d   ! (decoded using ASCII)

(If your phrase was less than 16 characters long, perhaps you could pad it out to 16 characters with 0x20 space characters or 0x00 null characters, giving 32 character shares).

EDIT: Oh, you're making physical objects, rather than sending text messages?

When making physical objects to encrypt some short phrase,
I think that visual cryptography is a lot more fun.

The visual cryptography system described by Dirk Rijmenants
can be done with ink on normal transparency paper, or holes drilled through metal,
to do the XOR operation.
(Is there a way to make the leftover "random background" less distracting ?).

The visual cryptography system used in the "amulets" of Henry Segerman
uses linearly polarizing filters to to do the XOR operation.

Perhaps a tiny bitmap font would be useful.
a b c d e f g h i k


In end-to-end encryption, doesn't the server need to be trusted?

End-to-end encryption over a channel with an eavesdropper, like the WhatsApp server, works by using a mathemagical spell called Diffie–Hellman key agreement.  What follows is not actually how WhatsApp works,* but explores some of the high-level ideas to concretely answer the question without getting lost in the full gory details of everything about the protocol, which defends against many more threats than what you asked about.

Alice and Bob agree on public parameters $p$ and $g$,† say $$p = 2^{2048} - 2^{1984} - 1 + 2^{64} (\lfloor2^{1918}\pi\rfloor + 124476)$$ and $g = 2$.  When Alice wants to have a conversation with Bob, she picks an integer $a$ with $0 \leq a < (p - 1)/2$ uniformly at random, computes the remainder after dividing $g^a$ by $p$,‡ written $g^a \bmod p$, and transmits $g^a \bmod p$ over the channel.  Bob does similarly: picks $b$ uniformly at random in the same range, computes $g^b \bmod p$, and transmits $g^b \bmod p$ over the channel.

By a remarkable feat of mathematics, when Alice receives $g^b \bmod p$, she can compute $(g^b \bmod p)^a \bmod p$, and it turns out to be the same as $g^{ab} \bmod p$.  Bob does the same: given $g^a \bmod p$, computes $(g^a \bmod p)^b \bmod p$, and obtains the same number as $g^{ab} \bmod p$.

Nobody has figured out the remarkable feat of mathematics that would allow someone who knows $g^a \bmod p$ and $g^b \bmod p$ but not $a$ or $b$ themselves to also compute $g^{ab} \bmod p$.

Thus can Alice and Bob share a secret, $g^{ab} \bmod p$, over a channel without revealing to an eavesdropper what the secret is.  They will then hash this into a short secret key, say the 256-bit $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$, perhaps with SHA3-256, and proceed to use it for symmetric-key encryption such as AES-CTR.

But that's not all.  What if it's not just an eavesdropper, but our friend Mallory who, aside from having an annoyingly ungendered name, actively intercepts messages in transit?  Mallory could pretend to be Bob to Alice, and Alice to Bob, and do a pair of Diffie–Hellman key agreements, and establish shared secrets with Alice and Bob, and then eavesdrop on all the messages they exchange.  The WhatsApp server is in a position to do this.

To thwart this subterfuge of per-conversation shared secrets, Alice and Bob use long-term authentication in addition.  Alice generates a number $\alpha$ just like $a$, and puts $g^\alpha \pmod p$ in the telephone book, or shows it to Bob on her phone screen; Bob does likewise with $\beta$.  Thus they have a long-term shared secret $\kappa = \operatorname{SHA3-256}(g^{\alpha \beta} \pmod p)$.  Now when Alice wants to have a conversation with Bob, she does the per-conversation protocol—but instead of transmitting just $g^a \bmod p$, she transmits $(g^a \bmod p, \operatorname{KMAC256}_\kappa(g^a \bmod p))$.

When Bob receives a candidate message $(A, t)$, he first checks whether $t = \operatorname{KMAC256}_\kappa(A)$ before processing it.  If not, he drops the message on the floor and ignores it.  Only Alice and Bob can compute the function $\operatorname{KMAC256}_\kappa$, because only Alice and Bob know the secret $\kappa$.

Next, instead of just encrypting their actual conversation with $k = \operatorname{SHA3-256}(g^{ab} \bmod p)$ using AES-CTR, they encrypt and authenticate their conversation using AES-GCM.  The WhatsApp server can flip bits in messages encrypted using AES-CTR without either Alice or Bob being any the wiser even though only Alice and Bob know the secret key, but without knowing the secret key, the WhatsApp server cannot change anything in messages encrypted and authenticated using AES-GCM without Alice and Bob noticing.

What if Alice and Bob can't exchange $g^\alpha \bmod p$ and $g^\beta \bmod p$ on their phone screens because they've never actually met in person?  They have to consult the telephone book—which WhatsApp publishes.  When Alice consults WhatsApp for Bob's long-term public identity key $g^\beta \bmod p$, WhatsApp could spoof it and lie about it, and if Alice ever later checks Bob's phone screen she will detect the subterfuge because it won't match the key that the WhatsApp server handed out.

On the other hand, if WhatsApp does not spoof Bob's long-term public identity in the telephone book, then Alice will remember it in her personal address book.  If the WhatsApp server ever tries to impersonate Bob when Alice tries to start a conversation, Alice will detect that.  This model of authentication is sometimes called TOFU, or trust on first use.  You will also find it in the ssh protocol.

There's a catch: Sometimes Bob's identity key changes, like when he gets a new phone.  What should Alice do in that case?  In Signal, the app won't send any new messages on behalf of Alice; it will notify her that something is amiss and ask her what to do.  In WhatsApp, by default,§ the app will automatically retry with the Bob's new identity key, in an attempt to reduce usability hurdles for users who don't understand this, which led to an enormous kerfuffle about mainstream media reporting of the choice, which somehow dwarfed a much worse vulnerability in the app leaking the text of what you were typing if it looked like a URL.

In the end, since WhatsApp—part of Facebook—provides the software and doesn't let you scrutinize it, they certainly have the power to read and impersonate your messages, which they probably think very earnestly they won't ever abuse.  That's better than letting everyone on the internet route between Alice and Bob, like the stalker who is sitting a few tables down at the coffee shop on the same wifi network as Alice, which is why it was so harmful for the Guardian to report breathlessly in a back door in WhatsApp the way it did.

Even if your phone spoke TLS to the WhatsApp servers with a pinned certificate, it's still easier to engineer audit trails for malicious changes to the telephone book than it is to engineer audit trails for eavesdropping by the WhatsApp servers—whether by a technical attacker exploiting a software vulnerability, by a LOVEINT disgruntled employee, or by a court-ordered wiretap.

So, can third parties read your WhatsApp messages?  No, not likely, and it would take an active attack by WhatsApp itself—similar to the kind that Apple refused to do for the FBI—for them to read your messages.

* WhatsApp claims to use the Signal protocol (technical documentation).

† Technical details: $p$ is a safe prime, meaning it is a prime of the form $p = 2q + 1$ where $q$ is also prime.  $g$ is a quadratic residue modulo $p$, and thus has order $q$, meaning there are $q$ distinct possible remainders of $g^x$ when divied by $p$ for any integer $x$.  The powers of $g$ modulo $p$ form a subgroup of the multiplicative group of integers $(\mathbb Z/p\mathbb Z)^\times$.  None of this is important for you to understand how to share secrets over a public channel, but I provide the keywords for you to follow if you want to study further.

‡ Alice does not actually compute, e.g., 2^13805771959684693407656077397889219317288456747119690312451189306384849479687628613222950288427889322679415500741971589068616989911210949597114445259398229588157002772876797268276100622563299377498600497546320786879884333079126581727906347769889606788799518360227168951984468071470187490408276074397578464837282521956615118563389889631151319459158126320262667606793413409480951816493115818911703426164912115254095626026747790743791560327229116656590818054138360168383331595495242709153295834514181328053967320381842712608527965926684083141420258332671624779764031721576291538707703835661166957458717002972300906725181, and then divide the result by $p$; instead she uses a modular exponentiation algorithm so that it is possible to get an answer before the universe burns itself out.

§ Some of this is configurable: conscientious users who must use WhatsApp, like a journalist whose only contact with a source is WhatsApp, should study WhatsApp's privacy and security options.


Will I be able to (ab)use a FIDO U2F compliant hardware token to decrypt data?

No, you will not be ble to abuse challenges in that way. You may be thinking about e.g. raw RSA, where signing and decryption are mathematically similar. However, this is not possible in FIDO U2F:

All the defined signature algorithms use SHA256 on the signed data, meaning that you'd have to brute force search for something that produces the correct signature.
Not all the hashed/signed data is controlled or even necessarily known by the server. E.g. the signer has an incrementing counter that's part of the signed data.


Signing the hash of a key with the same key

No, signing the hash of the public key cannot introduce a weakness on a secure signature scheme.

When we have a signature scheme, we assume that it is secure in an chosen text model, where the attacker has access to the public key, and can ask any text of his choosing to be signed.  We can see that any such scheme (such as ECCDSA, or so we believe) cannot be specifically weak this way.

This is easy to see; suppose we had a weakness that was caused by this (whether it revealed the private key, or made it easier the create a forgery).   What the attacker could do is hash the public key, and then ask that hash to be signed.  If the public key system had a weakness, this signature would reveal it, hence showing that the signature scheme didn't meet the requirements of security in the first place.


Yes; as long as the product of the two plaintexts $p_1 \cdot p_2 < N$, you'll get their product; it doesn't matter what the ciphertext values actually are.

The relevant question is: what happens if the plaintexts overflow; that is, what if $p_1 \cdot p_2 \ge N$?  In that case, when you decrypt, you'll get the result $p_1 \cdot p_2 \bmod N$


Is it possible to construct dataset for only another party to consult?

Answering my own question. I believe it is possible. We can use the scheme by Boneh et al. described here.

It uses pairing-based cryptography to be able to create a searchable, asymmetric, tagging scheme. In this scheme, queries are made through a trapdoor of the real key that we want to search, making it impossible for the set holder to retrieve information about the underlying queries.


Compute discrete logarithm mod $n=p \times q$ knowing factorisation

This is not true in general. Bach showed that given the factorization of $n$, computing the discrete log modulo $n$ requires computing it modulo the factors (also cf. this previous question for more details.). So, if both the factors are large then DLP is still hard.


NTRUSign (considered broken) as a one or few time PQ signature scheme

To quote RFC4270

  There is an old saying inside
     the US National Security Agency (NSA): “Attacks always get better;
     they never get worse.”

One of the main reason people avoid cryptographic protocols with known attacks is the above wisdom. Essentially, the attacks show there is an intrinsic weakness in the protocol, and often following works improve the effectiveness of the attack. If you really want to use a protocol with known weaknesses, you need both

to have good reasons to think the possible improvements on known attacks won’t come close to parameters were it would destroy your security. In your case it means being sure that there is no way to improve the number of signatures needed to the attack from a few hundred to a few, or at least that no one will find one in the relevant time frame.
to gain a very strong advantage, like speed.

Since the main practical interest of NTRU signature protocols is their post quantum security, it means that the time scale considered for improvement of attacks the decades needed for your adversaries to have a quantum computer useful for cryptanalysis (otherwise, use RSA !). Given past history of cryptanalysis, I really do not believe one could have any assurance more effective attacks against NTRUsign won’t be found over the next two decades !


Disclaimer: this answer is opinion based.

TL;DR: The question does not really make sense. Because you cannot put things into boxes like that.

The best way to make you understand it is to make an analogy. Cryptosystem is to Chess what Cryptanalysis is to Chess Games Strategy/Reviewing.

As you define a Cryptosystem with the following components:

Plaintext
Encryption Algorithm
Ciphertext
Decryption Algorithm
Encryption Key
Decryption Key

You can define Chess with:

a 8x8 board
16 white pieces (King, Queen, 2 Rooks, 2 Bishops, 2 Knights, 8 pawns)
16 black pieces idem.
a set of rules

And you can see the review and strategy as:

Openings moves and tactics (Alekhine's Defence, Caro-Kann Defence, King's Gambit...),
Midgames moves and tactics,
Endgames  and tactics,
Mat in 3 (and more),
pinning,
forks,
discovered attacks
etc.

Cryptanalysis will be the art to look at a cryptosystem, find it's weaknesses and how to improve it:

differential/linear/integral Cryptanalysis,
boomerang attacks, related key attacks, impossible differentials,
birthday bounds,
Meat-in-the-middle attack,
Game-based proofs,
Shor's/Simon's/Grover's algorithm
etc


I think the comments bring up some good points that make this potentially intractable.  However, I figured I'd give the initial thoughts that come to mind.

This immediately reminded me of Bitcoin BIP-39, which might be a part of your impetus for asking, since it's pretty much identical to what you described, but since you didn't mention it and its reference implementation was in Python, it seems worth calling out.

The obvious downside to this approach is that it would take a considerable number of words to encode an RSA key.  And I know from experience that even the 24 words for a Bitcoin private keys (256 bits) are a pain to communicate verbally.

Something like Base58Check encoding would perhaps be a bit more compact, and still lend itself somewhat to be communicated verbally (in terms of minimizing/auto-correcting mistakes), but would still very long.

You could potentially look into compressing the public key and then using some sort of encoded like the above options, but the answers to that question still don't get you down to 256 bits which, again, is already cumbersome to communicate verbally.

All-in-all I think it depends on the level of effort you're expecting users to put in and the level of technical knowledge they having.  Two technologists communicating a very long Base58Check string would be a huge pain but would likely work.  With any other scenario I expect a mnemonic phrase might be better, but you'd probably have to find something better than the BIP-39 definition.  And even then I'm not sure you'd get to a level that wouldn't cause people to switch to another method (e.g. emailing a PEM file).


How do I generate a number for a lottery and later proves its existence

You could use HMAC for this. HMAC is available in pretty much every crypto library out there.

The process would work like this. Randomly pick A and C. For simplicity, let's assume they are strings (of any length). Compute $B=HMAC(A,C)$. Publish $B$. Once someone guesses $A$, you publish $C$. Anyone can then verify that $B=HMAC(A,C)$.

As long as a good hash function is used, and $C$ is sufficiently long (say 128 bits), knowing $B$ should not help anyone compute $A$.

The benefits of doing this over what you propose in the question is that it is much simpler, faster, and the values generated are much smaller. For factorization to be hard enough, your primes will have to be around 1000 bits each.


Some limitations of the proposed protocol:

It only applies when both parties have a private key, not in the common browser-connects-to-server scenario.
As noted by others, it is not true Forward Secrecy, for it does not protect from leak of both private keys.
Authentication of parties is not provided before knowledge of $K_{ep}$ is demonstrated, in a step not illustrated (easily added).
The scheme is only marginally less costly than authenticated Diffie-Hellman with long-term RSA keys, which solves 1 and 2.
The output of a participant's random generator can be scrutinized by an active adversary with a public key recognized by said participant.
Illustration: Bob or Trudy connects to Alice under his real identity. Alice (accepting Bob, and perhaps Trudy with less privileges) generates a random number using her RNG and sends it encrypted. He deciphers it, gaining insight about what Alice's RNG has output. Poor RNGs and poorly seeded CSPRNGs are legion in the history of security breaches.
And if that participant's random generator becomes predictable, that participant's ability to authenticate (per the method in 3) falls apart, and with that the confidentiality of whatever it's willing to transmit encrypted only to selected authenticated participants.
Illustration: Trudy, having learned a defect in Alice's RNG, can impersonate Bob because he can find $x$ by trial and error, rather than with Bob's private key. He can then receive and decipher whatever confidential information Alice is willing to send to Bob.
Bob has some control on $K_{ep}$.
Illustration: Bob is tricked into using rigged software that chooses $y$ iteratively so that the top 40 bits of $K_{ep} = KDF(x\mathbin\| y)$ are some secret function of the other 88 bits. Even though Bob runs that software in a firewalled VM and has audited that it sends nothing but what it is supposed to send, confidentiality is doomed.


I'm reading the question as asking for a public pseudorandom number generator seeded by a key $K$, which will output integer values $r_j$ in a specified range $[a,b]$ (here, [1 to 75]) pseudo-randomly according to the key, then cycle after having reached each of them all exactly once. Add that the next output is a function $F_K$ of the previous (rather of some internal state).

All we need is a pseudo-random permutation $P_K$ of the set $[0,n-1]$ with $n=b+1-a$, and it's inverse ${P_K}^{-1}$, from which we define
$$r_{j+1}=F_K(r_j)=P_K({P_K}^{-1}(r_j-a)+1\bmod n)+a$$

In other words, to move to the next number, we

subtract $a$
apply the inverse permutation ${P_K}^{-1}$
add one, and if the result is $n$ replace it by zero
apply the permutation $P_K$
add $a$

This essentially is applying $P_K$ to a cyclic counter, and an offset. The first two steps are unnecessary if we can keep memory of the counter's state.

Constructing pseudorandom permutation $P_K$ is a classic problem of Format Preserving Encryption. One option is a table built with a Fisher-Yates shuffle. Another is to use a block cipher and cycling:

compute $w=\lceil\log_2(n)\rceil$, that is the number of bits in $n-1$
build a $w$-bit block cipher $C$ with key $K$ (assimilate up-to $w$-bit integers to $w$-bit bitstrings per e.g big-endian convention).
compute $y=P_K(x)$ as

$y\gets x$
$y\gets C_K(y)$, that is encrypt $y$ with key $K$ per block cipher $C$
if $y\ge n$, go to the previous step

compute $x={P_K}^{-1}(y)$ as

$x\gets y$
$x\gets{C_K}^{-1}(x)$, that is decrypt $x$
if $x\ge n$, go to the previous step

The encryption and decryption loops always terminate, and are executed few times on average.

To construct permutation $C_K$, we can use a symmetric Feistel cipher, except we want to use $\displaystyle w=\min\left(2\left\lceil\frac{\log_2(n+1)}2\right\rceil,4\right)$ which will ensure that $w$ is even, that the Feistel cipher is not so small as to be degenerate, and that in the case where $n$ is a power of four we use a slightly larger block cipher to compensate for it being an even permutation.

Another option is a near-symmetric Feistel cipher when $w$ is odd, and addition instead of XOR for the round loop (fixing the even permutation thing), which let us use $w=\min(\lceil\log_2(n)\rceil,4)$.

If we are not in a hurry, the Feistel round function for round $i$ can be $F_{i,K}(L)=\operatorname{PRF}_K(i\mathbin\|L)$ truncated to $\lceil w/2\rceil$-bit, for some PRF such as HMAC-SHA-256.

In any case (and especially if we use a simpler/weaker round function), we should use a lot of rounds for small $w$, perhaps $\lceil 6+60/w\rceil$.


how to calculate maximum data size of an RSA signature

See step 3, 4 & 5 of 9.2 EMSA-PKCS1-v1_5 that defines the PKCS#1 v1.5 padding mechanism for signature generation:

  If emLen < tLen + 11, output "intended encoded message length too
    short" and stop.
  Generate an octet string PS consisting of emLen - tLen - 3 octets
    with hexadecimal value 0xff.  The length of PS will be at least 8
    octets.
  Concatenate PS, the DER encoding T, and other padding to form the
    encoded message EM as

EM = 0x00 || 0x01 || PS || 0x00 || T

EM will have the same length as the modulus.

This means that T, the data that is padded and then used as input for modular exponentiation is modulus size - 11 bytes (if the modulus size in bits is a multiple of 8). So the data that can be "directly" signed is 11 bytes shorter than the modulus.

This is however half the story. PKCS#1 v1.5 uses signatures in combination with a hash mechanism. This is in step 1..2:

  Apply the hash function to the message M to produce a hash value
    H:

H = Hash(M).

  If the hash function outputs "message too long," output "message
    too long" and stop.
  Encode the algorithm ID for the hash function and the hash value
    into an ASN.1 value of type DigestInfo (see Appendix A.2.4) with
    the Distinguished Encoding Rules (DER), where the type DigestInfo
    has the syntax

  DigestInfo ::= SEQUENCE {
        digestAlgorithm AlgorithmIdentifier,
        digest OCTET STRING
    }

  The first field identifies the hash function and the second
    contains the hash value.  Let T be the DER encoding of the
    DigestInfo value (see the notes below) and let tLen be the length
    in octets of T.

So if you use the PKCS#1 v1.5 standard then T will always fit into the modulus as it just contains an (identified) hash value. The message size is than limited to the input size of the hash function, which is virtually unlimited.


What is the most secure/reliable CSPRNG currently available?

The most secure CSPRNG would be one which produces a stream indistinguishable from random data without knowledge of the key, and which takes a key large enough that an exhaustive search of the key space is impossible. It turns out that there are many such CSPRNGs, so there's more than one answer:

ChaCha and Salsa20 are 256-bit stream ciphers which can output $2^{64} \times 512$ bits of data per key.
AES in CTR mode is secure, but becomes distinguishable after generating about $2^{64} \times 128$ bits.
HMAC_DRBG and Hash_DRBG are NIST standards that use a secure hash function, but are slow.

There are many more which I could list, but not all are popular. ISAAC for example is a secure CSPRNG with no known weaknesses, but it hasn't been the subject of a large amount of research for this reason.

If you are asking which CSPRNG is least likely to be the subject of major cryptanalytic breakthroughs in the future (i.e. which have the highest security margin), then the answer would be complex enough to fill entire cryptography journals, and indeed, they do. In general, ChaCha20 (ChaCha with 20 rounds) is currently thought by many to have one of the highest security margins. But they're all unbreakable.


Operation sequence authentication shared storage

Yes. $\:$ Since "Eva sees everything written on Bob's PC", the process needs to involve something

that's not written on Bob's PC. $\:$ They could use either some sort-of MAC that can be computed

with pencil-and paper, or a signature scheme whose private key is held on a hardware token.

I don't have any particular such MACs in mind, although my immediate idea would

be to lay the message out on a grid, interpret characters as modular integers,

and let the tag consist of sums of characters from certain small subsets of the grid.

Also, it is very rare for using "Number encrypted by private key"

and decrypting values with public keys to be secure.

Almost always, one should be using Number signed by private key

and verifying with the public key instead.


How to construct a variable length IND-CPA cipher from a fixed length one?

The typical way to make an encryption scheme work for variable length message is to use a mode of operation.

Since you are starting with an already IND-CPA secure cipher, even the often despised ECB mode will work. That said, you will still need padding to make the plaintext length a multiple of the blocksize. If adding padding is out of the question, a streaming mode such as CTR will work.


Optimising Pollard's Rho algorithm for large semi-primes

Might as well make this an answer, enough comments. This'll answer your latest questions:

I don't think they have to start at 2, however they need to start at the same value (as per the cycle detection algorithm). So 2 is the simplest choice, and since the function is assumed to trace a pseudorandom sequence, it doesn't really matter where you start.
The function can be any pseudorandom function satisfying the Rho property (gcd is conserved by iterating through it, basically it inherently "remembers" whenever you capture a factor of $n$ without having to store all the numbers, this is the core concept). But $x^2 + c$ is the simplest one, so it's often the best choice as it's fast to calculate and produces a relatively chaotic sequence mod $p$.
$c$ can be negative, because the function is taken modulo $n$, so a negative value is still positive, however it cannot be $0$ or $−2$ (to prevent trivial cycles in $x = 0$ and $x = \pm 1$).
Yes, I said "on the order", this is a probabilistic algorithm so it's usually either a bit less, either a bit more.. it depends on $c$ and on the factor found.  The idea being that it's very fast on small factors (~20 digit prime factor maximum, so I would say a 40-50 digit semiprime is the best you're going to get with Pollard's Rho in reasonable time, which is still pretty good considering its simplicity)


AES-CMAC is defined for messages of any length.

The algorithm can be reduced to the following, if you have non-empty messages smaller than the block size:

(K1,K2) := Generate_Subkey(K);
n := ceil(len/const_Bsize);
M_last := padding(M_n) XOR K2;
X := const_Zero;
Y := M_last XOR X;
T := AES-128(K,Y);
return T;

You don't need to derive some non-standard way of padding your messages.

You should note that len/const_Bsize in the RFC is floating point division. The C implementation does this little trick to not use floating point division: n = (length+15) / 16;.

Shameless plug: I have a JavaScript implementation of AES-CMAC that you can play around in: Online AES-CMAC calculator


Has the ECDH protocol been designed just for key exchange or is it widely used for key exchange?

As far as my understanding of the ECDH goes, after systems are encrypted using ECDH protocol

Stop right here, you cannot encrypt data using ECDH. ECDH is an algorithm, not a full fledged transport protocol (or protocol for securing data at rest, for that matter).

Literature says that ECDH is used for the purpose of key exchange(when data is encrypted using symmetric encryption methods like AES) but can I not communicate application data via ECDH

That's correct. The only thing that is required for ECDH is the public key, and - in specific situations - a nonce. The public key of the sender / receiver is send to the other party for key agreement. Anything else is outside of the ECDH algorithm, and you cannot use the public key to encrypt data directly.

PS: I'm trying to establish encrypted communication between 2 BLE devices.

Right, so you need to follow the Bluetooth protocols and ask us crypto specific questions about it, or ask StackOverflow when it comes to implementation specific questions. The IT security site can be asked about things like key management and practical security of the protocol.
If you want to encrypt just a specific message you may need to look at (EC)IES which uses ECDH for message based encryption. Beware that the scheme requires a trusted, static public key though (otherwise you obviously don't know who can decrypt, and you're therefore susceptible to MitM attacks).


ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to elliptic-curve variants.

If you look at ElGamal closely, you will see that it is, in fact, a Diffie-Hellman key exchange, where the resulting key is used to encrypt a message in a kind of one-time-pad system (the $y^r$ value is the DH output, and is combined, using the group operation, with the message to encrypt). Using the group operation allows for homomorphism, but when that property is not needed, it is a useless complication and overhead.


Length of a Challenge in Challenge and Response Protocol

If your challenge is random bits, the security level is about $2^{bitlen}$, but since you are using it in challenge response you might want to avoid collisions as you said, especially if $O(2^{bitlen/2})$ storage is feasible, so you should set the length about twice required security level. But since you will likely be using pseudo-random numbers, your actual entropy won't be higher than its seed. For example, if the seed is just 64 bits, even if you produce 1K long sequence, we can expect collision in about four billion challenges since PRN generators produce a sequence deterministic to the seed which an attacker who is recording can replay using someone else's signature to complete authentication. But $k$ bit long seed from some source of entropy does not necessarily mean $k$ bits of entropy if the source of entropy used for seeding is not very good. And the PRNG must be cryptographically strong as well. In a nutshell, assuming cryptographically secure PRNG, you can expect repetition as you said in about half the actual bit entropy of the seed.


Exactly how slow is asymmetric encryption?

Yes, asymmetric encryption is slow compared to symmetric encryption.

With symmetric ciphers, encryption and decryption speed can be several gigabytes per seconds on a common PC core; see these benchmarks.

With RSA encryption, on comparable hardware, we are talking tens of thousands encryptions per second, and only few hundreds of decryption per seconds, for common key sizes, and small messages (like 1 bit to 250 bytes, way enough for a session keys and authenticators); see these benchmarks.

Pure asymmetric encryption would often be like 3 to 5 decimal orders of magnitude slower than symmetric encryption is. That's the main reason why in practice, when enciphering messages that could be over what fits the capacity of a single asymmetric encryption, we use hybrid encryption.


What values constitute failing for ENT tests?

Failing ENT output is a little like the length of string; elusive.  So I offer an anti-answer.  The following is the output from running the code below and shows a random sequence passing ENT.  You'll have to use some judement to weigh output diverging from this reference test.

The code executed for 1 MB, 10MB, 100MB, 1GB and 2GB random files using a decent cryptographic PRNG:-

public class SHA1 {

public static void main(String[] args) throws Exception {
    try (DataOutputStream dos = new DataOutputStream(
            new BufferedOutputStream(
                    new FileOutputStream(
                            new File("c:\\scratch\\SHA1-1GB.bin"))))) {
        SecureRandom sr = new SecureRandom(new byte[]{42});
        byte[] data = new byte[1_000_000];

        for (long i = 0; i < 1000; i++) {
            System.out.println(i);
            sr.nextBytes(data);
            dos.write(data);
        }
    }
}
}

C:\scratch>ent sha1-1mb.bin
Entropy = 7.999807 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 268.02, and randomly
would exceed this value 27.54 percent of the times.

Arithmetic mean value of data bytes is 127.6351 (127.5 = random).
Monte Carlo value for Pi is 3.135252541 (error 0.20 percent).
Serial correlation coefficient is -0.001522 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-10mb.bin
Entropy = 7.999982 bits per byte.

Optimum compression would reduce the size
of this 10000000 byte file by 0 percent.

Chi square distribution for 10000000 samples is 251.25, and randomly
would exceed this value 55.46 percent of the times.

Arithmetic mean value of data bytes is 127.5007 (127.5 = random).
Monte Carlo value for Pi is 3.140763656 (error 0.03 percent).
Serial correlation coefficient is 0.000043 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-100mb.bin
Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 100000000 byte file by 0 percent.

Chi square distribution for 100000000 samples is 241.51, and randomly
would exceed this value 71.86 percent of the times.

Arithmetic mean value of data bytes is 127.4998 (127.5 = random).
Monte Carlo value for Pi is 3.141108366 (error 0.02 percent).
Serial correlation coefficient is -0.000179 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-1gb.bin
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 1000000000 byte file by 0 percent.

Chi square distribution for 1000000000 samples is 234.14, and randomly
would exceed this value 82.14 percent of the times.

Arithmetic mean value of data bytes is 127.5055 (127.5 = random).
Monte Carlo value for Pi is 3.141422821 (error 0.01 percent).
Serial correlation coefficient is 0.000024 (totally uncorrelated = 0.0).

C:\scratch>ent sha1-2gb.bin
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 2000000000 byte file by 0 percent.

Chi square distribution for 2000000000 samples is 231.40, and randomly
would exceed this value 85.30 percent of the times.

Arithmetic mean value of data bytes is 127.5032 (127.5 = random).
Monte Carlo value for Pi is 3.141451323 (error 0.00 percent).
Serial correlation coefficient is 0.000034 (totally uncorrelated = 0.0).

You will see both the pi approximation and chi squared values converging.  For another truly random sample (pi out to 2.5 trillion places), chi is 12 as all digits become fairly equally distributed.

(Apologies for the formatting spaghetti)


Yes, as @DrLecter said in the comments, that equation holds from the bilinear property. Here is a step-by-step proof.

Let $e : \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T$ be a bilinear pairing.
The bilinear property states that:

\begin{align}e(g_1 ^ a, g_2 ^b) = e(g_1,g_2)^{ab}\end{align}

Since you don't seem to distinguish between $\mathbb G_1$ and $\mathbb G_2$, we will assume that the pairing is symmetric, so $\mathbb G_1$ and $\mathbb G_2$ are the same group and will be denoted as $\mathbb G$, with generator $g$.

Now, you said that $H  \in \mathbb G$. Since $\mathbb G = <g>$ (i.e., $g$ generates the cyclic group $\mathbb G$), then we can assume that $H = g^h$, for some unknown $h$ (we don't need to know $h$, it is just needed for proving that the equation holds).

Using elementary algebra, we have that:

\begin{align}e(g^x,g^yH^z) = e(g^x,g^y\cdot (g^h)^z) = e(g^x,g^{y + hz})\end{align}

Next, we apply the bilinear property:

\begin{align}e(g^x,g^{y + hz}) = e(g,g)^{x(y + hz)}\end{align}

Again, applying basic properties of the exponentation:

\begin{align}e(g,g)^{x(y + hz)} = e(g,g)^{xy} \cdot e(g,g)^{xhz}\end{align}

Finally, you just "undo" some of the transformations, using the bilinear property:

\begin{align}e(g,g)^{xy} \cdot e(g,g)^{xhz} = e(g^x,g^y) \cdot e(g^x,g^{hz}) = e(g^x,g^y) \cdot e(g^x,H^z)\end{align}

Using this technique, you can prove any of the derived identities of bilinear pairings. The following is a general identity that involves the product of pairings:

\begin{align}e(g^a, g^b) \cdot e(g^c, g^d) = e(g,g)^{ab+cd}\end{align}


Lattice-based cryptography is based on the hardness of certain lattice problems (almost tautologically). The region marked "crypto" denotes the region of approximation factors $\gamma$ such that:

We know how to construct cryptographic primitives assuming the hardness of $\mathsf{SVP}_\gamma$
It is plausible that $\mathsf{SVP}_\gamma$ is hard (as there are not known poly-time algorithms).


Practical BCrypt plus XOR encryption for small messages

No that is not secure.

If someone knows the first part of the message (27 characters I think), they can extract the first part of the LongKey and regenerate the rest of it, WITHOUT THE PASSWORD.

The so called checksum is not cryptographic, not even as robust as CRC32, if you have a 100 character message with the first and 2nd half the same, the checksum is 0. You can also swap message halves without changing the checksum. And worst of all, the checksum is both unencrypted and gives away information about the plaintext, assisting in a plaintext recovery effort.

Trying to use the checksum like a salt as part of the bcrypt input is ineffective, and if the password is long enough, is ignored, making all of LongKey first blocks identical, allowing immediate breakage of all messages that used the same passwords.

The passwords being XOR'd together makes the combined password length only as long as the longest one, and might help prevent a dictionary attack but does not increase entropy like concatenation would.

If you want me to rate from "kids safe" to "unbreakable", you might have gotten it up to "kids safe" if almost every step of the way wasnt done incorrectly.


Why bcrypt is one-way while Blowfish is reversible?

Because bcrypt uses Blowfish as a component inside an irreversible algorithm.  This is very common—many variable-input length cryptographic algorithms are built from smaller, fixed-input-length components that may or may not be reversible.

One example is the SHA-3 hash function, which is designed following an algorithm known as the sponge construction, which builds a hash function out of a reversible function (a permutation).


How to establish if a string contains a message

It will depend entirely on the specific encryption scheme. There is really no theoretical reason why a ciphertext should not be clearly identifiable as being a ciphertext and not a plaintext. In fact, take any encryption scheme and modify it so that the encryption algorithm works as before, only it appends to the ciphertext the string "THIS IS A CIPHERTEXT!", and modify the decryption algorithm to work as before only ignoring this string. For pretty much any reasonable encryption scheme this modified scheme will be (theoretically speaking) as secure as the original scheme.

Why is this? Because, when we evaluate the security of a scheme we assume that the adversary (i.e., the entity trying to break the scheme) knows what scheme he/she is breaking and is explicitly told what pieces of information are ciphertexts.


Does this leak information about the keys?

It leaks information about the plaintext.  For example, given the three ciphertexts, it's possible to compute the XOR of the second and third plaintexts.  This is often enough to deduce the original plaintexts.

  What if some sort of random mapping where each bit of the key does not encrypt consecutive bits of the next key was thrown into the mix?

To start, instead of trying to guess about how to make the process more complex, I would suggest thinking about how to rederive the attack I mentioned above.  Learning about how to do cryptanalysis is the right place to start to learn how to design cryptography.


Yes, you can; you can use Batcher's Merge Exchange algorithm, paired with a constant time/access compare-and-swap routine (which reads two elements from locations A and B, and writes the larger element into location A and the smaller element into location B).
This takes $O(n (\log n)^2)$ time, which makes it not quite as fast as other sort algorithms; however if you want constant time/memory accesses, that's about the best we have.
The code on Wikipedia assumes that $n$ is a power of two; it is not hard to extend it to arbitrary $n$...


Are there any formal tests to estimate encryption strength?

TLDR: There are no tests that prove that some algorithm have particular strength.
Statistical metrics can only prove that an algorithm is weak. If the metrics give "good" results, it does not mean anything.
Example: If your algorithm produces encrypted messages that are indistinguishable from a random stream of bytes, you can get "good" metric values. But if this algorithm uses effectively only the first 40 bits of the 128-bit password, it can be relatively easy brute-forced.
Brute-forcing as iterative trying of all possible values is not used in serious cases, because it may require the computational power of the whole planet and even 1 000 000 000 years may be insufficient to try all possible password candidates.
Instead, first the analysis of the encryption algorithm should be done to reduce the amount of work needed for decrypt. For instance, if some algorithm uses 128-bit passwords, a straight forward brute-forcing may need 2^128 "units of work", which means that it is practically impossible to find a password. But if somebody finds a way (an algorithm, an "attack") to exclude many passwords or in some other way to reduce the number of "units of work" from 2^128 to only 2^40, then this will require little resources and it can be successfully brute-forced.
Finding ways to reduce the amount for work needed for brute-forcing is a very complex activity. It cannot be formalized fully. This is the reason why we need cryptographers.
What can you do? Such question was already answered many times on Crypto SE: Pay a professional cryptographer who will analyze your algorithm. If there are some trivial weaknesses, they will be found. But even if not found, it does not mean there are no any weaknesses.


The use of Elliptic Curves as part of a blockchain transaction

If you're asking why don't we use a simple hash to authenticate, well, that doesn't actually provide any authentication (as anyone can compute that hash).

On the other hand, there are signature algorithms based on hash functions (oddly enough, called hashed-based signatures) which rely on the preimage resistance (or collision resistance) of a hash function.  They would appear to be ideal for block chains, except that they do have these drawbacks:

These signatures are significantly larger than ECDSA signatures; we might be talking on the order of 1kbyte rather than 64 bytes for what bitcoin is currently using.
There are practical drawbacks; in the simplest case ("one time hash based signatures") a public key can safely sign only one message.  On the other hand, this might be an acceptable limitation in the bitcoin case; everytime we sign a transaction, we'd generate a fresh public/private key pair, and include the public key in with the transaction we're signing (and use the new private key the next time).  There are other schemes that lessen this restriction (in case this approach turns out not to be feasible).

I suspect reason #1 is the main reason why bitcoin hasn't transitioned to this approach


PyCrypto and AES: can i use a longer key than the block size (16byte)?

I see that in many scripts are used keys of 16 characters for a block of 16 byte, but can I use key of 40 (for example)?

No, AES uses a key size of 128, 192 or 256 bits. That's 16, 24 or 32 bytes.

  And then why in some scripts with aes module the block size is set to 32 byte if aes can handle a fixed size block of 128 bit? Is it correct?

No, that's not correct. It could however be that the module implements Rijndael instead of AES. AES is a subset of Rijndael, and Rijndael can have the block sizes 128, 160, 192, 224 and indeed 256 bits. So in that case the block size can be 256 bits.

Notes:

not all implementations of Rijndael offer support for 160 and 224 bit block and key sizes (so many posts don't mention these block and key sizes);
bytes are not characters, although the name of a byte in C/C++ is traditionally called a char as for ASCII each character is represented by exactly one byte - no conversion necessary;
sometimes when characters are mentioned they actually contain hexadecimal digits; as you need two hexadecimal digits to represent one byte it may seem that 256 bits are used instead of the actual 128 bits.


Yes, it's okay.

This is actually mentioned in passing in the SRP 6 design paper. Previous versions used a random $u$ where an attacker who saw (or could predict) it before revealing $A$ could compute $A = g^a v^{-u}$ and use this to effectively cancel out the long term secret. With $u$ derived from a hash, even if the attacker saw $B$, the dependence of $u$ on $A$ means that they would need to break the hash function to be able to find a suitable $a$/$A$ for an attack.


A lower bound on the insecurity of CipherCloud?

That paper refers to the numerical ordering, while what would be relevant for searchable encryption without changes to the providers is the substring ordering. $\:$ (Thus, their bound does not apply.)

What do you mean by "existing queries in a database"?

If your assumption holds, then
{
Encryption must be deterministic (given the key), since different encryptions of the

same message (with the same key) must be substrings of each other (and thus equal).

There must be a noticable $\big($though not necessarily $\theta\hspace{.01 in}(1)\big)$ chance of breaking authenticity via a

single ciphertext only (by submitting a random substring of it). $\:$ The scheme must be malleable by

almost the same amount, again with just a single ciphertext only and for basically the same reason.
}

"without changes to the providers" is a rather stiff assumption. $\:$ For example, one could easily shut

down active attacks by splitting the ciphertexts into two columns and having the cloud just search the

left column, while the right column has message authentication codes which are only relevant to the user.


Are PQ/Classical Hybrid Key Exchanges a reflection of how little we trust PQ cryptography primitives?

Actually, we do trust many (but obviously not all) post-quantum cryptosystems more than traditional schemes. We haven't been using them because they fail to meet practical space and time trade-offs.

  When elliptic curve cryptography was first being deployed no one was suggesting using elliptic curve cryptography with classical RSA or Diffie-Hellman in a hybrid scheme.

A hybrid solution would defeat the primary motivation of switching to ECC; faster, smaller and more secure. PQ schemes may be faster xor smaller, but our interest is in their increased security.

  When SHA-3 was standardized no one suggested making a hybrid of SHA-3 and SHA-2. When AES was invented no one suggested using it in a hybrid with Triple DES or some other cipher.

Many applications use multiple hash functions either for cross version compatibility or increased collision resistance. I.e. MD5, SHA1, and SHA256 checksums for source or package distribution.

  Is the desire for PQ hybrids a reflection of the distrust we have in the fundamental primitives that underlay our post quantum schemes?

The primary applications for PQ where hybrids are desired involve forward secrecy in key exchanges. If we must spend the time and bandwidth for a PQ scheme, then using ECC in addition to this is almost negligible.

  If we do trust these primitives why the need for a hybrid?

If I audit a piece of software and I know it uses a hybrid scheme and I understand and trust one of its components, such as ECC, then I may be satisfied without having to learn about the particular PQ scheme in use. If an assumption in the PQ scheme is incorrect, I know the protocol is at least as secure as the traditional scheme.


Is it okay to send an encrypted key using XSalsa20-Poly1305, and send subsequent messages using ChaCha20-Poly1305?

Yes, this is secure.

Even simpler would be to just use XSalsa20-Poly1305 and the long term key directly. You could authenticate any additional data with the Poly1305 just as well as in the case of the ChaCha-based combination. However, if you use e.g. libsodium where the former interface does not support additional data and the latter has a short nonce, then combining them like you suggest is OK as well.

Note, regarding your comment: there is no need to authenticate the message length separately. The whole message is already authenticated by default so you can just calculate its length.

If the only additional data you need to authenticate is a sequence number, you could include it as part of the 192-bit nonce and use XSalsa20-Poly1305 only. 128-bit random part and 64-bit sequence number would be fine, and 160/32 would be even better.


Encryption scheme with high complexity encryption over decryption

You could use a PoW style system combined with authenticated encryption similar to SIV mode as follows:

Determine the hash of the plaintext, $H$ = SHA512$(P)$

Using a 128-bit nonce $N$, an incrementing 64-bit counter $C$, calculate $S$ = SHA512$(E_k(H) | N | C)$  until you have the required amount of sequential high order bits with a value of 0, 32 for example.

Encrypting the plaintext hash makes sure you will not generate the same secret as someone else using the same plaintext and nonce but with a different key.

Truncate $S$ to the 96 lowest bits, and use that as the nonce for CTR mode to encrypt the data

The ciphertext will be supplied with the $N$ and $C$, after decryption you calculate $H$ then $S$ and verify that it matches BOTH the ctr nonce as well as having the correct 0-bit prefix, you should also authenticate $N$ and $C$ some how.

The scheme is configurable for the workload by choosing the amount of sequential 0-bits in the hash. Using a single iteration of SHA512 (or Blake2b) means one cannot use bitcoin ASIC to accelerate encryption, and that encryption requires high cpu but low memory. Hash calculation is generally much less complex than other algorithms such as ECC.

If you want there to be no way to have the same plaintext/key combo generate the same hash, the nonce can be based on prior data like in a blockchain, or based on the current time (if not fakeable), or a sequential counter. (or a combination of several values). You can also eliminate optimization attacks on the hash message schedule by making $S$ = SHA512$(E_k(C | C) | E_k(H) | N)$, but that is probably not a concern.


Why in cryptographic schemes we always assume that the key and plaintext are independent?

What if the plaintext depends on the key? How it can endanger security?

Well, one trivial example where it can is if you are using RSA (without padding), and encrypt one of the prime factors. Someone seeing the ciphertext could immediately factor the modulus (by computing the GCD of the modulus and the ciphertext), thus endangering security.

There is a formal name for systems where this provably can't happen; circular security.  See this paper for a public key cryptosystem that can securely encrypt any polynomial function of the private key (up to a degree bound).

My personal opinion: If you really need to do this sort of thing, I think a hybrid scheme such as the Integrated Encryption System would suit your requirement quite nicely.


Public key crypto instead of hashing passwords in a database

This is a really bad (and somewhat pointless) idea (if you do it on your own), because it provides less security than standard hashing and should only be considered if password escrow is a necessary feature.
If you don't need the password escrow (= recover the password using the heavily secured airgapped private key) you can simply password-hash the password using a modern scheme such as Argon2 which won the Password Hashing Competition.
If you really need the escrow functionality you should use Thomas Pornin's (who's here around sometimes) Makwa password hashing scheme which has been recommended by the Password Hashing Competition (PHC) for special use cases (as yours).

Now for the obvious approach and why it is bad.

I'd assume you would implement this by applying straight, raw RSA to your passwords and compare the results.

Now, if you just do $E_S(PW)$ without any randomness, you're basically creating a one-way hash function (with a backdoor and without compression) which is unsalted and doesn't use stretching (like for example raw MD5 password hashes). As your update reveals you indeed planned on using salting so it's not completely bad, but still far from optimal.
The second issue is that you won't get a compression. Meaning any password will occupy 256 bytes in your database as opposed to the standard 16 or 32 because you need the whole RSA encryption for key escrow.
The next issue is that you could add a salt, but because it's RSA you need to use a big salt, because there is an attack with run-time $O(\sqrt{m})$ meaning you need at least another 32 bytes salt, which further increases storage penalty.
Now you can also quite fastly compute the RSA encryption, meaning brute-force attacks won't be slowed down. This would mean you'd have to apply RSA multiple times are do some intense pre- or postprocessing without loosing information which is quite not easy.

I presume you didn't think of all these issues (yet), so better go with Argon2 or Makwa.


Can we exchange the permutation of a sponge construction?

The security of the sponge construction rely on two parts:

the size of the capacity.
and the strength of the permutation used in the construction.

This permutation is expected to have at least the following requirement:

provide a strong diffusion (in Keccak this is provided by $\rho$ and $\pi$).
provide confusion ($\theta$ and $\chi$).

In the case of Keccak, $\theta$ is an operation mainly columns oriented.

Which is why $\pi$ will ensure that every bits of a column is evenly spread in the slice. This prevent the creation of patterns.

$\chi$ is the main ingredient in Keccak-$f$. It is the only part that is not linear. Without it Keccak would be super weak to cryptanalysis.

propagation of a difference through $\chi$

Lastly, Keccak-$f$ provides a weak alignment (resistance to truncated differential cryptanalysis). The idea is to make sure that the differences are not constrained by a subdivision of the state (byte for AES or a group of 5 bits in the case of Keccak). However, due to the weak alignment of Keccak-f, finding the lower security bounds of the algorithm is harder.

If another permutation provide such characteristics (NORX permutation? I'll let  Richie Frame answer that part. He loves NORX). Then I guess it would be another decent choice.

I haven't studied LFSR.

TL;DR: The candidate permutation must provide strong diffusion, confusion and if possible a weak alignment.


Can Curve25519 be used for pairing-based cryptography?

The embedding degree specifies how many times bigger the finite-field you map to is compared to the field the curve is defined over.

For example for BN(2,254) the degree is 12, mapping to a 3000 bit field, which matches the security level of the curve (~128 bits of security for both) and is reasonably efficient (you can perform a couple of hundred exponentiations per second in this field).

For Curve25519 the degree is 1206167596222043702328864427173832373476186059896651267666991823047575708498 $\approx 10^{75}$, mapping to a $\approx 3 \cdot10^{75}$ bit field. It's rather unlikely that you could afford a computer which can store an element of this field or perform computations on it.

https://safecurves.cr.yp.to/transfer.html


Uncompress password protected WinRar file without password

Why can't you simply ask the person who made that file to tell you the password?

No one knows how to decode an AES-encrypted file, such as password-protected WinRar files, without knowing the password.

As far as we know, the only way to decode AES-encrypted files is to somehow obtain the right password, and then use that password to decrypt the file.

In the movies, sometimes you see people "cracking" a password.
They try all possibilities for the first letter,
and then when they get the first letter right,
they try all the possibilities for the second letter, etc.
Eventually all the letters fill in, and the then the actor has the whole password.

It doesn't work like the movies with AES. AES passwords are all-or-nothing. If you get all-but-one of the letters right when typing in your password, you get exactly the same "failed" message as if you typed in a completely wrong password.
(It's not possible to distinguish the random-looking gibberish from decoding with an almost-correct key from other random-looking gibberish from decoding with a completely wrong key).
It's not possible to tell if one guess is "closer" to the right password than another guess.

(There are various "timing attacks" that, with some systems, can tell a researcher if one guess is "closer" to the right password than another, but they don't work on AES-encrypted files).

There are various "password unlocker" programs that will try one guess at a time until they stumble on the correct WinRar password.
If the person who made the password-protected WinRar file picked a "strong" password -- for example, a passphrase of 8 words randomly chosen using dice from a short dictionary -- we expect that it will take more than a thousand years to stumble across the correct password.
If that person picked a "very weak" password -- such as a single word in the dictionary, or a single dictionary word followed by a single digit, or a single word repeated 8 times, or a sequence of 5 completely random characters -- we expect that it will take less than a day for that program to run through all those very weak passwords and find the correct one.

EDIT:

According to Wikipedia: WinRAR, the "method of encryption" used by WinRAR is the AES (Advanced Encryption Standard) with a 128-bit key.

I agree with Thomas. It's probably hopeless trying to crack it without knowing anything about the password.
If you do find a way to crack AES, Bruce Schnier, the readers of crypto stackexchange, and every other cryptographer on the planet would be fascinated to find out, especially those cryptographers who work at the SVR, the NSA, and other intelligence agencies.


What are the disadvantages of using random s-boxes?

This relates to the "why" behind some of the rules for s-boxes. AES, for example, requires an invertible s-box. A random s-box will not necessarily be invertible. In an s-box we also want non-linearity to thwart linear and differential cryptanalysis. This might not be the case with a random s-box.

  In AES, the s-boxes had to obey certain mathematical rules, which? And why?

According to "The Design of Rijndael" the design criteria was 1) non-linearity, specifically "the maximum input-output correlation amplitude must be as small as possible" and "the maximum difference propagation probability must be as small as possible". This is to prevent linear and differential cryptanalysis. And 2) algebraic complexity. This was to prevent algebraic attacks.

They achieve 1) by choosing an s-box that was studied in Differentially uniform mappings for cryptography. This particular s-box however is algebraically simple. Thus, the AES designers added an affine transformation which would be easy to describe yet algebraically complex.

One additional restriction they placed was that there were no fixed points and no opposite fixed points.

  What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?

Full disclosure, I'm not too familiar with these ciphers. From what I saw on wikipedia, the s-box in GOST can but doesn't have to be kept secret. The effect of this is an increase in the key size. Secret s-boxes would have to have properties similar to those of AES's s-box in order to thwart differential and linear cryptanalysis.

Generated s-boxes, I'm assuming must have some algorithm to setup an s-box using keying material that still meets the necessary properties. I'm guessing this is why Khufu has an expensive setup operation.


That wouldn't appear to work.  In a known plaintext attack, that is, where the attacker knows both $m$ and $c$, he can compute:

$$e = c - m * B$$

recovering the secret key.

Alternatively, in a ciphertext-only scenario, the attacker could take two ciphertexts $c, c'$ and compute

$$(c - c') * B^{-1} = m - m'$$

resulting in the difference between the two plaintexts.