How to calculate the maximum output size for data encrypted with a RSA Private Key?

We do initially did not have the specification of prv_key_enc, thus we can could not answer with some level of certainty anything more than: the maximum size of its output, in bytes, is at least 128. Looks like the answer now is: the output is always exactly 128 bytes before Base64 encoding, making it exactly 172 bytes.

One thing is sure: the term prv_key_enc is grossly non-standard. Problem is not that Googling it is circular. The main issue is that in RSA, encryption is always with the public key, thus at least one of the following does not hold: prv is for private key, enc is for encryption and correctly describes the overall intend.

Confusing public with private is an even worse sin than confusing encryption with signature, so the best guess we can could make is that the question is about a signature, or rather the signature of a hash (which is functionally equivalent) if we trust the notation (the first step of signature in most practical schemes is hashing, but is part of the signature process, including unambiguously in PKCS#1, so the notation suggests the signature of a the result of sha1_hash that will get re-hashed; such double-hashing is sometime used in practice, e.g. in Global Platform).

Update (AGAIN): Even given the Java code, I am uncertain about what is really done. It could be some signature that is NOT one prescribed by PKCS#1: using RSAES-PKCS1-V1_5 encryption overs the hash of the message, except with the private key instead of the public key; this would be a randomized signature scheme; its security uh, would be an other question, depending to some degree on the verifying code, and perhaps the public exponent.

In any case, a PKCS#1 RSA cryptogram (resulting from one encryption or signature) with a key of $n$ bits is defined to be an octet-string of exactly $\lceil n/8\rceil$ octets, which is always enough to code $x^y\bmod N$ when $2^{n-1}<N<2^n$, where $y$ is the public exponent $e$ for encryption, and a private exponent $d$ for signature; and $x$ is a prescribed padding of the message to encipher, or of some hash of the message to sign. Under PKCS#1, encryption of a 20-octet SHA-1 hash with a 1024-bit key, and signature of any data of any size up to at least $2^{61}-1$ octets with any key, both result in a single RSA cryptogram. Thus for $n=1024$ the single cryptogram is exactly 128 octets (or bytes, that's synonymous on modern computers), including when the leading octet(s) are zero, assuming PKCS#1 is followed to the letter.

However the association of ECB (initials of Electronic Code Book) with PKCS1Padding is very uncommon, except as part of some crypto APIs trying to unify things that should not. Update: We are now told this is Java We are left uncertain about what ECB means. Especially if prv_key_enc did encryption as we are told it does, prv could designate some private hybrid encryption mode using ECB at some point, and who knows what the size of the cryptogram would then be, except that if it uses RSA per PKCS#1 it is going to be at least 128 octets, or won't be decipherable.

Also importantly, practice differ widely!! And we do not have any initially had no clue about practice in the mysterious prv_key_enc (we now have); in particular it is not uncommon that a PKCS#1 signature

is ASN.1 encoded, which always increases its maximum size by several bytes, but can make it of variable size (leading  bytes in the encoding of the integer can be suppressed, this is allowed but not required by at least some ASN.1 implementations, there is a complication with sign, leading to several different ASN.1 signatures valid for the same message even for deterministic signature schemes); (update: given the Java source, I would say this is not the case here);
or/and is expressed as a base-64 (or other base) character string of characters, which increases the size in bytes to some degree (update: given the Java source, base-64 is used here).


Calculating the inverse modularity of the determinant for Hill cipher

Maybe the impossibility of solving the equation system uniquely was meant to strengthen the cipher. :D If everything was done correctly, there'll be multiple solutions. When you have some idea of how the plaintext may look like, it should be easy to determine it uniquely.

During the computation you have to divide something by 62 modulo 26, which is (as already stated) impossible. However, the nominator will always be even, and for any $a$, finding a solution to

$$62 * x \equiv 2a \pmod{26}$$

is as easy as finding the unique (mod 13) solution to

$$31 * x \equiv a \pmod{13}$$

Just note that for each $x$ also $x' = x+13$ solves the original equation.


Using PKCS #11 Certificate Objects for Verification

Quoting the PKCS#11 specification:

  Certificate objects (object class CKO_CERTIFICATE) hold public-key or attribute certificates. Other than providing access to certificate objects, Cryptoki does not attach any special meaning to certificates. (§4.6.2)

So no, you can't do anything with a certificate object other than store it and retrieve its attributes.

This is confirmed in the specification of C_VerifyInit:

  The CKA_VERIFY attribute of the verification key, which indicates whether the key supports verification where the signature is an appendix to the data, MUST be CK_TRUE.

A certificate object is not a key and CKA_VERIFY is not listed as a permitted attribute, so it can't be used for C_VerifyInit.

The ability to store a certificate in a token is primarily useful when it's stored together with the private key. You use the private key to sign data (including authentication challenges) and send the certificate signed by a CA as part of authentication. It's useful to store the private key in a cryptographic token because this offers better protection against a compromise of the key. It isn't particularly useful to store a public key or a certificate in a cryptographic token because it isn't confidential¹. The point of putting the certificate in the token is that it's easier to manage the key lifecycle (creation, enrollment, destruction, …) if the key and the corresponding certificate(s) are stored in the same location.

¹  Putting the certificate in a cryptographic token guarantees its integrity, but that's usually pointless because the code using the certificate is outside the token. You don't gain anything by preventing modifications to the certificate if you can change the code that uses the certificate to use a different one or ignore the verification result.


Combination of TLS_PSK and TLS False Start

There is no real problem with applying "false start" to PSK cipher suites. The "false start" thing is about beginning to use the negotiated key to encrypt data before having confirmation (with the Finished message) that the peer really agreed on the same key. In that sense, the peer authentication is still implicit at that point. This is not a worry for "normal" cipher suites. (Note: it might be a problem with SRP, though.)

If you want to target low-power embedded systems, you might want to use the ChaCha20+Poly1305 cipher suites (RFC 7905) which are a lot lighter than AES (especially AES/CCM, which invokes the AES encryption routine twice for each block). If you still stick to AES, and AES/GCM can also be lighter.

Also, while PSK is light (no asymmetric crypto), it has its own issues, namely the need for a shared secret, which is not the easiest thing to deploy; you might want to consider using a non-PSK system with a certificate. If the constrained system is the client, then RSA key exchange involves only public key encryption on the client, and that's lightweight, because RSA public key operations use the public exponent, which is short. Alternatively, some elliptic curves can be light enough for an embedded CPU.

Shameless plug: consider BearSSL. It's not yet ready for production use (in that I have still not made extensive automated verifications against a fuzzing SSL/TLS implementation) but can give a taste of what is doable. On a 48 MHz Cortex-M0+, my C code can do an EC point multiplication in about half a second (half that value if using Curve25519).


Limitations of Elliptic Curve Cryptography?

This is a rather open ended question, but I'll try to answer:

Limitations:

most ECDSA implementations require a secure random generator - if the same random value is reused (for different plaintext) then the private key parameter can simply be calculated;
ECDSA requires a hash function and cannot be (easily?) used for signatures with message recovery (then again, the signatures are generally much smaller than e.g. RSA in the first place);
ECC doesn't provide a direct method of encryption, instead EC-IES is commonly used - which means that that a key pair generation has to be performed and that the public key must be send along with the ciphertext;
ECC is much more efficient than RSA for signature generation and decryption, but it's still much slower than symmetric algorithms;
ECC requires some agreement on which type of curve and curve parameters to use;
support for ECC - especially more modern curves - is lacking from many libraries.

Security:

the fact that the calculations can be performed on relatively small integers (compared to e.g. DH/DSA or RSA) makes the algorithm rather efficient but it may also help quantum crypto-analysis;
many curves - such as the most used curves by NIST over prime fields - require additional verification of the public key to be performed;
RSA is much easier to understand than ECC (and a better understanding aids the security of protocols and implementations);
RSA is still much better researched, e.g. with regards to side channel attacks.


Key cracking: Prefer many small texts over one large text?

Assuming perfect implementations and good block ciphers, it doesn't matter (for any of your questions).

As long as the underlying block cipher is good and has a long enough block length (e.g., 128 bits, as all versions of AES have), any good mode of operation has a security theorem guaranteeing security against chosen plaintext attack for a total of about $2^{b/2}$ blocks of data, where $b$ is the block length. For $b=128$, that's $2^{64}$ blocks, which is more than anyone could ever have time to generate or encrypt (or store).

All this applies to CPA security, which is an even stronger property than resistance to key cracking.


There are a few pitfalls:

File name integrity: signing files one at a time signs the contents of the files.  It (typically) does not protect the file names from tampering.  This could be disastrous in some situations (e.g. an attacker could change blacklist.txt to whitelist.txt).

Set membership integrity: signing individual files does not prevent adding or removing files from the set of files that were transmitted.  In some cases, this is important: if you're transmitting a set of log files, an attacker could selectively remove one that captured incriminating information.  If an attacker has the opportunity to see multiple transmissions, they could add files from an old transmission to the new transmission (essentially a variant on replay attacks).  The files would still have valid signatures individually, so the additions would not be detected.  If you're transmitting a set of user accounts (one per file), an attacker could revert their account to an earlier state (e.g. back to having admin status).

I recommend protecting the transmission as a whole instead of part-by-part, if possible.  The easiest way of doing this is usually to create a tarball or zip file and sign the entire archive.  Signing a list of file hashes is also adequate, but take care when coding the verification mechanism.


BB84 - Bits needed to detect Eve's presence

Remember that Alice and Bob will only compare those measured qubits that they both measured in the same basis. As you said, on average this will be about 50% of the total qubit stream, but this doesn't actually affect the calculation needed.

As you said, Eve will measure using the wrong basis about 50% of the time. However, even when she does measure using the wrong basis, there is still a 50% chance that Bob receives the correct bit-value. To be explicit, say Alice and Bob decide to compare a qubit after learning they both measured it in the standard basis. Alice had sent Bob a |1> qubit, and Eve then intercepted it, but measured it in the Hadamard basis, yielding either |+> or |->. Finally, Bob measured this state in the standard basis, and will have "correctly" measured |1> about 50% of the time.

Given that Eve measures in the correct basis and is undetectable 50% of the time, and she measures in the incorrect basis but is still undetectable about 50% of the remaining 50% of the time, it follows that she is only detectable with probability 25% on each compared qubit. So your bounds do indeed hold, if for a slightly different reason.


What does "with all but negligible probability" mean?

$\Omega(n)$ is a mathematical notation from the same family that the notation $O(n)$ comes from.

To review, $O(n)$ is bounded from above; that is, if we say that $f(n) = O(g(n))$, what we're actually saying is that, for all sufficiently large $n$, there exists a constant $c > 0$ such that $f(n) < c \cdot g(n)$, that is, $f(n)$ grows no faster than $g(n)$.

$\Omega(n)$ is the same, except that it is bounded from below; that is, if we say that $f(n) = \Omega(g(n))$, then (for all sufficiently large $n$) there exists a constant $c > 0$ such that $f(n) > c \cdot g(n)$, that is, $f(n)$ grows at least as fast as $g(n)$.

Hence, what they mean when they say $1 - 2^{-\Omega(n)}$, there's a constant $c$ such that the probability of success is always $> 1 - 2^{-cn}$ (except for possibly small $n$); hence, for large $n$, the probability is quite high (however, that doesn't say what "large" means in this context :-)

In case you're wondering, from the same family, we also have "little-oh" notation $f(n) = o(g(n))$ ("f grows strictly slower than g"), little-omega notation $f(n) = \omega(g(n))$ ("f grows strictly faster than g") and theta notation $f(n) = \Theta(g(n)))$ ("f grows as fast as g, within multiplicative upper and lower bounds")


Ensuring integrity in a multi-user secret vault

Malroy could easily add a malicious secret (i.e. a specially crafted phishing link) by encrypting this secret for all the indented recipients.

Asssume Mallory is also a regular user of the vault. Then if Mallory deposits any malicious information by himself (regardless if it is original or tries to fake some other content), that is impossible to prevent (and doesn't fall under the purview of integrity).

Integrity means, that Mallory can't just change the information placed by Alice - and everyone still thinks the information was put there by Alice. And to achieve that goal it is enough using digital signatures. And of course, everyone can only sign his own secrets.

About the adding of recipients: You said you didn't care about the encryption method, but that actually does matter. Usually you would use hybrid encryption for this kind of storage:

Encrypt the data itself with a symmetric cipher and a random key (one for each file).
Encrypt that key with the public keys of the recipients and send it to them (or make otherwise available).

So adding new recipients is simply encrypting the random key with their public key. And to get the integrity:

Alice signs the encrypted data (symmetric encryption with random key, without the encryption of that key under some public key - that would be user-dependent) with her own signing key.

You have the assumption that every user has a pair of private/public key for encryption, and users know the public keys of others (to make information available). It's not that much of a stretch to also have a signing and verification key for each user.


Number message limits of Galois/Counter Mode (GCM) per key

If you encrypt 264 blocks or more than an attacker can forge encrypted data, i.e. you lose authentication.
Also, be careful about how much total data you encrypt with a key (no matter how many unique IVs are used).  Schneier, et.al. once recommended that with CBC mode you encrypt at most 232 blocks, but with CTR mode you could go to 260 or so blocks due to the fact that you didn't have to worry about reusing IVs with CTR mode like you do with CBC mode (birthday problem).  However, subsequent research suggests that the limit for CTR mode is the same as CBC mode, see this.  However, it depends on how long the data needs to remain secure and your tolerance of risk.  If you want to encrypt data for tape and it needs to be secure for 30 years without being re-encrypted you might want to greatly lower than amount to 220blocks.


Can public key cryptography be equivalent to asymmetric cryptography? If not, what's the difference?

Yes, they are the same in most contexts. The asymmetry is in the keys used, public and private keys. It's definitely not in the encryption and decryption method; in (textbook) RSA the method for encryption and decryption (modular exponentiation) is completely the same. RSA is certainly used for public key cryptography and it is certainly also an asymmetric algorithm.

Key agreement and signature generation are also asymmetric cryptography. You could say that "public key cryptography" puts some more emphasis on the public key, probably hinting that the public key is generated by one party and trusted by another. This is usually the case for PKI(X), the underlying certificate based public key infrastructure used for e.g. TLS / HTTPS.

The public & private key may however not be static or trusted for Diffie-Hellman key agreement where the public / private key pairs are ephemeral (generated per key agreement operation).

Diffie-Hellman however also works with static/trusted keys, so that difference is feeble at best.

Note:

Asymmetric private keys are sometimes called secret keys. I think private keys is the better term. I use the term "secret keys" for symmetric keys (those may not be private to one party but must be kept secret by the parties holding them).


Let's assume that the final design of record structure can be altered for security and various other reasons.

CBC mode requires a uniformly random and unique IV for each invocation with the same key. The IV for the 2nd round is satisfied with this property with the reasons mentioned in the question.

This is basically a deterministic pesudo-random permutation on a large block, and semantic-security could (and should) be added by adding randomization inside the block.
Since this question's been slashed, let's separate the concerns here.
Modern ciphers such as AES are currently not known to be suspectible to KPA. Since every bit of the 2CBC ciphertext is the output from AES encryption function, such concern could be said neglegible.
As said before, seperation of concern.

First we should redesign the record structure, we can have 128 bytes for the site of login, 128 bytes for username, 128 bytes for password, 64 bytes for randomization. (When strings are nul-terminated, the rest of the empty area as said in the question could also be used for randomization)

These are the contents to be encrypted using 2CBC. Next we use a separate key (assuming we have a KDF for deriving encryption and authentication keys) to HMAC-SHA512 the encrypted data and append a 64-byte MAC to the end to form a full 512-byte record.

Also remember, if you're not sure there's the need for message authentication, just have it before you find yourself having to break backword compatibility, gain should always be greater than pain.


Does adding a random number to my data make it secure?

Yes, adding a secret random value $r$ to secret data $s$ and publishing the result $t=r+s$ can leave $s$ confidential; not perfectly so, but arbitrarily close to perfectly.

How much information leaks about $s$ from revealing $t$ depends on the assumed distribution of $r$ and $s$. For example, if $s$ is assumed to be chosen in $\{0,1\}$, and we chose $r$ uniformly randomly in $\{0,\;1,\dots,\;2^{128}-3,\;2^{128}-2\}$, then $t$ fits a 128-bit bitstring. It $t$ is $0$ or $2^{128}-1$, then the adversary has learned $s$ with certainty, but that's unlikely: probability about (just above) $2^{-127}$ for any distribution of $s$, or about $2^{-128}$ if $s$ is chosen by fair coin toss. And in other cases, the adversary has learned nothing about $s$.

More generally, if $s$ is an $m$-bit integer and $r$ is a uniformly random $n$-bit integer, then probability that the adversary learns anything about $s$ from $t$ is at worst about $2^{n-m-1}$ when that's small.

Other distributions of $r$ allow $t$ to use much less bits, without increasing the probability that an adversary learns $s$ with sizable probability, but trade this against more often revealing a little about $s$.

The question mentions that it should still be possible to perform some computation about $s$ from the masked $t$. That holds for addition at least. For example we can perform $t_i=s_i+r_i$ for several secret $s_i$, and the $r_i$ generated pseudo-randomly from a key $K$ and $i$ (using some PRF such as HMAC). $\sum t_i$ then allows to find $\sum s_i$ for one knowing $K$.


How does BB84 fare against an attacker who can entangle qubits?

After some consideration of Lukas' comment, it seems I haven't thought this through.
In fact, Eve will only entangle Bob's qubit with hers if Alice chooses the diagonal basis.
However when Bob also measures the diagonal basis, a quick calculation shows he randomly measures 0 or one, with probability 1/2 each.
So even though Eve learns which bits Bob measured, she will also introduce a 25% error chance as if she had measured them, and she will be detected.


Apple are being asked to put a backdoor, not in the encryption algorithms (which are mathematical constructs that you can't add a backdoor to after you've designed it, and tend to be designed to be free of backdoors), but in their encryption system.

Cryptography isn't just about the basic algorithms but also how you use them. Other big topics in cryptography include protocol design (how basic algorithms are combined to design secure storage and communication systems) and key management (how you generate, distribute, store and revoke keys). The particular aspect that is at stake here is rate limitation, and it is related to key management.

Consider a 4-digit PIN. Suppose that legitimate unlocking of the phone given a PIN must take no longer than 1 second. If you try all PINs (brute force attack), that'll only take a little over 3 hours at most. To make this secure, two things are needed.

The encryption key must be derived not only from the PIN, but also from some other secret component which varies from device to device. Otherwise a resourceful adversary could go through all possible 10000 PINs by trying them on multiple devices.
That secret component must be physically hard to access. You can't just store it in a flash memory. It can't be encrypted. (bootstrapping problem: with what key would you encrypt it?) Recent iPhones and iPads (since the Apple A7 processor) have what Apple calls a “secure enclave” which includes a physically protected processor with some memory for that key. There aren't much details around about the secure enclave; Apple's security guide says what they're willing to say about it.
The secret component must be programmed not to allow an outside entity to try all possible PINs to give out the data encryption key. It's programmed to impose a delay between attempts and lock itself out after too many failed attempts. The same technique is used on other types of devices that must resist physical attacks, such as smartcards (e.g. credit cards with a chip, as is the norm in Europe among other places).

Apple claims, and this is likely, that they cannot give FBI access to a locked phone. This implies that:

Their security architecture follows the idea that I described above, with a secret component in a physically protected memory (that the FBI isn't able to dump). It may not be exactly this, but something with similar properties.
They have not kept a copy of the secret component that's in each phone. (It's probably randomly generated when the device is first booted, and probably regenerated when the device is reset to factory settings.)
They have not programmed the secure enclave with a backdoor, e.g. a secret password that would make it give out either the encryption key or the secret component (from which the encryption key could be calculated for each PIN value).

Apple surely could update their software (the iOS operating system, or more precisely, in fact, I think, the software that runs in the secure enclave) to include a backdoor, e.g. a secret password that would cause the enclave to release the secrets that it stores. Their letter doesn't say so explicitly, but it implies that they could and choose not to. Of course, if such a password existed, there would be no way to limit its use to “legitimate” cases: it would be bound to leak sooner or later, and a secure enclave doesn't know whether it's getting a password from the FBI in a terrorist case, from the FBI in an unauthorized surveillance, or from the FSB, the Ministry of State Security or the Mafia.

The fact that Apple could do it in the future doesn't help for existing devices. If the device can't be started for lack of a PIN, it won't apply the firmware updates.

Note that what I described doesn't rule out the possibility of other attacks. For example, it may be possible to take out the flash memory, put in another flash memory with a different firmware image that contains an update for the secure enclave firmware, and use that to get the secure enclave to relinquish its secret component.

In summary, the answers to your questions are:

What the FBI is asking for would be a backdoor in the encryption system of iDevices. It would be a universal key for iDevices.
Unsoldering a flash chip is well within the FBI's resources. But there are techniques, such as the ones used in smartcards, that allow storing a small amount of data (typically hundreds of kB, I think) and make it much more difficult to extract that data even with relatively fancy equipment.


Why is TLS SRP verifier based on user name?

One of the design goals of SRP is that it should be a zero-knowledge authentication protocol.  This is to say, even the legitimate server should not be able to learn anything about the user's password (other than what it could learn using a generic brute force attack on the verifier).

SRP also assumes that the user may not be able to remember anything except their username and password.  In particular, even though the user may choose the salt when they first compute their verifier, that salt is stored on the server and is sent back to the user by the server whenever the user wants to authenticate.

If the username was not included in the verifier calculation, a malicious or compromised server could try to learn whether user Alice had the same password as user Bob by sending Bob's salt to Alice when she tries to authenticate and seeing if the authentication (using Bob's verifier) still succeeds.  Including the username in the verifier prevents this potential information leak.

Admittedly, this is a fairly minor leak, and probably not of much concern in practice.  Still, it does violate the intended zero-knowledge property of SRP.

Ps. While looking at the SRP documentation to see if it says anything about this, I noticed something curious: the original 1998 paper defining SRP-3 doesn't seem to say anything about the username being included in the verifier calculation.  Indeed, the protocol specification in section 3.2.2 simply says that:

  "To establish a password $P$ with Steve, Carol picks a random salt $s$, and computes: $$x = H(s, P)$$ $$v = g^x$$

However, the SRP-6 paper starts off with:

  "The original protocol, sometimes referred to as "SRP-3" for historical reasons and specified in [4], operates in a group defined by a large safe prime $p$ and a primitive root $g$. Reviewing briefly, the server computes its verifier value $v$ for a user identity $I$ as follows: $$x = H(s, I, P)$$ $$v = g^x$$

The reference "[4]" in the SRP-6 paper is not actually to the earlier paper, but to RFC 2945, which claims to describe the same protocol as the SRP-3 paper but does include the username in the calculation.  So apparently this change was quietly made at some point between the publication of the SRP-3 paper in 1998 and its standardization as RFC 2945 in 2000.


I answer in hopefully didactic order.

  What does the author mean by the intermediate texts exactly?

The intermediate texts after $n$ rounds are the 64-bit quantities $L_n\mathbin\|R_n$, numbering these per the specification of DES. $L_n$ and $R_n$ are the halves.

  Why after the eighth round of encryption the two halves must be equal?

I do not know if the two halves must be equal. But we can prove that it is enough that the two halves are equal, which is what the quoted text does.

Ignoring $\mathsf{IP}$ and $\mathsf{IP}^{-1}$, the normal equations of DES encryption are, for $1\le n<16$:
$$\begin{align}
L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f(R_{n-1},K_n)\\
L_{16}&=L_{15}\oplus f(R_{15},K_{16})&&&R_{16}&=R_{15}
\end{align}$$
As a consequence of the values of the four weak keys $z$, all bits in register $C$ are identical. Therefore $C$ remains invariant as it rotates during encryption. The same applies for $D$. Hence $K_1=K_2=\ldots=K_{15}=K_{16}$. Thus for $1\le i\le16$ we can replace $f(R_i,K_i)$ by a function $f_z(R_i)$ identical in all the rounds, for fixed $w$. The above DES equations turn into
$$\begin{align}
L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f_z(R_{n-1})\\
L_{16}&=L_{15}\oplus f_z(R_{15})&&&R_{16}&=R_{15}
\end{align}$$
If $L_8=R_8$ (that is equals halves after round 8) then, by plugging this into the equations for $n=8$ and $n=9$, we get
$$\begin{align}
L_8&=R_7&&&L_8&=L_7\oplus f_z(R_7)\\
L_9&=L_8&&&R_9&=L_8\oplus f_z(L_8)
\end{align}$$
We plug the top two equations into the bottom ones, and get
$$\begin{align}
L_9&=R_7&&&R_9&=\bigl(L_7\oplus f_z(L_8)\bigr)\oplus f_z(L_8)\\
&&&&&=L_7\oplus\bigl(f_z(L_8)\oplus f_z(L_8)\bigr)\\
&&&&&=L_7\oplus0^{32}\\
&&&&&=L_7
\end{align}$$
We used associativity of $\oplus$, that $f_z$ is a function (and identical in all rounds), that for all 32-bit $X$ it holds $X\oplus X=0^{32}$ (the bitstring of 32 zero bits), which is the neutral for $\oplus$.

Wrapping up, we get $L_7=R_9$ and $R_7=L_9$. Thus "the intermediate texts after seven rounds and after nine rounds of encryption will be equal" within an inversion of left and right that the quotation mistakenly sidesteps.

We plug these results into the equations for $n=7$ and $n=10$, and get
$$\begin{align}
R_9&=R_6&&&L_9&=L_6\oplus f_z(R_6)\\
L_{10}&=R_9&&&R_{10}&=L_9\oplus f_z(R_9)\\
\end{align}$$
After simplification as previously, we get $L_6=R_{10}$ and $R_6=L_{10}$. And so on, up to $L_1=R_{15}$ and $R_1=L_{15}$. For the next step we must take care that the the equations for the last round reverse $L_{16}$ and $R_{16}$ compared to others. We obtain $L_0=L_{16}$ and $R_0=R_{16}$.

The 64-bit plaintext $P$ is such that $\operatorname{IP}(P)=L_0\mathbin\|R_0$ and the 64-bit ciphertext block $C$ is such that $\operatorname{IP}^{-1}(L_{16}\mathbin\|R_{16})=C$. It follows that $P=C$. Call that quantity $m$ and we have $\operatorname{DES}_w(m)=m$, Q.E.D.

  Why are there $2^{32}$ fixed points?

There are $2^{32}$ possible values for $L_8$, thus for intermediate text $L_8\mathbin\|R_8$ with $L_8=R_8$. By the above reasoning, each gives a value of $m$ with $\operatorname{DES}_w(m)=m$ for a given weak key $w$. And the values thus obtained must be distinct: DES encryption is deterministic for a given key $w$, thus the same input value can't give different intermediate texts after 8 rounds.

Hence there are at least $2^{32}$ fixed points $m$ for a given weak key $w$. I do not know how many more there might be, for each of the four $w$. However, we can tell that the counts are the same for the all-zero and all-one $w$ (ignoring parity bits); same for the two other weak keys. That follows from DES's complementation property.

  How to find fixed points for DES weak keys

One option is to modify some DES encryption code to start at round 8 with $L_8=R_8$. The ciphertext will be a fixed point for the weak key used. We can find $2^{32}$ of these for a given weak key $w$, by using a counter for $L_8$. When that's done for a weak key $w$, we can derive fixed points for the complement of $w$ by using DES's complementation property.


Linear Cryptanalysis - possible without plaintext?

Yes, linear cryptanalysis may still be possible, depending upon the distribution on the plaintexts and the specifics of the block cipher.

For instance, suppose we know that the plaintext is English encoded in ASCII.  Then we know that the high bit of each 8-bit byte is zero.  We may also know some additional linear approximations that hold on the plaintext that hold with non-zero bias.  This may be enough to mount linear cryptanalysis, e.g., if you can find a linear characteristic for the whole cipher that only involves those bits of the plaintext (only the high bits of each byte) and not any other bits of the plaintext.

As I recall, there has been results showing that ciphertext-only linear cryptanalysis of DES is possible, assuming that the plaintexts are ASCII-encoded English text.  This result might even have been included in Matsui's original paper on linear cryptanalysis; I cannot remember.


Reading the original paper, I figure out the question.
This voting scheme employed the well-known undeniable signature scheme, proposed by Chaum and Van Antwerpen in 1989 (or Chaum 1990 or Chaum and Van Antwerpen 1991).

KeyGen: The RA is a signer and has a public key $X = g^x$ and a secret key $x$
Sign: For a message $m \in \mathbb{G} = \mathbb{Z}_p$, the signature is $\sigma = m^x \in \mathbb{G}$. (In your case, $m = r_{id}$.)
Cofirmation: The verifier (the polling station) and the signer (the RA) interacts to verify a token $(r_{id},\sigma)$ from a voter is correct or not.

In confirmation, the RA proves that $\log_g(X) = \log_{r_{id}}(\sigma)$. You can find the standard $\Sigma$ protocol for this confirmation, say, the $\Sigma$ protocol for the DDH language.

You can find the $\Sigma$ protocol for the DDH language in the lecture notes available at the web.

Section 5 of Berry Schoenmakers: Lecture Notes - Cryptographic Protocols
Lindell: Sigma protocols and Zero Knowledge (Session 5 of Winter School on Secure Computation and Efficiency)


Is ChaCha20 alone sufficient for securing data-at-rest?

You really don't want to use ChaCha20 alone in (nearly) any situation.

What ChaCha20 does for you is to prevent attackers from (passively) reading your data, which is good. But ChaCha is a so-called stream cipher which works by XOR'ing a pseudorandom pad with the message (your file at rest). However it is for this very way of working that ChaCha doesn't prevent attackers from (actively) reading your data if you allow them to decrypt anything but the stored cipher text.

If an adversary now gets hands-on your drive / file he can manipulate the file. For example assume it's your next day's financial transaction plan. An attacker who knows where the account ID of the receiver lies and knows who should receive the transaction can flip the bits at that position in a way that his bank account is the target.

Poly1305 is designed to prevent this kind of attack by assuring that the data hasn't changed without knowledge of the key. Assuming the key for Poly1305 is unknown to the attacker he can't correctly update the authentication tag. If he now changes a single bit of the cipher text the verification will fail and you'll notice that somebody has changed your file, protecting you from a malformed operation ( / transaction).

TL;DR: ChaCha20 protects your file from being (passively) read, but not from being manipulated, which may easily cause severe attacks. So you really want to use Poly1305 in addition to ChaCha20.


Why Bulletproofs protocol needs to raise $u$ to power $x$ in Protocol 1?

One of the authors give an anwser:

  Protocol 2 proves the following statement: "given a point P, there
  exist vectors a and b such that P = aG + bH + *G". This problem
  is that this statement isn't very useful. If I give you a point P,
  it's nice to know that I can deconstruct it into some sort of inner
  product thing, but in practice you typically know what  should
  be, and you want a proof that it's the correct thing. We'll call the
  statement being proved here Statement 1.

  So the statement we really want is "Given P and c, there exist vectors
  a and b such that P = aG + bH and c = ". Same as above, but I've
  moved the actual inner product "out of hiding" by taking it out of P
  and making it explicit. Call this Statement 2.

  The obvious way prove Statement 2, which we want, given only a proof
  system for Statement 1, which we have, would be for the verifier to
  compute "P' = P + cG" and ask for a proof of Statement 1 on P'. This
  doesn't work, because a malicious prover could simply prove Statement
  1 on a point P', then choose c to be whatever he wanted and provide c,
  P = P' - cG to a verifier.

  There are a few ways to prevent this. The tactic chosen in the paper
  is to force the prover to choose P before he learns what G is. Then he
  can't set P = P' - cG; for a given P' this is either true or it isn't!
  Instead, the prover is forced to choose P' = P + cG, which is exactly
  what we want him to.

  So how can we force the prover to choose P before knowing G? Easy,
  hash P to get a new value x and replace G with xG.


What is the difference between a PRF and a PRP, and are cryptographic hash functions the same as HMAC (PRFs or PRPS)?

I read one answer to a similar question that put forth that a hash function is distinct from a PRF, however I've also found materials purporting that cryptographic hash functions are PRFs, and I'm not sure now.

Those latter materials are wrong.

Random function

A mathematical function (i.e. a "pure" function) whose output values depend only on its inputs, but whose outputs are random.  Think of it as a (potentially infinite) table with two columns:

The first column lists every possible input exactly once;
The second column has been filled-in ahead of time with values selected uniformly at random from the function's range.

A random function is an ideal object—something we know can't practically exist at the sizes we're interested.

Pseudorandom function family (PRF)

A deterministic computer algorithm such that it:

Takes a secret key and a (not necessarily secret) input;
Runs in polynomial time;
Has the property that if you choose the key secretly and at random, an adversary would find it so difficult to crack that they wouldn't even be able to tell it apart from a random function in any practical amount of time, even if they know the algorithm and can choose the non-key input to it.

Note that a PRF is intended to act as a practical aspiration—something that cryptographers hope that a practical computer algorithm can achieve.  Note that there isn't actually hard proof that it's possible to implement a PRF in real lie—the existence of PRFs is a conjecture.

Note also that I boldfaced secret over and over—that's an important little detail here.

Random oracle model

A type of cryptographic security proof where a hash function is modeled as a random oracle—a public random function that is accessible both to honest parties and adversaries.

Note that just like I boldfaced secret above, here I boldfaced public, because that's a key difference.  A PRF takes a secret key that the honest party must choose at random, and thus a PRF is supposed to behave like a random function that only that party is able to evaluate. Whereas crypto hash functions like SHA-256 are designed to resist attacks in scenarios where there's no secret key. For example, an adversary isn't supposed to be able to find two SHA-256 inputs that collide in any practical amount of time, even though no secret about the algorithm or computation is kept from them. So ideally, hash functions should behave like random functions that are known to every party.

Note that another confusion you'll come across often is people who use the term "random oracle" to mean random function.  I like to think of it with this analogy: being a random oracle is like being the President of the United States.  You have to be a natural born citizen and 35 years or older, but what makes them President isn't that they fulfill those two requirements, but rather the role they play in the political system.

Likewise, a random oracle must be a random function, but what makes that function a random oracle isn't just the fact that it's random, but rather the role it plays in some scenario.

Now, the rest of your questions:

  Also, is HMAC a PRP because of being keyed?

HMAC is routinely conjectured to be a PRF. It's not a permutation because there must exist multiple inputs that produce the same output. And thus it cannot be a PRP, which is a subtype of PRFs with the additional stipulation that for each key, the algorithm must implement a one-to-one function (a.k.a. a permutation).

  I thought that a cryptographic hash function being keyed (i.e., with a constant prepended/appended to the input) was what determined whether it was a PRF or a PRP, however upon searching more I've become increasingly confused.

Your mistake here is thinking that being "keyed" is a contextual property of how you choose to use the function in one scenario, but you really need to look at it as an intrinsic property of the function itself, or otherwise you'll indeed get confused.  SHA-256 has just one input, and that input is for a message that the function doesn't demand that you keep secret. So no, SHA-256 definitely isn't secret keyed function.

If you need a PRF, however, one way to build one is HMAC-SHA-256, a construction that defines a function that does take a separate key (that it demands that you choose secretly at random) and message.  Then, under the hood, HMAC-SHA-256 combines those two inputs in a specific way and hands them to SHA-256.

But the fact that HMAC-SHA-256 is a keyed function that's built out of SHA-256 doesn't mean that SHA-256 is "sometimes a keyed function"—it just means that you can build keyed functions out of unkeyed building blocks.  Again, "keyed" should be understood as a fixed, intrinsic property of how the function is defined, not a variable contextual fact about how it's used in some scenarios.


Permutation for which an inverse is a hard problem

It is obviously possible; one simple example is the function $f(x) = g^x - 1 \bmod p$, where $p$ is a large prime, and $g$ generates the entire group $\mathbb{Z}_p^*$; this is permutation over the range $[0, p-1)$, and is difficult to invert if the discrete log problem is hard.

What may be more difficult is to design an efficient hard-to-invert permutation; most efficient permutations are designed as a composition of trivially invertible permutations (and hence the result can be easily inverted).


EdDSA Signature Algorithm - hash of secret key

Ed25519 needs two secret values:

The private scalar (~256 bits)
A hash prefix used derive a secret nonce from the message (256 bits)

Using the same value for these is bad style, as is deriving one of them from the other. You could also use their concatenation as private key, but that'd double its size to 512 bits. So Ed25519 chose the clean solution of deriving both from a 256 bit master secret.


How does OAEP improve the security of RSA?

Well, yes, everyone (or, at least, everyone who can use the public key) knows the hash function H and G; so we can assume that an adversary knows them as well.

You ask:

  If YES: How does it help the security, if he just can decode
  the padding and read the message?

Well, he can't decode the padding; the ciphertext has been encrypted using RSA, and he doesn't have the private key; so he can't get at the padded version.

Here's how OAEP works; you take the plaintext message $m$ to send, you pick a random value $r$, and compute the function:

$Padded = OAEP(m, r)$

(with H and G as parts of OAEP).  Then, once we have that, we encrypt it using the base RSA public operation (using the public key):

$Ciphertext = RSA(PublicKey, Padded)$

The $Ciphertext$ is what's actually sent; because it is encrypted using RSA, the attacker cannot recover $Padded$.

So, if the OAEP operation doesn't prevent an attacker from decrypted the ciphertext in this straightforward manner, why is it there at all?

Well, raw RSA has some nastly properties (called an homeomorphic property), namely:

$RSA(k, A) \times RSA(k, B) = RSA(k, A\times B)$

(where $\times$ is implicitly modulo the public key modulus).

Because of this property, using raw RSA to directly encrypt plaintexts is almost always the wrong thing to do; there are clever ways to use this homeomorphic property to recover plaintext.

What the OAEP function does is try to mimic a random function between plaintexts and padded versions; because we present the raw RSA operation with effectively random texts, these homeomorphic properties are no concern.


Prime factorization of 700 decimal digits number

No an attacker will not be able to factor your $n$ (e.g. break it).

Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size.

As for the largest known-broken modulus size, this would be a 768-bit modulus and it is conjectured that nation-state attackers are able to factor 1024-bit moduli using their ressources.

You have chosen 400 digits and 300 digits. While this is safe in this instance, this is unusual to do, because too much unbalancedness can help the attacker as he can apply attacks that find small factors first (by trial division or ECM). The standard way of approaching this is to generate two equally large primes (in terms of digits) and ensuring that $|p-q|>2^{k/3}$ (where k is your modulus bitlength), which will hold anyways with overwhelming probability if you choose both primes independently at random.


How DES/AES can guarantee by feeding different secret keys, the encrypted outputs are different?

I am learning the meet-in-the-middle on DES attack.

I don't know of any meet-in-the-middle attack on DES; I'll assume you're talking about 2DES (where you apply DES with one key $k_1$, and then apply another iteration of DES (possibly in decrypt mode) with another key $k_2$.

  why can we guarantee to find one and only one pair of k1 and k2?

We don't.  In fact, if we're just looking at a single plaintext/ciphertext block, there are likely to be circa $2^{48}$ $k_1, k_2$ pairs that map that plaintext block into that ciphertext block.

That is not a major obstacle; what we typically assume is that we have a second plaintext/ciphertext block that can be used for validation; given a candidate $k_1, k_2$ pair, we try those keys on our second plaintext block (and see if we get the second ciphertext block).  If it passes that, then it is most likely the correct $k_1, k_2$ pair.

This second check (which we may need to perform $2^{48}$ times) is less costly than the original MITM search, and so we mostly ignore that cost when estimating the cost of the attack.

  One step further, how DES guarantee that by taking the same plaintext and different secret key, the encrypted outputs can never be the same?

It doesn't; we generally assume that differing keys define different DES permutations (and so two different keys can map the same plaintext block into the same ciphertext block).


Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgård?

No. That is about as accurate as saying that airplanes are based on motorcycles, because they both have engines.

In MD, the input to the hash is converted to a key, which is used by a block cipher to encrypt the initial value, then the entire encrypted value is the hash.

In a sponge based hash, the input is XOR'd into the initial value, then the entire value is ran trough a permutation, and finally a small piece of the permuted value is used as the hash


No, they aren't a group.

Justification: We know that the subgroup generated by DES is very large.
If (any of the variants of) 3DES formed a closed group, then the subgroup generated by 3DES would be no larger than $2^{168}$.  We know the latter is not the case.  Therefore, the former is not the case, either.

Also, for the EDE variants of 3DES, it is easy to see that the size of the subgroup generated by 3DES is the same as the size of the subgroup generated by DES (consider what happens with EDE-3DES when you set all three subkeys equal to each other; the result is equivalent to plain DES).


Just a super basic question - Does the key create the algorithm?

The key does not create the algorithm.

The algorithm is a fixed, publicly known set of steps. Clearly, a fixed, publicly known set of steps is not capable of encrypting anything.

So we include some secret information into the steps in the form of a key. A key for a symmetric encryption algorithm is a random sequence of bits that is kept secret. The knowledge of this secret random sequence of bits is what enables one to perform the encryption/decryption steps - and what prevents anyone else from doing the same.

For example, the AES algorithm uses the following steps:

Add key
Add constant
Mix Columns
Substitute bytes

The Add key step is the same instruction for everyone who uses the algorithm, but the data that the instruction operates on is different for everyone because of the key.

This may be the source of the confusion. There are two things going on in an encryption algorithm:

The instructions, or steps that are applied
The data, which are the bits of information that the instructions operate upon

The instructions (the algorithm) are fixed and publicly known. The key is data, and it provides the source of secrecy that enables one to compute the encryption/decryption operation. The plaintext and ciphertext are also data, which are operated upon by the instructions in conjunction with the key.


Scheme is not IND-CPA for any message longer than one block. I'll include a image of CBC mode below for reference (Source: Wikipedia).

Suppose instead of block cipher encryption we have plaintext xor-ed with the key as you propose. You'll note that for message block 1, $M_1$, the ciphertext block $C_1 = M_1 \oplus IV \oplus Key$. Similarly $C_2 = M_2 \oplus C_1 \oplus Key$ Substituting for $C_1$ we get $C_2 = M_2 \oplus M_1 \oplus IV \oplus Key \oplus Key$ which reduces to $C_2 = M_1 \oplus M_2 \oplus IV$. Knowing this we can build a distinguisher $D$.

Suppose we send two messages $M0$ and $M1$ to the encryption oracle and get back $C$. $D$ will take $C$ and check if either $C_2 = M0_1 \oplus M0_2 \oplus IV$ or $C_2 = M1_1 \oplus M1_2 \oplus IV$ (note that the $IV$ is not secret), returning whichever plaintext corresponds to $C$. Clearly this distinguisher has non-negligible advantage, and thus the scheme is not IND-CPA for messages longer than one block.


Is there a practical zero-knowledge proof for this special discrete log equation?

Let $\#G$ denote the number of elements in the group. In your particular case, $\#G = \varphi{}(n)$ (and even $\#G = n-1$ if $n$ is prime). Let $\xleftarrow{\$}$ denote a uniformly random sampling from a finite set of elements. Furthermore, $\mathbb{Z}_m$ denotes the set of non-negative integers smaller than $m$ and $\stackrel{?}{=}$ denotes a equality test between two values to be performed by the Verifier. The Verifier accepts if and only if all such equalities hold.

Public knowledge: $g, h, a, b, c$

Claim: knowledge of $x_1, x_2$ such that $(a,b,c) = (g^{x_1},x_2h^{x_1},h^{x_2})$

Interactive proof:

$\begin{matrix}Prover & & Verifier\\
v,s,s',s'' \xleftarrow{\$} \mathbb{Z}_{\#G} & & \\
 & \xrightarrow{\begin{matrix}(g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v\end{matrix}} & & \\
& & k \xleftarrow{\$} \mathbb{Z}_{\#G} \\
& \xleftarrow{k} & \\
r \xleftarrow{} x_1 + ks \mod \#G & & \\
r' \xleftarrow{} x_2 + ks' \mod \#G & & \\
r'' \xleftarrow{} v + ks'' \mod \#G & & \\
& \xrightarrow{r,r',r''} & \\
& & g^r \stackrel{?}{=} a(g^s)^k \\
& & h^{r'} \stackrel{?}{=} c(h^{s'})^k \\
& & b^{r''} \stackrel{?}{=} ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v\end{matrix}$

The proof can easily be made non-interactive by applying the Fiat-Shamir heuristic, i.e.: $k = \mathcal{H}(g,h,a,b,c,\ldots)$ where $\mathcal{H}$ is a suitable hash function which is applied to the input of the protocol and (optionally) some extra sources for randomness such as the time or the Prover's first message.

Theorem 1. This interactive proof is complete, i.e.: if the claim is correct, the Verifier will accept.

Proof. Proof by construction.

$g^r = g^{x_1+ks} = a(g^{s})^k$

$h^{r'} = g^{x_2+k{s'}} = c(h^{s'})^k$

$b^{r''} = (x_2h^{x_1})^{r''} = (x_2h^{x_1})^{v + ks''} = ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v$ $\square$

Theorem 2. This interactive proof satisfies the special soundness property, i.e.: only if the claim is true will the Verifier accept (and, moreover, any two accepting transcripts of this proof applied to the same claim and starting with the same initial message will leak the witnesses $x_1$ and $x_2$).

Proof. We prove the "moreover" part of the theorem as it implies regular soundness. Given two transcripts $T_1$ and $T_2$, we can first compute $s$ from $T_1.r - T_2.r = (T_1.k - T_2.k)s$ and then compute $x_1$. The same goes for $r', s'$ and $x_2$.

Of course, if $T_1.r = T_2.r$ and $T_1.r' = T_2.r'$, then this does not leak the witnesses per se. However, in this case $T_1$ can only be different from $T_2$ if $T_1.r'' \ne T_2.r''$ from which we can calculate $v$ and $s''$. The latter value allows us to calculate the witness $x_2 = (x_2^{s''})^{s''^{-1}}$. $\square$

Theorem 3. This interactive proof is special honest-verifier zero-knowledge.

Proof. There exists a simulator algorithm $\mathcal{S}$ which takes as input the claim $(g,h,a,b,c)$ and a challenge $k$ and outputs a transcript $S$ of the interactive proof which is indistinguishable from the transcript $T$ of an authentic interaction proving the same claim.

The simulator $\mathcal{S}$ generates a valid conversation $(((g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v),(k),(r,r',r''))$. Let the elements of this conversation represent variables which are to be assigned a definite value. The simulator $\mathcal{S}$ does this as follows.

$ \begin{matrix}r,r',r'' \xleftarrow{\$} \mathbb{Z}_{\#G} \\
 v \xleftarrow{\$} \mathbb{Z}_{\#G} \\
 (x_2h^{x_1})^v \xleftarrow{} b^v \\
 (g^s) \xleftarrow{} (g^ra^{-1})^{k^{-1}} \\
 (h^{s'}) \xleftarrow{} (h^{r'}c^{-1})^{k^{-1}} \\
 (x_2^{s''}) \xleftarrow{\$} G \\
 (h^{x_1s''}) \xleftarrow{} (b^{r''}b^{-v})^{k^{-1}}(x_2^{s''})^{-1} \end{matrix}$

There cannot exist a distinguisher $\mathcal{D}$ who can distinguish between an authentic transcript $T$ and a simulated transcript $S$. The distributions of $T$ and of $S$ are identical. $\square$


How to calculate Enc(-m) from Enc(m) in Paillier cryptosystem?

Actually, computing the inverse modulo $n^2$ using (say) the Extended Euclidean method is exactly what you do.  If $c = g^m r^n \bmod n^2$ is an encrypted version of $m$, then $c^{-1} = (g^m r^n)^{-1} = g^{-m} (r^{-1})^n$ is a representation of $-m$ (because if $r \in \mathbb{Z}^*_n$, so is $r^{-1}$)

That $enc(m) * enc(-m)$ isn't precisely 1 isn't relevant; however if we use different randomness $r$ and $s$ during the separate encryptions (as we're supposed to), it'll actually be $r^ns^n = (rs)^n$.  However, there is lots of encrypted representations of 0; while 1 is such a valid representation, $(rs)^n$ is as well.


Are there any real protocols secure in the random oracle model that have been broken in practice?

The one real example out there is RMAC. This was proposed in this NIST standard, and was shown to be broken for some instantiations in practice in the paper Analysis of RMAC by Knudsen and Kohno. The construction is proven secure in the random-oracle model in the paper: On the Security of Randomized CBC–MAC Beyond the Birthday Paradox Limit: A New Construction from FSE 2002. (Although, when instantiating with a block cipher it's more like the ideal cipher model.)

Another, less convincing example is to generate a MAC by compute $SHA(K\|M)$ which is vulnerable to extension attacks, but is secure in the random-oracle model. This is less convincing since most people knew that this was vulnerable to extension attacks.


How bad is it to use the identity function as hash for ECDSA?

There is a way to generate forgeries for (EC)DSA when the hash function is not one-way:

Let $n$ be the order of the group, $P$ a generator, and $Q = aP$ for some secret $a$;
Pick arbitrary $\alpha$ and $\beta$ $\in \{0, \dotsc, n\}$;
$r = x \bmod n$, where $(x, y) = \alpha P + \beta Q$;
$s = r \beta^{-1} \bmod n$;
$h = s \alpha \bmod n$;
Invert $H(h)$ to get $m$. Since we are using the identity function here, $m = h$.

You can verify that $(h s^{-1}) P + (r s^{-1}) Q = (\alpha P + \beta Q)$, whose $x$ coordinate is precisely $r$. Therefore this is indeed a valid signature.


What are the number of output bits of the internal function F used in BPS algorithm?

Yes, in BPS, if the internal function $F$ is a block cipher, then $f$ is its block width, thus 128 for AES (for all key width variants). That's clear enough in the paragraph quoted in the question:

  We denote by $f$ the number of output bits of the internal function $F$. (...)
  If $F$ is a $f$-bit block cipher (...)
  We denote by $F_K(x)$ the application of the block cipher $E$ with the key $K$ on the plaintext $x$ ($F_K(x)=E_K(x)$), (...)


Is there an example of a “robust, yet not private” SMC protocol?

Sure.
Parties:  more than 1
Input:  each party has a secret input
Output:  empty string

"Protocol":  Each party broadcasts their secret input then outputs the empty string.

That is robust for arbitrary thresholds, but is

not private against even a single semi-honest adversary.


Are there any NIST curves with pairings?

Are there any standard curves which support pairings?

No, there are currently no pairing-friendly NIST curves; NIST has not announced any plans to approve of either a pairing-friendly curve, or any cryptographical operation that involves a pairing operation.


Encrypt twice with DES using same key ? $\operatorname{DES}(\operatorname{DES}(x,k), k)$

Does encrypting with $\operatorname{DES}$ in the following way $\operatorname{DES}(\operatorname{DES}(x,k), k)$ make $\operatorname{DES}$ as strong as $\operatorname{2DES}$ with 2 keys?

No.

  So overall $2*2^{56} = 2^{57}$ just like meet in the middle complexity, right ?

This time estimate ignores the memory requirement that the meet-in-the-middle attack on 2DES requires.

Memory is cheap, but it's not free.  The estimate of $2^{57}$ operations to break 2DES ignores the overhead of both the memory and the interprocessor communication (it's unlikely that a single processor will be able to perform $2^{57}$ DES operations in an acceptable period of time).  As these objections can be addressed, it's not a lie to ignore them, but they are nontrivial considerations.

In contrast, finding the key for $DES(DES(x,k), k)$ requires no memory, and can be trivially parallelized.


How would I make a decoder agnostic steganographic file?

I will assume you're referring to steganography in images.

The most important thing would be to use a color space that is likely to be recognizable 20 years in the future. For this, sRGB is a good candidate. It was created more than 20 years ago, in 1996, and it is still the most popular color space in use. It's safe to bet that, in 20 years, it will not be forgotten. You can use traditional LSB steganography to encode information. As long as the color space is preserved, it should be compatible with whatever future software you are using (or compatible software that is easy to find).


Can I find the encryption key if I know the plain text and the encrypted text (DES and AES)?

The most cost-effective way to do this is to try each key and see if it works.  The expected number of trials is $2^{55}$ with DES, $2^{127}$ with AES-128, and $2^{255}$ with AES-256.

You can speed the search up by making many trials in parallel, e.g. by using a million DES circuits making one trial every microsecond, which will give an answer in a few hours, at most under a day—a task that has even been commercialized (note: I do not endorse this commercial service; I am only mentioning it for practical scale comparison).  Note that parallelizing the search doesn't change the overall cost: powering a single circuit for an hour will cost approximately the same energy, and same number of rubles, as powering sixty circuits in parallel for a minute.

If you have many keys $k_i$ which you want to recover any one of given their respective ciphertexts for a common plaintext, then you can do better with a parallel machine that saves repeated effort using Oechslin's rainbow tables.  Say you have $n$ target keys.  A machine parallelized $n^2$ ways with each parallel circuit not much larger than an AES-128 circuit, with a small constant amount of memory for each circuit, can give you your first answer with probability $p$ in about $2^{128}p/n^3$ time, at the same cost as about $2^{128}p/n$ AES-128 evaluations.

For AES-128, these numbers are large, but not unimaginably so.  The Bitcoin network today performs about $30\times10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year.  If we had trillion ($10^{12}$) AES-128 circuits in parallel attacking any one of a million ($10^6$) keys, we would break at least one of them with high probability using a couple hundred thousand times the annual cost of the Bitcoin network (which has been increasing exponentially since about 2015), assuming the cost of one AES-128 evaluation is approximately the same as that of SHA-256.

Can you break AES-128, or any generic 128-bit function, using this method?  No.  Can humanity?  Maybe.  But definitely not AES-256 unless there's a cryptanalytic breakthrough.  (Quantum computers don't make much of a dent in AES-256 or even AES-192 either.)


Seeking clarification of OTP & MAC discussion

Taken in order:

  Any hash can be used for message authentication, including MD5?

No.  A message authentication code or tag is generated by using a keyed cryptographic hash function.  Raw MD5 is an [unkeyed] cryptographic hash function.  One of the goals of this type of primitive is that it should not be feasible to create a valid tag for a message without the key.  If you have no key, as with MD5, it's easy for anyone to compute a valid hash of the message. MD5 might be used internally within a MAC algorithm, but not as a MAC algorithm.

  The MAC tag must be encrypted with the OTP?

No.  In fact, you can see in the 2nd to last paragraph of kasperd's answer that when an appropriate (information theoretically secure) construction is chosen, it does not matter if the tag is encrypted with the OTP or not, though there is some additional cost for encrypting it with the OTP with no corresponding security gain.

  The size of the hash only affects the probability of a successful forgery?

Yes, that is the primary goal of the tag, which is the output of the MAC algorithm.

  The inherent security proof of a OTP is maintained even by appending a MAC to the plain text, then encrypting?

This is true if the MAC algorithm provides information theoretic security, such as Wegman-Carter authetication, as kasperd pointed out in his answer.  This is not true for other MACs, such as HMAC which was the original object of the question.


Is there any public-key cryptosystem that is (possibly) secure against $NP\cap coNP$ adversary?

Hash based signatures come to mind; essentially, to break them, you need to find a (second) preimage of the underlying hash function, and that problem is not known to be within $NP\cap coNP$.
Of course, the current instantiations are based on fixed-sized hash functions (and hence are not within $NP$); however generalizing the concept to variable length hash functions should be fairly straight-forward.


RSA: Proving that $p+q-1 < 3 \sqrt{N}$, where N = pq and p,q are prime?

There is likely an assumption on the sizes of $p$ and $q$ that you haven't listed in your question that exists in the description. For example, Boneh's description of Wiener's attack has that $q<p<2q$.

With that assumption, we can prove the inequality.

We know that

$$p+q < 2q+q$$
$$p+q < 3q$$

Furthermore, since $N=pq$ and $p>q$, we have that $\sqrt{N} > q$, or $3\sqrt{N} > 3q$. So

$$p+q < 3q < 3\sqrt{N}$$

In your inequality, you have $p+q-1$ which is clearly smaller than $p+q$, so everything works out, $p+q-1 < 3\sqrt{N}$.


What is the collision resistance of a 2048-bit hash based on SHA-3?

No.

It turns out that for a tree composition and concatenation of $n$-bit hash functions, collisions can be found at $O(2^{n/2}\operatorname{poly}(n))$ cost.  So it still has pretty much 256-bit collision resistance.  The additional complexity buys you essentially nothing.

Note that 256-bit collision resistance is already obscenely high, against all plausible attackers (and there's no advantage even if you have a quantum computer); anything beyond it is completely meaningless.

Side note: If the adversary knows the $B_i$, the antiforgery property of a MAC, derived from the prefix-PRF $m \mapsto \operatorname{SHA3-512}(k \mathbin\Vert m)$, is not relevant.  If the adversary doesn't know the $B_i$, then this is not the scenario of collision resistance—but you're not going to get better than ‘512-bit security’ anyway, which is already (completely meaningless)^2.

Rather than worry about how to obtain (completely meaningless)^4 security levels from the cryptography, you should focus on writing a clear statement of your application's security model, making sure it's easy to audit and understand in the context of what you're trying to achieve, and making sure you've covered all possibly relevant threat models.


In the referenced paper, $M^{(i)}_{j,k}$ is bit $k$ of the 32-bit $M^{(i)}_j$, with $-5\le i<80$, $j$ the same index as in $m_j$ with $0\le j<6$, and bit index $k$ is with $0\le k<32$.

The question's two statements are thus equivalent to
$$\forall i,0\leq i\leq79,\quad M^{(i)}_0=\begin{cases}
\mathtt{00000000_h}&\text{if }m_0^{(i)}=0\\
\mathtt{00000002_h}&\text{if }m_0^{(i)}=1
\end{cases}$$


Is it possible to change the generator without knowing the private key used?

For example, prover sends P = xG and verifier somehow sends back P = xH without learning x.

Yes; if the verify knows that $H = yG$, he just computes $P' = yP = xyG = xH$


As an above comment said, you have $2^{24}$ different combinations to test as the key. However, if you don't have anything to verify with (i.e. the plaintext is still random data), no.


Security of a parallelizable block cipher mode

One of the basic security requirements of a block cipher mode of operation is that it is indistinguishable under chosen plaintext attack (IND-CPA).  Essentially, this means that, if an attacker chooses two messages $m_A$ and $m_B$ and the defender randomly returns either $\text{Encrypt}(K, m_A)$ or $\text{Encrypt}(K, m_B)$ (with $K$ kept secret from the attacker), the attacker should be unable to determine whether the defender chose $m_A$ or $m_B$.

This scheme is not secure under that definition.  Here's how an attacker can win (assume $n$ is the block size).

The attacker submits $m_A = 0^n \| 0^n$ (two zero blocks) and $m_B = 0^n \| 0^{n-1}\|1$ (a zero block, and a block that is all zeros except the last bit).
If the defender chooses $m_A$, it will return $E(K, 0^n \oplus BT_0) \| E(K, 0^n \oplus BT_1) = E(K, IV) \| E(K, IV \oplus (0^{n-1} \| 1))$.  In other words, the output blocks will be different.
If the defender chooses $m_B$, it will return $E(K, 0^n \oplus BT_0) \| E(K, (0^{n-1}\|1) \oplus BT_1)$, where $E$ is the block cipher.  This simplifies to $E(K, 0^n \oplus IV \oplus 0^n) \| E(K, (0^{n-1}\|1) \oplus IV \oplus (0^{n-1}\|1)) = E(K, IV) \| E(K, IV)$.  In other words, the output blocks will be the same.

The attacker can easily distinguish which plaintext the defender chose.  This violates IND-CPA, which often leads to vulnerabilities in real-world systems.

Counter mode seems to offer similar benefits without the security problems: parallelizable, random access, etc.


I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and therefore factor $N$), if $e<\sqrt{N}$. See Boneh's 20 year survey of attacks on RSA. See that paper and the reference within for the algorithms, etc.

Since then, the bounds for $e$ have been update somewhat, but still requires leaking the same number of bits. Also, random subsets of bits are sufficient to factor where $(1-\frac{H_r}{r})\log{N}$ bits of $p$ are known ($H_r$ is the r-th harmonic number).


Why is elliptic curve cryptography not widely used, compared to RSA?

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, and relevant standards have existed since the late 1990s. Also, both RSA and elliptic curves have been covered by patents, but the RSA patents have expired in 2000, while some elliptic curve patents are still alive.

One perceived, historical advantage of RSA is that RSA is two algorithms, one for encryption and one for signatures, that could both use the same key and the same core implementation. But this is not a real advantage because it is usually a bad idea to use the same key for both encryption and signatures. Also, you can mathematically use the same private key for ECDH (key exchange) and for ECDSA (signatures), so that's really not an "advantage" of RSA over EC at all.

Another advantage of RSA is that its mathematics are somewhat simpler than those involved for elliptic curves, so many engineers feel that they "understand" RSA more than elliptic curves; again, a fallacious argument, since implementation of cryptographic algorithms is fraught with subtle details and best left to professionals -- and there is no need to understand the internal mathematics of a library to simply use it (we could make this argument semi-valid by pointing out that RSA relies on the hardness of factorization, which has been studied for 2500 years, whereas discrete logarithm on elliptic curves can only sport about 25 years of research).

The only scientifically established advantaged of RSA over elliptic curves cryptography is that public key operations (e.g. signature verification, as opposed to signature generation) are faster with RSA. But public-key operations are rarely a bottleneck, and we are talking about 8000 ECDSA verifications per second, vs 20000 RSA verifications per second.

An additional interoperability issue is that elliptic-curve operations can be made over curves of distinct types, and can be widely optimized if you stick to a specific curve known when the code was written. There is no security issue in using the same curve for many distinct people with distinct key pairs. But it means that most implementations will only support two or three specific curves. NIST has defined 15 standard curves. However, in practice, many implementations only support two of them, P-256 and P-384, because that's what is recommended by NSA (under the name "suite B")(a notorious example is NSS, the cryptography library used by the Firefox Web browser for SSL).

There are two ANSI standards for elliptic curves, X9.62 for signatures (partially redundant with FIPS 186-3, but much more detailed), and X9.63 for asymmetric encryption.

So there is a lot of political push for the adoption of elliptic curves in cryptography, by both academic researchers and institutional organizations. But inertia of the firmly entrenched RSA will take time to defeat. Also, the perceived mathematical complexity, and the potential legal risks related to patents, still hinder wide acceptance of elliptic curves.

(To your list, you can add "key generation time": generating a new key pair for ECDH or ECDSA is widely faster than generating a new RSA key pair.)


Parameterizing adversaries with security parameters

The adversary should definitely always be "allowed to know" the security parameter. In other words, a security definition should allow the adversary's behavior to depend on the security parameter. This can be accomplished either by quantifying the adversary after the security parameter is chosen, or by letting the security parameter be an explicit input to the adversary.

The alternative would fly in the face of Kerckhoff's principle -- since the adversary is not allowed to "know" the security parameter, it would mean that the scheme is (apparently) deriving some important property from the secrecy of the security parameter.

Nonetheless, here are some valid reasons why this dependence on security parameter might be omitted in the notation:

Authors are lazy, the extra parameter to the adversary is cumbersome to write, and the intended audience probably knows the standard conventions about security parameters.
In an earlier section, authors have said "all algorithms are assumed to take a global security parameter as common input" or something along those lines.
The adversary already gets to see certain things from which it could infer the security parameter anyway. So it is redundant to give the security parameter explicitly. For example, the adversary sees a public key in some security game, and the length of the public key is the security parameter. Especially in things like public-key crypto, it is without loss of generality that you include the security parameter in the public key.


Why do Edwards curves protect against side-channel attacks?

Some formulas like the usual short Weierstrass addition formula for curves over fields of characteristic ${>}3$, involve terms like $$\frac{y(P) - y(Q)}{x(P) - x(Q)}$$ which don't work when $P = Q$.  So to reliably add two points, you have to write logic like:

if P == Q:
    return doubling_formula(P)
else:
    return addition_formula(P, Q)

This conditional may take a different amount of time depending on potentially secret points $P$ and $Q$.  Even if doubling_formula and addition_formula take exactly the same amount of time, the machine may take a different amount of time depending on which way the branch goes because it may predict one way and take more time if the prediction is wrong, or it may have different effects on CPU caches depending on which branch is taken.  In general, CPUs do not keep branch conditions secret.

One way to do this is to compute both doubling_formula(P) and addition_formula(P, Q) and then choose between them with arithmetic like (d & m) | (a & ~m) where d is the outcome of doubling, a is the outcome of addition, and m is all 1 bits if $P = Q$ and all 0 bits if $P \ne Q$.  But this costs more to compute because now you have to compute the addition formula and the doubling formula, even if you're going to use the result of only one of them, whenever you want to add two points.

The Edwards addition formula, in contrast, does not have any such terms, and it works for all pairs of points, even if $P = Q$.  Consequently you don't need to write conditionals and you don't need to spend the cost of computing multiple different formulas.  But it only works for some curves like edwards25519; it doesn't work for, e.g., secp256k1.

(While there are complete addition formulas for arbitrary curves, they are considerably costlier than the Edwards addition formula, so like the do-every-branch-and-select-with-arithmetic approach, they present a conflict between performance and security.)


Read the result of the hash by SHA-256 as a number

Yes, the output of SHA-256 is well distributed over the entire output of the hash function. That also means that any number generated by unknown input is well distributed, of course.

Which number is represented depends on the number system. If you want to interpret it to be in the range $\big[0, 2^{256}\big)$ then that's certainly possible - and the most likely interpretation by cryptographers (as most cryptographic algorithms use modular operations, and those are most easily defined to use zero- or positive integers).

To use SHA-256 as a positive number you simply interpret it as a statically sized, unsigned number.

Now the fact that it is statically sized doesn't matter much, as any library will likely skip leading zeros. It may however an issue if you want to revert back to bytes.

That leaves the issue of endianness of the number. You can interpret such a value as big endian (network order) number or little endian number. In case of big endian the most significant byte is on the left, while in little endian it is on the right. As the number is well distributed, each interpretation is equally valid - but obviously they will lead to different values with near-certainty for such large values. Generally cryptographers prefer big endian, especially for large number calculations as e.g. in RSA.

One way to do this for C++ is to use a cryptographic library, where such conversions are common. E.g. in Crypto++ there is the Integer constructor with a constructor using the following signature:

Integer::Integer  (   const byte *    encodedInteger,
                        size_t          byteCount,
                        Signedness      sign = UNSIGNED,
                        ByteOrder       order = BIG_ENDIAN_ORDER
                    )

Here encodedInteger would be the hash value of 32 bytes, byteCount would then be set to 32 of course. sign already defaults to unsigned as this is about cryptography and byte order has the right default as well. Beware that not every "BigNum" implementation will have such cryptographically sensible defaults - Java's BigInteger for instance does require you to explicitly indicate that the result should be interpreted as unsigned value.

In the RSA standard the operation is known as the Octet String to Integer Primitive (OS2IP). Please do note though that the formula for that method mathematically describes the usual layout of the bytes in memory. There is no need to perform any exponentiation or multiplication to implement such functionality.


Non-commutitive and nonassociative algebraic structures in cryptography

A self-distributive algebra is an algebra $(X,*)$ that satisfies the identity
$x*(y*z)=(x*y)*(x*z)$. There are several cryptosystems that use self-distributive algebras as platforms and these cryptosystems should be thought of as non-associative versions of the more well-known non-abelian group based cryptosystems (such as the Anshel-Anshel-Goldfeld and Ko-Lee key exchanges). Since the current quantum algorithms have nothing to do with self-distributivity, I would suspect that cryptosystems based on self-distributive algebras would be no less secure against quantum attacks than they are against classical attacks.

Cryptosystem 1: This paper by Kalka and Teicher presents a self-distributive algebra based key exchange which is a modifification the Anshel-Anshel-Goldfeld key exchange for groups.

Cryptosystem 2: In this paper, Patrick Dehornoy proposed an authentication protocol which (with some modification) could use any self-distributive algebra as a platform.

Cryptosystem 3: The Ko-Lee key exchange for non-abelian groups extends to a self-distributive algebra based key exchange. Define terms $t_{n}$ for $n\geq 1$ by letting
$$t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y).$$
Then $x*(y*z)=t_{n+1}(x,y)*(t_{n}(x,y)*z)$ for all $x,y,z$ and $n\geq 1$. Consider the following key exchange.

  A self-distributive structure $(X,*)$ and an element $x\in X$ are
  public.

  Alice selects some $a\in X$ and $n\geq 1$ and sends $r_{1}=t_{n+1}(a,x),r_{2}=t_{n}(a,x)$ to Bob.
  Bob selects some $b\in X$ and sends $s=x*b$ to Alice.

  Let $K=a*(x*b)$.

  Alice computes $K$ using the fact that $K=a*s$.
  Bob computes $K$ using the fact that $K=r_{1}*(r_{2}*b)$.

Now these cryptosystems just need a suitable self-distributive algebra as a platform.

Platform type 1: racks and quandles. Racks and quandles are among the most well-known self-distributive algebras. Racks and quandles arise from groups, so I would consider these cryptosystems a part of non-abelian group based cryptography instead of non-associative cryptography.

Platform type 2: Shifted conjugacy on braids. Braid based cryptography does not appear to be secure and Dehornoy's authentication scheme for shifted conjugacy has been attacked in this paper.

Platform type 3: Algebras of elementary embeddings. These are the algebras which I have been working on, and there is currently no one else studying these structures. The algebras of elementary embeddings are self-distributive structures that arise from the rank-into-rank cardinals at the top of the large cardinal hierarchy. It is too early to comment whether these algebras of elementary embeddings could be made into secure cryptosystems.

Note: The action of braid groups on quandles could be used to greatly improve the security and efficiency of braid group based cryptosystems.


Why xor the message into the state for sponge hashes?

Section 4.3 of the paper Cryptographic sponge functions analyzes the Overwrite-mode for a sponge, which does just what you propose: instead of XORing the next part of the message into the non-hidden part of the state, replace the non-hidden part of the state by it.

They show that it can be implemented on top of the Duplex mode (which outputs the non-hidden part of the state), and for this reason has equivalent security as the usual Sponge mode (which XORs the message part), with the cost of two bits of capacity or bitrate used for padding and a frame bit.

This is also intuitively clear: All the security claims of a sponge are relative to the capacity, i.e. the size of the hidden part of the state. What you do with the non-hidden part doesn't really matter, as long as your new data somehow comes into play.


Why are there no MACs inspired by block cipher modes other than CBC and CFB?

It is certainly wrong to state that "MAC can only be produced with AES in CBC and CFB mode", but there seems to be a simple reason that people were inspired by these modes when thinking up possible MAC constructions: They carry along some state that incorporates information from the message while traversing the input blocks. In both modes, encrypting a block involves taking the current state along with a message block and transforming them in some way to obtain a ciphertext block and an updated state. This is not the case with the other common block cipher modes.

ECB is completely stateless.
Counter mode (CTR) has some state (namely, the counter), but it is independent of the message and therefore useless to assert message integrity.
Output feedback mode (OFB) is also stateful, but the message is XORed into the to-be ciphertext block after the fed-back block has been tapped. Therefore, the state is independent of the message, just like for counter mode.


What you are looking for is called steganography. It is a different field from cryptography so you might want to check in some other fora also.

I don't know much about steganography but i remember this paricular algorithm. You can take you ciphertext, and an image say a greyscale bitmap. Then you can replace the least significant bits of every pixel with a bit from your ciphertext. Since ciphertext are "random" bitstrings one would no be able to recognise a ciphertext from random noise on the pixel values.

You can then reconstruct the ciphertext by reading the last bit from each pixel.


The key pair used to sign the proof is just a means of securely communicating with the service (it doesn't prove anything, it just establishes a means of proving data integrity, i.e. "I'm really the one who just sent you this proof, see, I signed it with my private key? -Oh, OK, I just verified with your public key; all good")

Now for the first key pair (since I don't know which key pair you are referring to by saying "simple key pair"):
Same thing, except here it's to prove the integrity of the passport. It was signed by a government, so all the data contained within it are certified by that government (one can't just modify his digital passport to appear older and whatnot).

The ZKP part of your question is hard to answer since it's very abstract in the quote you provided, but put simply:

You're not going to send your birthdate contained in your passport (as that would not be zero knowledge). A zero knowledge proof protocol would take (i), (ii), (iii) as input and provide a proof (to the service), without disclosing any of (i), (ii), (iii). Through such a protocol, the service would know (/be convinced of with a high probability) that you are indeed over 19 years old and that this information inside your digital passport has been certified by your government.

The difficulty here would be the ZKP protocol itself that would be able to provide such a proof.

The service won't receive your passport data, signature, or birthdate (encrypted or not with a key pair), but a proof of the statement "I am over 19 years old".

I hope I helped clarify this though I'm not sure. With a reference to the blog post I could maybe see the ZKP (if he provided it) he imagined to achieve this.


Is it fair to assume that SHA1 collisions won't occur on a set of <100k strings

The chance of a collision in such a set is approximately $ \frac{1/2 \cdot n^2}{2^{160}} $, which for n=100k evaluates to about $ 3.4 \cdot 10^{-39} $. So it is fair to say, such a collision won't occur accidentially.

AFAIK nobody has ever found a SHA-1 collision The only concrete SHA1 collision to date was Google's on February 23rd, 2017 (found here). Collisions become likely once you generate about $2^{80}$ or $10^{24}$ hashes.

If cryptoanalysis advances, an attacker might be able to create inputs that deliberately collide. Currently, however, there is no known way to do this efficiently. Of course, this only applies if your application needs to protect against deliberate collisions; many applications only require protection against accidental collisions. If you need protection against deliberate collisions, I'd prefer SHA-2 over SHA-1.


Increased security weaknesses when truncating SHA1

Given message $A$, you have to find message $B$, such that the first 64 bits (say, MSB) of their hashes collide:
$$
MSB_{64}(H(A)) = MSB_{64}(H(B))
$$

This problem is called Second Preimage Search for the function $MSB_{64}(H)$, or Partial Second Preimage Search for the hash function $H$ alone.

When $H$ is the full round SHA-1, there is no result, theoretical or practical, that would allow you to do it faster than by trying $2^{64}$ (on average) arbitrary strings for $B$. Clearly, your third restriction does not make the things easier, but still, you need to brute-force $2^{64}$ messages to solve the problem.


Is it possible to work out the hash using length extension attack but with different hashes type?

This is not possible in general, or for the specific case of SHA1 and SHA512. Length extension works because MD-hashes iterate the same function, so knowing the output you also know the intermediate state for some related longer inputs.

Now there are some cases with "different" hashes where it could be possible. That its when the hashes are related. Like SHA512 -> SHA512/500 or another such truncated hash that uses the same IV and compression function.

In that case you can use the normal length extension attack and just truncate the final output.


How does Signal Messenger's Safety Number Works?

Here is a detailed blog post about the safety numbers:
https://signal.org/blog/safety-number-updates/

They are unique per conversation and basically consist of hashes of your and your contact's public long-term key.

You should compare them if you want to be sure that there is no man-in-the-middle.


For the first part of the question regarding DES subkey generation, the reason there is a difference in the rotation amount is so that each subkey is different, and that all bits of the original key are used, and that there is a fairly equal probability that a bit will be in a subkey.

The rotations occur on the equal sized 28-bit halves of the 56-bit permuted key (after PC1), and are then sent to PC2 and reduced to 48-bits.

Because of the rotation constant, all 16 subkeys are different. If the rotation constant was 2, the subkeys would start to repeat after 14 rounds.

The combination of PC2 and the rotation constant means that each bit of the 56-bit key is used in approximately 14 of the subkeys. Bit 1 of 56 for example is used 15 times, whereas bit 2 is used 13 times. A complete list of bits (prior to PC2) used in the subkey generation are shown in this answer.


Verify hash of plaintext through ciphertext

Answering in a pragmatic way (it might help, depending on the background of the question):

Even if step 3 is possible, it does not matter, since this will not add any additional security value.

Because: Bob still has to trust Alice that she will send him K in case that he pays the money. So Bob could also simply trust Alice, that she has already send him the correct encrypted text E(M, K) in the first place.


How to compute the inverse of a polynomial under $GF(2^8)$?

The classic generic algorithm for computing modular inverses is the Extended Euclidean Algorithm. The algorithm is primarily defined for integers, but in fact it works for all rings where you can define a notion of Euclidean division (i.e. "Euclidean domains"). In particular it works with polynomials whose coefficients are in any field.

Let $K$ be a field. In the case of AES, this is $\mathbb{F}_2^8$, the finite field with 256 elements, but this does not actually matter here. $K[X]$ is then the ring of polynomials with coefficients in $K$. Given two such polynomials $A$ and $B$, you can find polynomials $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ (the largest power of $X$ for which the corresponding coefficient of $R$ is non-zero) is strictly less than the degree of $B$. This is easily computed in about the same way you would compute a division of integers; in fact it is easier because there is no carry to propagate between coefficients.

The magic part of it is that the $Q$ and $R$ polynomials are unique; i.e. for two polynomials $A$ and $B$, there is only one pair of polynomials $(Q,R)$ that matches the conditions above. Thus, the Euclidean division of polynomials is well defined, and the Extended Euclidean algorithm works.

In practice, the Extended Euclidean Algorithm is about finding the Greatest Common Divisor. In the context of polynomials, "greatest" means "of largest degree". Note that this GCD is defined only up to a multiplicative constant; it is often taken as convention that the GCD should have its largest non-zero coefficient equal to 1 (you can always arrange for that, because if polynomial $B$ divides polynomial $A$, then $tB$ also divides $A$ for all non-zero field elements $t$).

So if you have a polynomial $A$ and want to inverse it modulo $B = X^4+1$, then you run the Extended Euclidean Algorithm to obtain polynomials $U$, $V$ and $G$ such that $G$ is the GCD of $A$ and $B$, and $AU+BV = G$.

If $G$ has degree 0 (i.e. it is the constant $1$), then $A$ is invertible modulo $B$, and its inverse is $U$.

If $G$ has a non-zero degree, then this means that $A$ and $B$ can both be divided by that non-trivial polynomial, and there is no solution: $A$ is then not invertible modulo $B$.

Note that $X^4+1$ is not irreducible over $\mathbb{F}_2^8$; it is equal to $(X+1)^4$. It follows that a polynomial $P$ of degree at most 3 in $\mathbb{F}_2^8$ is invertible modulo $X^4+1$ if and only $P$ is not divisible by $X+1$, i.e. $P(1) \neq 0$. For $P = 3·X^3+X^2+X+2$ (I am calling "$3$" what the AES specification denotes 0x03), you have $P(1) = 3 + 1 + 1 + 2 = 1$ (remember, we are working in $\mathbb{F}_2^8$, so addition is XOR), so that polynomial $P$ is indeed invertible.

Another, completely different way of computing inverses is with modular exponentiation. The polynomials which are invertible modulo some given polynomial $B$ form a multiplicative group. If that group has order $e$, then the inverse of any invertible polynomial $A$ modulo $B$ is necessarily $A^{e-1} \pmod B$. In the case of $B = X^4+1$, the invertible polynomial modulo $B$ are all the polynomials $P$ such that $P(1) \neq 0$, so $e = 255·256^3 = 4278190080$ (this is easily seen in the following way: you can choose three coefficient arbitrarily, but for the fourth coefficient, you must avoid the one value that would make $P(1) = 0$). Therefore, to compute the inverse of a given polynomial $A$ modulo $X^4+1$, you "just" have to compute $A^{4278190079} \pmod {X^4+1}$, which can be done with a square-and-multiple algorithm.

That method is less efficient than the Extended Euclidean Algorithm, but possibly simpler to implement.


Practical way to generate random numbers from PRNG which are indistinguishable from true random

CAUTION: The seeding planned in the question has the potential to remove the default best-effort seeding normally provided by SecureRandom. It will actually do so with some security Providers. Some others will produce true random no matter what.

Worse, the seeding planned might make the output predictable by spying the machine's communication with random.org.

The specification of SecureRandom in Java (1.)5 and down to at least (1.)3 states (emphasis added):

  The SecureRandom implementation attempts to completely randomize the internal state of the generator itself unless the caller follows the call to a getInstance method with a call to one of the setSeed methods.

Java 8 is even clearer:

  If setSeed is not called, the first call to nextBytes will force the SecureRandom object to seed itself. This self-seeding will not occur if setSeed was previously called.

Recommendable practical ways to generate random numbers which are indistinguishable from true random assuming everything works as specified are:

Right after the SecureRandom constructor, perform a single nextBytes with some small numBytes >0 and disregard the result (even though 0 should do if a Vulcan implemented the spec), then setseed with whatever unpredictable data at hand, then use nextBytes.
Do not setseed, directly use nextBytes; but that additionally assumes that the runtime is able to supply entropy.

Method 1 is guaranteed not to lose the default best-effort seed, for in setseed:

  The given seed supplements, rather than replaces, the existing seed.

The above statement is leaving out an implicit and much needed: if any ! Notice that the additional statement:

  Thus, repeated calls are guaranteed never to reduce randomness.

only guarantees that the second and later setseed can't reduce randomness.

This quirk of the Java crypto API is a feature intended for testing: an initial setseed can make tests reproducible. That can be useful. Unfortunately it works, or not, depending on security Providers (at least, and to my knowledge only), and I know no way to tell other than trying. More generally the Java crypto API is complex and occasionally error-prone, to the point that it is hard to be sure that you will reliably get what you want to get, even though casual testing might suggest so.


Will compression help defeat single letter frequency attack against a mono alphabetic substitution cipher?

What user466720 said about ciphertexts being uncompressable is applicable to modern ciphers such as AES. It does not apply to monoalphabetic substitution ciphers, since such a cipher does not change the entropy of the data.

Per fgrieu's comment, you should assume that the attacker knows whichever compression algorithm is used.

Compression, unlike the monoalphabetic substitution cipher, does change the entropy of the data. When a monoalphabetic substitution cipher is applied to the compressed data, the encrypted data will therefore have the same entropy as the compressed data. As such, an attacker will not be able to conduct a frequency analysis on this data. That is because they do not know what the entropy is (which is a requirement of performing frequency analysis).

If you were to apply the cipher, then compressed the encrypted data, the attacker could decompress the encrypted data, and then perform frequency analysis on the decompressed data, assuming they can figure out the compression algorithm used. This is a fair assumption to make, since no aspect of the compression algorithm is secret and their specifications are freely available to all people.


Can you confirm whether this attack will work

It depends on a situation which is mind boggingly unlikely to happen, but if it is does happen, yes, it will work.

We'll have $\beta = p - 1$ iff $d$ just happens to be the value $(p-1)/2$; this happens with probability $1 / (p-2)$.

For El Gamal to be secure at all, $p$ needs to be large, say, at least 2048 bits.  This means that this has a probability circa $2^{-2048}$ of happening.  We typically don't sit around worrying that we'll be hit by a meteor in the next 10 seconds; that has a much higher probability of happening than us picking the bad $d$.