What are the chances of an RSA signature collision?

So what you are asking is if we could create $\operatorname{Sign}_S(M_1) = \operatorname{Sign}_S(M_2)$ where $S$ is the private (and secret) key. Obviously, this cannot be the case. If you could then an adversary could claim you signed $M_2$ even though you actually only signed $M_1$. That would also mean that the signature would be repudiable; a signer could simply claim to have signed a different message. Non-repudiability is arguably the most important aspect of a digital signature in the first place (authentication can also be performed using other primitives, e.g. using a static DH key, after all). To round it up: if signatures would collide for separate messages and the same key (and the same configuration parameters) then the algorithm would be fundamentally broken.

Note that many signature generation algorithms are non-deterministic. In other words, they take the input of a random number generator as input, and will therefore generate a different signature each time the signature is generated. The often used RSA-PKCS#1.5 scheme is however deterministic and RSA-PSS can be configured to be deterministic by configuring the salt size to an empty octet string / byte array. Mind you, runtimes may decide not to make the salt size of RSA-PSS configurable, in which case RSA-PSS remains non-deterministic per default.

So yes, you can use a hash to subtract or condense the signature into an identifier, as long as your signature is deterministic (and presuming you want to regenerate the identifier later on). If your hash is too large then you can simply use the leftmost bytes or use a smaller hash function. There are also multiple ways of expanding the result - although that's unlikely required for your use case. Nowadays you would probably use a XOF such as one of the SHAKE functions (part of SHA-3 specs) for expansion. An KDF that supports expansion such as HKDF-expand would also be an option.

Note that most if not all modern signatures already include hashing of the data - if just to make sure that the requested property holds. It would be a good idea for the hash functions to have about the same security strength. Of course you need to use a secure hash function (e.g. SHA-2 / SHA-3 and not MD5 or SHA-1) for the hash function.

The smaller the final identifier, the bigger the chance of collisions, of course. Note that you would need $2 \cdot s$ bits to reach a strength of $s$ bits due to the birthday problem. Don't make your identifier too small, especially if you're planning of using many identifiers. Using the full hash output should of course be preferred.


For calculating the index of coincidence for each sequence

As explained on the link you posted, the Vigenere cipher with a key on length $n$ encrypts every $n$-th symbol with the same key under the Caesar  cipher. So to calculate the IC you should take all the $n$ sub-sequences separately: $\{1, 1+n, \dots, 1+kn, \dots\}$,  $\{2, 2+n, \dots, 2+kn, \dots\}$ and so on and compute the IC for every sub-sequence.


Probability of $D_k(a*k+b) =p$ for a PRP

Let's look at some simpler relations first. I'll be sloppy with the probabilities, I'm only trying to gauge the order of magnitude.

The probability that $E_{k_1}(p) = k_1$ is $2^{-128}$ for a given $p$, but must be true for some $p$ with every AES-128 key $k_1$.

The probability that $E_{k_2}(p) = k_2$ for the same $p$ is $2^{-128}$ for a given $k_2$.
The probability that there is some $k_2 \not = k_1$ for which $E_{k_2}(p) = k_2$ is about $2^{128}-1$ times as much, i.e. quite likely.
The probability that there are three different $k_i$ for which it is true is again close to $2^{-128}$.

Now that was with a constant $p$ that we "found" with some key $k_1$. Take another key and there's another $p'$ for which a similar equality holds, and $p'$ is likely different. For that you can again look at all other keys, probably finding at most one other key that fulfills it, but finding three with probability around $2^{-128}$.

Go through all $p'$, of which there are a small factor fewer than $2^{128}$, and you are quite likely to find one for which three keys match $E_{k_i}(p) = k_i$. Not 100% likely, but maybe 10% or whatever.

Now you can make the equation more complex. If you XOR a random constant $x_1$ on the right side, you can approximate it as an independent equation. There are $2^{128}$ possible values of $x_1$ so now you are overwhelmingly likely to find one triplet of keys for which it holds. Might even find four, but probably not.

Your form is more complex so there's more freedom to choose the constants and $N$ is probably larger. However, my math was sloppy enough already that I won't guess at the value.


Negating the risk of a random 64-bit nonce

Without looking at the code I would say your construction is pretty much the same as XChaCha20:

From https://download.libsodium.org/doc/advanced/xchacha20.html

  Internally, XChaCha20 works like a block cipher used in counter mode.
  It uses the HChaCha20 hash function to derive a subkey and a subnonce
  from the original key and extended nonce, and a dedicated 64-bit block
  counter to avoid incrementing the nonce after each block.

(emphasis mine)

I'm not sure if this HChaCha20 hash function has any specific properties but using HKDF is probably just fine.

Here is the paper on XSalsa20. It should be possible to adapt the security proof.


As PulpSpy have mentioned, It is called proxy re-encryption. A company called NyCypher have implemented it but with secp251 keys https://blog.nucypher.com/proxy-re-encryption-playground-in-python-3bc66170b9bf.
Other option is charm-crypto,https://github.com/JHUISI/charm/tree/2.7-master


Is libsodium's `box` construct secure without additional manual padding of the plaintext before encryption?

The _easy and _detached APIs are faster and improve usability by not requiring padding, copying or tricky pointer arithmetic.

This refers to the way the original NaCl API worked. You had to add some zeros before the message, and remove them after decryption. But this is just how the functions had to be used. It made the primitive implementation easier, but usage trickier. It didn't add any actual padding to the messages.

  (e.g. malleability caused by determinism)

Irrelevant here. The nonce ensures that the same message encrypted twice produces different ciphertexts.

Padding should be added only if you consider that an attacker may learn something relevant from the length of the messages. If you are sending encrypted passwords, this will reveal the length of the passwords, which may not be desirable. If the only messages that can be exchanged are "yes" and "no", the attacker will not require to decrypt anything to guess the message. Here, padding would be useful.

But for most applications, it is useless.


Does this mean H is collision resistant?

No, it cannot be collision resistant.

Consider $H(x)$ over all possible values $x \in \{ 0, 1 \}^k$ for $k \ggg n$.  There are $2^k$ possible inputs, and only $2^n$ possible outputs; furthermore, the preimages for any specific output must be contiguous.

Hence, if we consider $x$ stepping from the minimal possible value $0^k$ through consecutive values to the maximal value $1^k$, then $H(x)$ must be split up into (at most) $2^{n}$ ranges, where any two inputs in the same range will generate the same output; for those $2^k$ inputs, there are at most $2^n-1$ places where adjacent inputs produce different outputs.

Hence, if we select a random $r \in \{ 0, 1 \}^{k-1}$, and consider $H( r \mathbin\Vert 0 ), H( r \mathbin\Vert 1)$, then with high probability (at least $1 - 2^{n - k - 1}$), those two hashes will be the same, and that's a collision...


Finding a base of an exponent in mod field

Solving discrete logs modulo $2^n$ is easy.

You rely on this:

If we have (for odd $e$) $$(n 2^{k+1} + 2^k + 1)^e = b \pmod{2^\lambda}$$

then either:

$$(n 2^{k+1} + 2^k + 1)^e = b \pmod{2^{\lambda+1}}$$

or

$$(n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} = b \pmod{2^{\lambda+1}}$$

That can be shown because $(n 2^{k+1} + 2^k + 1)^{2^{\lambda-k}} \equiv 1 + 2^\lambda \pmod {2^{\lambda+1}}$ (binomial theorem), and so $(n 2^{k+1} + 2^k + 1)^{e + 2^{\lambda-k}} \equiv (n 2^{k+1} + 2^k + 1)^e \cdot (1 + 2^\lambda) \equiv $ $(n 2^{k+1} + 2^k + 1)^e + 2^\lambda \pmod{ 2^{\lambda+1} }$

So, you can find your exponent by starting at the bottom, $9^1 = 9 \bmod 16$, and then extending it for increasing values of $\lambda$, until you hit $\lambda = 2048$


Block cipher birthday bound and a KDF workaround

Obviously you assume blocklength is $128$ bits. I believe the following is correct.

One might try rainbow table TMTO attacks, assuming known plaintext, and succeed with time and memory complexity somewhat better than
$$
O(2^{(2/3)k})
$$
where $k$ is the effective keylenth,
against such a scheme but it would be secure beyond the birthday bound.


10*1 padding does not mean pad with a "10", it means pad with a single bit, then as many 0 bits as is required to fill the rate, then set the last bit of the rate to 1. 10*1 padding needs at least 2 bits of padding, such as the case of 574 bits with a rate of 576, in that case you only have a single 0, which is then set to a 1 since it is the last bit.

If the message is 573 bits, you need 3 more bits, so you add your single bit, two 0s, then set the final bit to 1, which leaves you with a literal "101" padding.

You may also want to deal with the ambiguity of the digest size. Your specific parametrization specifically calls out a rate of 576, but KECCAK1024 strongly implies a 1024-bit digest size, but in this case it is your capacity. If you are using the capacity, you want it bracketed, like  KECCAK[1024]


What libraries do people use to implement and evaluate cryptography protocols?

You can use any library you like, as long as it is has been tested for the specific algorithm. In other words, if $G^x$ is implemented in a specific library you must make sure that there are unit tests and if it is used in a verified algorithm.

There are some hints you can take from the library to see if it was programmed well:

the code should point to the implemented standard;
the code should use identifiers that can be mapped to the algorithms specified in the standard it implements.

There are some more general security requirements as well of course:

the code should keep to an apparent programming style;
the code should be accompanied with the test vectors;
the code should provide unit tests for (implementation specific) edge cases (maximum integer values etc.);
the code should provide unit tests for the complementary functions;
etc. etc.

As for the unit tests of the (complementary) functions: this is not often the case, I've seen horrible failures here, including those made by myself) but also e.g. the DH implementation of Bouncy Castle and the CCM code of SJCL. In some sense you could share heartbleed under this as well.

OK, so back to the question: it depends rather a lot about the size of $G$ to find out which $G^x$ is most efficient. The choice of library would probably depend on that. Runtimes may already include these kind of algorithms as well, but they may not always be the most efficient choice for certain parameters.

I'd recommend reference implementations if not for the fact that they are often horribly programmed. Mathematicians and cryptographers are just as likely to succeed in software development as anybody else. Quite often they do not keep to the requirements above, often for the sake of brevity.

Finally, you probably should chose a library that fits your programming environment of choice. The library should be quite extensive and the functions well defined; single purpose libraries should not be used unless they have been made for your specific problem domain.


AES or One-time-pad for encrypting a single 128bit block?

So, AES is more secure than one-time-pad in this case.

No, the one-time pad is perfectly secure, so it cannot be less secure than AES.  What's tripping you up is you're not understanding a subtle detail of what perfect secrecy means. People often misunderstand it to mean "the attacker cannot learn what the plaintext is," but in reality it means this:

No matter how hard they analyze the ciphertext, it cannot help the attacker learn anything more about the plaintext other than what they can figure out through other means.

Take your argument here:

In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use brute force for the remaining key bits.

Here the initial portion of plaintext is something that the attacker learned not by cryptanalysis, but through some other means.  So the question is whether analyzing the ciphertext can gain them additional knowledge about the plaintext.  And the perfect secrecy of one-time pads tells us that it cannot, because given just the ciphertext and initial portion of plaintext, every possible remaining portion of plaintext is equally likely.
Another way to put this is that given the initial portion of plaintext, analyzing the OTP ciphertext isn't any more effective than just looking at that initial portion of plaintext and guessing how it might continue. Like, if the initial portion says ATTACK AT D, you might guess the full plaintext is likelier to be ATTACK AT DAWN than ATTACK AT DUSK just because dawn attacks are more common than dusk attacks. But no matter how hard you analyze the ciphertext, it won't help to settle this any further.

In course content, answer is given as :

Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

I think this answer is wrong, depending how we interpret the question though.  A brute-force attack might learn something about the plaintext in the AES scenario; but "might" is a key word there, there's no guarantee.
The idea would be to do this. Given ciphertext $C$ and partial plaintext $P'$ of length $l$ (in bits), go over every possible AES key $K_i$, and:

Compute $P_i = \mathrm{AES}^{-1}_K(C)$ (the AES decryption of $C$ with key $K_i$);
If the first $l$ bits of $P_i$ matches $P'$, then add $P_i$ to the set $S$ of candidate plaintexts; otherwise, discard $P_i$.

Now, for the security of AES in this scenario to be the same as one-time-pad, the resulting set $S$ must be of size $2^{128-l}$—the set of candidate decryptions must be the same as the set of all possible 128-bit strings that start with $P'$.
But all it takes for this to fail is that there exist a single collision—a pair of keys $K_1$ and $K_2$ such that $\mathrm{AES}^{-1}_{K_1}(C) = \mathrm{AES}^{-1}_{K_2}(C)$ (i.e., that $C$ decrypts to the same plaintext for both keys). And such collisions are indeed possible. And if there are such collisions, then there will also be "missing" plaintexts in $S$, which the attacker therefore learns are impossible given $C$ and $P'$.
Ultimately the course's question is vague, because it has these problems:

"Can the attacker decrypt the ciphertext" is a simplistic goal. As I mention above, the sort of goal that cryptography normally contemplates is "can the attacker learn something about the plaintext by analyzing the ciphertext," which may fall short of a full decryption.
In the AES scenario the question poses, it's possible but not certain that the attacker could rule out some candidate plaintexts. But the question isn't formulated in a way where we know for sure whether to count that as "the attacker can" vs. "the attacker can't."

There's two key certainties here, though:

The one-time pad is perfectly secure but AES is not.
Network security textbooks often don't teach cryptography exactly right


Elliptic curve cryptography attack vector

If you use elliptic curve cryptography properly, with a suitable choice of parameters, there is no known weak point.  (More precisely: The cryptography is unlikely to be the weakest link in your system.)

The trick is to use the cryptography properly.  That's why people generally recommend that you use some existing well-vetted solution, like TLS 1.2 or similar, rather than implementing your own.

If you want to know what is the primary, most likely risk that will cause the security of your communications to be compromised, it is probably things like (1) insecure endpoints, (2) human error/mistakes, (3) compromise of one of the people/entities who are party to the communication, (4) traffic analysis, etc.  In other words: system-level issues, not the elliptic curve crypto algorithms.  One could write an entire book on what could be done about that, and people have; see the information security literature.


Decrypting an encrypted aes 256 cbc text with random IV, decrypts the string

Here is the picture for CBC decryption ($\oplus$ is the XOR operation of each bit/byte at the same position of the input blocks):

As you can see only the first block is altered by the IV.

During encryption every block is changed because the ciphertext will propagate the uniqueness of the IV over all subsequent blocks. However, during decryption only the first block is XOR'ed with the IV to get back the first block of plaintext.

If that block is random then the result will also be random. The rest of the blocks is unaffected.

If you change just a single bit of the original IV, then only that particular bit in the plaintext block will be affected.


How succeptible to accidental collision is the construct sha256(uuid4 + now) in Python?

You can skip the test, unless you suspect that uuid4()) + str(timezone.now() (and the random value you may have added) is possibly not unique. The chances that SHA-256 itself accidentally introduces a collision is negligibly small.

There are no known attacks on SHA-256 that break the algorithm, other than length extension attacks. Those however don't seem to be an issue with your protocol.

So you mainly have to worry about an attacker messing with your input. The date won't add much entropy, so as a long as the underlying random generator(s) are secure, your scheme is likely secure as well.

Although it doesn't seem to  be an issue with your current scheme, you should make sure that the input to the hash function doesn't rely on the size of the input data. For instance, A | BC hashes to the save value as AB | C. In other words, you need a canonical method of encoding your data structure. Best to document this, otherwise you may mess up your scheme at a later date.


Is this the right way to implement one time pad?

No, this is not a proper way to perform the One Time Pad, even with just 5 letters (assuming the pad and message are bound to be letters that is in range [65..90]).

Problem is, when we see that the first encrypted character is 139, and since we know that the pad is in range [65..90], we know that the first plaintext character is in range [65..74], not in range [75..90]. That's a huge information leak. When the ciphertext character is 130 (resp. 180), we exactly know the plaintext letter: it is 65/A (resp. 90/Z).

The solution to this problem is to compute ciphertext as $c=((p+m)\bmod 26)+65$, and decipher as $m=((c-p)\bmod 26)+65$ (implementable as (c-p+26)%26 + 65 in C). As a bonus, the ciphertext consists of letters.

  My idea is to use the same Ascii #2 to again if the message is longer

That's a tried, tested, and bad idea. This is no longer a One Time Pad and it is no longer unconditionally secure. See for example How to attack the Two Time Pad?.


AES S-Box implementation: from a byte-by-byte to 2-bytes-by-2bytes?

First of all without any context going from a byte-by-byte substitution to a 2-bytes-by-2-bytes does not means anything as it is S-box implementation dependent.

I. Using Lookup tables (Boooooo!)

Example:
one could implement bit-by-bit $\neg$ as a lookup table:

neg[0] = 1
neg[1] = 0

And then go to a 2-bit-by-2-bit $\neg$ as such:

neg[00] = 11
neg[01] = 10
neg[10] = 01
neg[11] = 00

This will effectively compute the requested result but as you can already see the space required is stupidly huge as it increases by with the square of the width of the S-box...

In the other hand one could also implement the $\neg$ using the assembly instruction, which allows to process at least 8 bitwise $\neg$ at the same time !

In other word: FORGET ABOUT TABLE LOOKUPS.

II. Using Computations (Meh)

For AES it is the same, you can either use a Sbox[x] look up or you can compute that value using the formula provided in the specifications (requiring an inverse over $\operatorname{GF}(2)[X]$).

Also the advantage of such implementation is that you are less likely to be sensible to cache-timing attacks. You can then try to replicate these computations on multiple bytes at the same time.

III. Using Bit-slicing (Yeah!)

In order to go further than a 2-bytes-by-2-bytes substitution, you can have look at the AES hardware implementation. You will see gates and paths. You can replicate this circuit using normal instruction in a software.

in other word for a $\oplus$ gate:

     +-----+
x ---|     |
     | XOR |--- z
y ---|     |
     +-----+

can be seen as : $\texttt{0000000x} \oplus \texttt{0000000y} \to \texttt{0000000z}$

Wait this is actually worse! you are doing one bit per instruction, this is going to be super slow!

Well you probably noticed that you have 7 bits left empty. And because you want to process multiple S-box (bytes) in parallel, all the hardware operations on each bytes will be the same. So we can take a bit of each of the 8 bytes and compute the gate on them:

For 8 bytes:
$a = \texttt{a}_0\texttt{a}_1\texttt{a}_2\texttt{a}_3\texttt{a}_4\texttt{a}_5\texttt{a}_6\texttt{a}_7\\
b =\texttt{b}_0\texttt{b}_1\texttt{b}_2\texttt{b}_3\texttt{b}_4\texttt{b}_5\texttt{b}_6\texttt{b}_7\\
c = \texttt{c}_0\texttt{c}_1\texttt{c}_2\texttt{c}_3\texttt{c}_4\texttt{c}_5\texttt{c}_6\texttt{c}_7\\
d = \texttt{d}_0\texttt{d}_1\texttt{d}_2\texttt{d}_3\texttt{d}_4\texttt{d}_5\texttt{d}_6\texttt{d}_7\\
e = \texttt{e}_0\texttt{e}_1\texttt{e}_2\texttt{e}_3\texttt{e}_4\texttt{e}_5\texttt{e}_6\texttt{e}_7\\
f = \texttt{f}_0\texttt{f}_1\texttt{f}_2\texttt{f}_3\texttt{f}_4\texttt{f}_5\texttt{f}_6\texttt{f}_7\\
g = \texttt{g}_0\texttt{g}_1\texttt{g}_2\texttt{g}_3\texttt{g}_4\texttt{g}_5\texttt{g}_6\texttt{g}_7\\
h = \texttt{h}_0\texttt{h}_1\texttt{h}_2\texttt{h}_3\texttt{h}_4\texttt{h}_5\texttt{h}_6\texttt{h}_7$

We can construct the following 8 bytes:

$bit_0 = \texttt{a}_0\texttt{b}_0\texttt{c}_0\texttt{d}_0\texttt{e}_0\texttt{f}_0\texttt{g}_0\texttt{h}_0\\
bit_1 = \texttt{a}_1\texttt{b}_1\texttt{c}_1\texttt{d}_1\texttt{e}_1\texttt{f}_1\texttt{g}_1\texttt{h}_1\\
bit_2 = \texttt{a}_2\texttt{b}_2\texttt{c}_2\texttt{d}_2\texttt{e}_2\texttt{f}_2\texttt{g}_2\texttt{h}_2\\
bit_3 = \texttt{a}_3\texttt{b}_3\texttt{c}_3\texttt{d}_3\texttt{e}_3\texttt{f}_3\texttt{g}_3\texttt{h}_3\\
bit_4 = \texttt{a}_4\texttt{b}_4\texttt{c}_4\texttt{d}_4\texttt{e}_4\texttt{f}_4\texttt{g}_4\texttt{h}_4\\
bit_5 = \texttt{a}_5\texttt{b}_5\texttt{c}_5\texttt{d}_5\texttt{e}_5\texttt{f}_5\texttt{g}_5\texttt{h}_5\\
bit_6 = \texttt{a}_6\texttt{b}_6\texttt{c}_6\texttt{d}_6\texttt{e}_6\texttt{f}_6\texttt{g}_6\texttt{h}_6\\
bit_7 = \texttt{a}_7\texttt{b}_7\texttt{c}_7\texttt{d}_7\texttt{e}_7\texttt{f}_7\texttt{g}_7\texttt{h}_7\\$

Notice that each byte $bit_\alpha$ contains only a the $\alpha$ bit of $a,b,c,d,e,f,g,h$.

Then we can replicate our gates operations as seen above on these $bit_\alpha$. Once the computations are done, all we need to do is rearrange back the bits in their respective bytes.

Remark: By doing so and extending this technique one can compute 8, 32, 64 or 128 AES S-box at the same time!

This technique is called bit-slicing.

Those are the 3 mains way to implement AES (a bit more to read here).

Now for your second question:

  What are the challenges/trade-offs involved?

Those are: Memory/Rom Space, Time of execution, complexity of implementation (meaning that it is also easy to screw up...)


Need to generate same ciphertext everytime

If you use a small value such as xx841jf== to retrieve a video then a hacker can simply brute force the URL by iterating over all the values. Similarly, if you use a hash over the number (5001) then the attacker can simply go over all numbers, perform the hash and perform the same attack.

There are a few good options for doing this:

Use a block cipher to encrypt the number value. In that case you need to pad the encoded number to a full block (using bit padding or PKCS#7 padding, for instance) and then the full result. This can be reversed to the number by the server.
Similarly you can use a hash over the number and a secret value (a pepper) to calculate a unique number, and then take the leftmost bits in case you want to shorten the URL (you'd still want at least 64 bits otherwise you may mistakenly reuse hash output values).
Often unique, large, random ID (a UID) is used to link to the number.

Notes:

For the first option you could use a 64 bit block cipher (e.g. Blowfish) or a 128 bit cipher such as AES. AES is more secure, but the URL will be much larger.
If direct encryption with the block cipher is not available then you could choose AES in ECB mode using PKCS#7 padding which is commonly available.
Of course you'd need to keep a table for the last two options, otherwise you cannot reverse the URL to the number and thus filename.
Instead of using standard base 64 encoding you could have a look at base-64-url encoding, which is URL-safe and thus doesn't require URL escaping.


What would be the best plain text Cryptography method without the use of a computer?

For confidentiality purposes?

one time pad (when possible)
rc4 (because you can by hand)


The idea of a hash function is the idea of a random Oracle. For any given input, this Oracle should return a truly uniformly random output. This is ideal of how hash functions work, so any hash function that isn't uniformly random is not behaving the same way as a random Oracle. So yes, hash functions should have uniformly distributed values.

I don't believe it's necessarily an explicit requirement to be uniform, but not being uniform would certainly weaken the strength of the hash. For example, if the hash was a 'normal' distribution, certain outputs would be far more common than other. We could get collisions far easier then.

I'm unfamiliar of any cryptographic hashes attempting to reach a non-uniform distribution as I imagine they would be more vulnerable to collisions and preimage attacks. If you were so inclined, you could hash the values with a known uniform distribution use the output in a non-uniform distribution function.


Do all stream ciphers (and AES-128-CTR in particular) produce equal output size as the input size?

First I will start with AES-CTR. This is a mode which turns a block cipher into a stream cipher. Since AES has a 128-bit block size, the output of the primitive is in blocks of 16 bytes. If you have a 3 byte message, 3 bytes is kept from that block to encrypt the plaintext via XOR. A broken implementation may not truncate. CTR requires a Nonce, which is generally included with the ciphertext and is usually 96-bits (12 bytes) in length, making that final message length 15 bytes. Salsa and ChaCha also require a Nonce.

Other variants of CTR mode include the authenticated GCM, which would then add an authentication tag to the ciphertext, at an implementation defined length.

Nonces and authentication tags are generally a multiple of 8 bits, so if you are encrypting a byte string, you should end up with one. Other data required to decrypt the message may be concatenated to the ciphertext, such as KDF iteration counts and salts, cipher or KDF identifiers, and message sequence identifiers. If an authenticated mode is used, and these are processed as additionally authenticated data, they are required to decrypt as per specification, even though without them you may still be able to recover the plaintext. Additionally authenticated data may included something that is not part of the ciphertext, such as the email or IP address of the sender.

Some stream ciphers do not explicitly require a Nonce, but they may be processed as part of the key, and still need to be included with the ciphertext.

Various implementations may obfuscate or operate on the plaintext prior to encryption. Plaintext compression can substantially change the ciphertext size, or may have no effect at all, depending on the content. Obfuscation may pad the entire message to 140 bytes, so it can then be plaintext encoded to fill an entire SMS message, hiding the true message size.


How can two (or more) parties share and agree upon a common random seed?

This is pretty much the schoolbook implementation of a shared random number generation (generate, commit, publish). So yeah, it's secure. But this only works for large random numbers, here's a small adaption that allows for arbitrary size integers:

If you need an $n$-bit random number everyone should generate $n$-bit random numbers - this is independent of the security level of the exchange itself. Then everyone also generates a second random number $m$, which is large (say, 256-bit)  to prevent bruteforcing, and publish $H(n || m)$. Then after everyone has commited everyone publishes their $m$ and $n$, but only use $n$ for the XOR-sum.

I'd suggest you to use a 256-bit hash for the commitments.

Beware of all kinds of nastyness with MITM and replay attacks, make sure you do all of this over authenticated channels.


How to use salt when there is only one user

In a scenario such as yours, where there is only one password/passphrase, but it is used as key material for the encryption of multiple CBC encrypted files, you will (as you noted yourself) obviously not make it any harder for an attacker to compute your password, should you use a salt.

However, using a salt would mean that the encryption of each file is independently keyed, which might increase resistance against collisions in the CBC chaining state, should you use the same password for encrypting a very large number of very large files. Since you are using AES-CBC and AES has a 128 bit block size, you would have to encrypt billions of GB sized files to get close to a 0.5 probability there would be just one such collision (in two 128 bit blocks somewhere), but depending on your security requirements, even such a small risk might be unacceptable. An alternative to using salts, would in such case be to use a cipher with a 256 bit block size instead of AES.

A third alternative would be to use random keys for each file, and only encrypt that file specific key using the key you derived from your password. If you put those encrypted keys together in a separate index file, you will get two additional benefits:

Changing the passphrase will become much cheaper, in particular if you have a large number of files or very large files. Changing the passphrase might, or might not, be something that improves your security. Obviously, if an adversary at some point in time gets hold of all of your files and is able to compute the passphrase you were using at that point in time, you gain nothing by later changing the passphrase. The file specific keys (for the files that existed at that point in time) will already be compromised.
However, using random file specific keys, will make it possible for you to put together index files for other users, containing only the keys of the files those users are supposed to get access to.


Advantages of using intermediate hash over full hash in digital signature application

There are two points I can imagine where partial hashes in a protocol can be useful.
Massively parallel computing from the same start
Using an intermediate state as the base for the PoW seems to be standard practice with Bitcoin ASICs these days and give a few dozen per cent of a speed-up. Technically you can pre-compute what you want in the next block and then send this to the ASICs for them to do the final compression function call and looking for the right property.
Regulatory Restrictions / Trusted-Signed Data Displayment
There may be regulatory restrictions along the lines of "the trusted computing device must have seen the actual transaction data", where the signature is over the sender, the recipient and the amount. Now the standard requires you to display the recipient and the amount on a card- / card-reader-controlled trusted display, however you could maybe save a bit of computation time by pre-computing the hash for the parts that do not need extra evaluation. Here the security gain would be in the fact that the card actually knows what it signed and not just some random blob (which could also have been a malicious transaction!).


How to caculate the summation of successive modular inverses?

The sum you are inquiring about is pretty much the right side of the Fermat quotient identity discovered by Eisenstein (proof here):
$$
-2q_p(2) = \sum_{i=1}^{(p-1)/2} 1/i \pmod{p}\,,
$$
where $q_p(a) = \frac{a^{p-1} - 1}{p}$.
Thus the sum can be computed as $-2 \frac{2^{p-1} - 1}{p} \bmod p$. Because computing $2^{p-1}$ is not feasible for very large $p$, and because one only requires the result divided by $p$ and then reduced again by $p$, computing $\frac{2^{p-1} - 1}{p}$ can be performed as $\frac{(2^{p-1} \bmod p^2) - 1}{p}$ without any precision loss. And to absorb that factor of $2$, one can compute instead $-\frac{(2^{p} \bmod p^2) - 1}{p} \bmod p$, which is exactly the formula you found.


Hash multiset to point on elliptic curve where $A = 0$

The short answer: MapToGroup can be used securely in this context. It reaches at least half the points on the curve (and much more if another bit from the hash input is used to determine the parity of y). Moreover, this encoding is "well-distributed" enough to act as an ideal hashing function, assuming the input is from a random oracle. Maitin-Shepard writes:

  I believe the try-and-increment encoding is fine from a security perspective, you just lose a few extra bits of security due to the larger bound on the size of the preimage of the encoding function.

The encoding in the ECMH paper caps the preimage size of points to three, and though I don't know of a bound for MapToGroup (which involves finding the longest sequence of non-residues in the base field), it doesn't seem to be a practical security concern.

Moreover, since about half the elements in the field mentioned earlier will be quadratic residues (see Counting Squares in $\mathbb{Z}_n$ by Stangl), an implementation of MapToGroup can expect about two trials on average to find a point. The average preimage size of points is less than two.

However, Aranha pointed out that an article Indifferentiable Hashing to
Barreto–Naehrig Curves exists which describes a deterministic encoding precisely to the curve being described in the question, and which is "secure" in this context.

The downside is that although the running time may be fixed, the implementation requires more computation on average than MapToGroup when using a BN curve. Moreover, there could be a side-channel leak from computing quadratic characteristics, which can vary in running time according to the input. This may be mitigated by "blinding" the computation of characteristics using inputs from a source of randomness, but is definitely an important implementation detail if the ECMH is being used on any private information.

Probably a good bet would be to go with the setup in the paper if there is support for binary curves, and otherwise consider whether any private information is being hashed.


Why the basis is reduced in nearest plane algorithm in solving CVP

Short answer: If the basis is not reduced, then there are no guarantees on the distance between the target and the output, compared to the distance between the target and an actual closest vector. By LLL-reducing the basis you can bound this distance, and therefore Babai's nearest plane algorithm solves CVP to a certain approximation.

Take a look at the second step of Babai's nearest plane algorithm, where $t$ refers to the target vector.

$ b \leftarrow t$
for $i = n$ to 1 do
$\quad b \leftarrow b - c_i b_i$ where $c_i = \lceil \langle b, \tilde b_i \rangle / \langle \tilde b_i, \tilde b_i \rangle \rfloor$
end
output $t-b$

Where the tilde denotes the Gram-Schmidt orthogonalization of the basis. Essentially, it looks for an integer combination of the basis vectors that is close to the target vector.

Now, if $t \in$ span$(B)$, you can see that you can bound the distance between the output and $t$ by the sum of $\langle \tilde b_i, \tilde b_i \rangle$. LLL gives us a bound on these values. For an arbitrary basis, these norms could be very large, meaning the second step could be very, very off.

In the case that $t \notin$ span$(B)$, you can use a similar argument on the projection of $t$ onto span$(B)$.

For the exact details of how the LLL properties of the basis are used to prove the correctness of the algorithm, see this lecture.


Why can't you hijack someone's public key

Short answer: Because the public key is derived from the private key.

Recall that when we are working with elliptic curves, we rely on the elliptic curve discrete logarithm problem (ECDLP). That is that we assume that if we have:

$$
Q = [k]P
$$

given the points $P, Q$ on our elliptic curve, it is hard to compute the scalar $k$.

Bitcoin uses ECDSA over the Secpk1 curve. In ECDSA, we have the public generator point $G$.
Alice's private key $d_a$ is randomly selected, as a large random number. With this $d_a$, her public key $Q_a$ is computed as follows:

$$
Q_a = [d_a]G
$$

This closely mirrors the equation above, about the discrete logarithm. Now your question is whether Fred can just use Alice's key $Q_a$, and generate his own private key $d_f$. He will only be able to choose a private key for which holds that $Q_a = [d_f]G$, but for this he would have to solve the ECDLP. In the case of for the Secpk1, this is practically infeasible (unless the scheme is broken).


Safely store data before moving to air-gapped machine

However, as far as I can see, the nonce for each message is transferred along with the message itself.

Yes, this is typically what happens nowadays when encrypting something using symmetric encryption.

Notice this is not necessarily the case if you're using asymmetric cryptography, since then the randomness used (which can be considered to be a "nonce") is usually encrypted along the message.

Probably the easiest way: asymmetric crypto

If you are only transferring data from one machine A to the other machine B and do not necessarily need to decrypt the data again on the first machine A, I would strongly recommend you to check out public-key encryption:

You could have a strong private key on your machine B and let machine A know the public key
Machine A could then encrypt everything you need to transmit to machine B using the public key of machine B, without leaking the secret key or anything that might allow someone to decrypt your data on machine A.
Machine B could then use its secret key to decrypt the data.

This is especially true if machine A is not air-gaped, while machine B is: you could consider machine A to be already compromised and as such all the keys, IV or passwords you might have on machine A might leak, whereas using public-key encryption, your data could not be decrypted by only looking at the secrets that went through machine A (even if the said data could be arguably already leaked while unencrypted).

(This can even work if you want machine A to be able to decrypt the data again, by encrypting the data for both the public key of machine A and B.)

About the air-gap

Notice that the air-gap in the end does not necessarily change things, as it boils down to two different scenarii:

Machine A is compromised and all the secret key, IV, nonces, and (most dramatically) messages that go through machine A can then be considered compromised
Machine A is not compromised and then we are fine

But maybe the air-gaped machine is compromised as well by a physical attacker, who knows? So there are more scenarii...
And in the end we have the same kind of scenarii than whenever we have two machines and we want to transmit data between them.

There is nothing in crypto that can help you protect your data from a compromised machine if the plaintext is on the compromised machine...

Yet, it is not because of this dichotomy (either compromised or not) that you don't need encryption.
Indeed, encrypting your data is still useful to protect the data when:

it's at rest, so that even if somebody access your machines and copy your data, they won't be able to read the data.
it's in transit, so that even if somebody intercepts your data, it will be encrypted and undecipherable for the attacker.

Even more so since it might be possible to recover erased data from a USB stick, or whatever transportation method you are using for your data...

And if the attach is not permanent, but occurs for example only when you're away ("evil maid attack"), then having encrypted data makes also sense.

Now, if you really want to do what you're discussing

  I would rather some method where the nonce could be generated by an
  algorithm that both A and B knew, with a seed that was secret shared
  between them. Is this possible?

Now, if you really want symmetric encryption, this is still possible and readily supported by Openssl, actually! (But not by other common tools such as GnuPG.)
If we take a look at the documentation of Openssl's enc feature, we can see the following:

  -K key

  The actual key to use: this must be represented as a string comprised only of hex digits. If only the key is specified, the IV
  must additionally specified using the -iv option. When both a key and
  a password are specified, the key given with the -K option will be
  used and the IV generated from the password will be taken. It does not
  make much sense to specify both key and password.

  -iv IV

  The actual IV to use: this must be represented as a string comprised only of hex digits. When only the key is specified using the
  -K option, the IV must explicitly be defined. When a password is being specified using one of the other options, the IV is generated from
  this password.

  -pass arg

  The password source. For more information about the format of arg see "Pass Phrase Options" in openssl(1).

So you could typically have a key specified using the -K argument, and derive the IV from a shared "password" file using the -pass file:pathname argument.
Notice you can choose how to derive the password, I would recommend you going with -pbkdf2 and setting a certain number of iterations:

  -iter count

  Use a given number of iterations on the password in deriving the encryption key. High values increase the time required to brute-force
  the resulting file. This option enables the use of PBKDF2 algorithm to
  derive the key.

BUT!
There are a couple issue with this method:

this will make it "easy" to reuse an IV, since if you are using the same password twice with the same number of iterations you should get the same IV, right? Well, not exactly, because Openssl got you covered. The password derivation algorithm is relying on a "salt" that gets passed on the first line of the encrypted file, just like you would usually pass the IV. I guess you could complain this is basically the same as passing the IV, but it is not, since the salt is used with a "secret" password to derive the IV.
this makes it easy to use too short keys!! This is really a problem, because if you are using a key that is not of the right size, Openssl will pad the key with zeros to achieve the right length!
using Openssl manually on the command line is a bit painful.
it is easy to use a "bad" parameters.
and finally, and most annoyingly: this does not allow the use of authentication encryption! This is justified in the documentation as follow:

  The AEAD modes currently in common use also suffer from catastrophic failure of confidentiality and/or integrity upon reuse of key/iv/nonce, and since openssl enc places the entire burden of key/iv/nonce management upon the user, the risk of exposing AEAD modes is too great to allow.

And this is true: key, iv and nonce management are considered difficult, and we do not recommend you to do it yourself! You can if you really want to, but it is typically not something we will tell you is "the most secure method" to do any kind of cryptography.

Notice that my last point is a problem: the lack of authentication means somebody could change your encrypted data without being detected, but you could solve it by performing a MAC after encryption, in the "Encrypt-then-MAC" style. This is possible using openssl mac or openssl dgst depending on your version.  Or you might solve it by using instead LibreSSL openssl that's including AHEAD mode in its enc command... You just need to pick an authenticated cipher.

TL;DR: don't do it.

However as you can see: the more we are digging that hole, the more we need to dig to try and have something "secure"... As such, this is typically not something you want to do "manually".

We usually recommend using symmetric or asymmetric encryption (using typically GnuPG), and not caring about managing the IV, and the "gory details" such as the need for authentication, etc. (Notice GPG --sign will use public-key signatures, so you would need to generate a key and share the public key with the other machine even if using the --symmetric mode.)

Also, if you are now considering "rolling your own" crypto, to solve your problems, you might as well try and take a look at what other have already done when facing a bit the same kind of problem as you do, there are many tools out there.
One of the "simplest" tool is probably "Enchive" which is using an interesting shared key generation algorithm based on Diffie-Hellman, but is still quite minimalist.

I also recommend you following the development of "Age" that has been recently designed and created by very good cryptographers, and should allow you to have high security, with good usability to do you want to do, without having to care too much about IVs, etc.

Notice how really nobody, even when "rolling their own" is letting users manage their nonces/IV, this is done for reasons... And I don't recommend you doing it neither.


Complexity of Boudot's zero-knowledge range proof scheme

Boudot's protocol is not based on the four-square decomposition - in fact, he was the first to come up with this idea of using a decomposition in four squares, but this was only mentioned orally in the talk he gave on this paper (as I was told by people who saw it - I do not think there is any written record). The first written record on this four squares idea is Lipmaa's Asiacrypt'03 paper (where you'll find additional discussion on the cost of finding these four squares). Boudot's original protocol has other efficiency shortcoming, though, but they are related to the communication required for the protocol, not to the cost of finding the decomposition.


What issues are there while using Linux's /dev/urandom for generating cryptographic keys?

Using /dev/urandom to generate cryptographic keys or secrets can be an issue when the state of the OS is not unique. This is the typically case when a VM was just booted from a template: the state of the CSPRNG could be shared among multiple VMs. In cases similar to this one, it is important to use /dev/random or getrandom() instead of /dev/urandom, so that the output of the CSPRNG blocks until it has collected enough entropy.
Of course, VM clones need to be rebooted or booted up from a shutdown state in order for the entropy count to be reset to zero.
The output of /dev/urandom and /dev/random comes from ChaCha20. To consider it insecure to create cryptographic keys once the inner state of ChaCha20 is initialized with enough entropy, one has to either:

know the inner state of ChaCha20,
or break the ChaCha20 cipher, which is today considered one of the most secure ones.

The remaining issue is how to count entropy. The Linux kernel is extremely conservative on this point, and the inner state of the CSPRNG most likely have far more entropy than counted (around two orders of magnitude more). However, to count it exactly is mathematically impossible.
Disclaimer: This answer is valid for the Linux kernel from version 4.8 to  version 5.9, which is the latest version at the time of writing of this answer. The Linux CSPRNG was heavily refactored in versions 4.8 (introduction of the ChaCha20 cipher) and in version 5.6 (simplification of the architecture), with minor changes introduced in version 4.17 and along the way.


You can print the data with (change PEM to DER if required):

openssl rsa -in Alice.key -text -inform PEM -noout

The following data is stored:

Modulus ($n = pq$)
Public exponent ($e$)
Private exponent ($d = e^{-1} \pmod{\phi{(n)}}$)
First prime ($p$)
Second prime ($q$)
First exponent, used for Chinese remainder theorem ($d_P = d \pmod{p - 1}$)
Second exponent, used for CRT ($d_Q = d \pmod{q - 1}$)
Coefficient, used for CRT ($q_{\mathrm{inv}} = q^{-1} \pmod{p}$)


Is multiplicative blinding less secure than additive?

In a finite field $\mathbb{F}_q$, both maskings are perfectly secure, provided that $x \neq 0$ for the multiplicative masking.

This is easy to see.  The finite field $\mathbb{F}_q$ defines two groups: the additive group $\mathbb{F}_p^+$ (i.e., $\mathbb{F}_q$ equipped with addition) and the multiplicative group $\mathbb{F}_q^*$ (i.e., $\mathbb{F}_q \setminus \{0\}$ equipped with multiplication).

Proposition  Let $\mathbb{G}$ be a group and let $\star$ denote the group law in $\mathbb{G}$.  Given $x \in \mathbb{G}$, if $r$ is a uniformly random element in $\mathbb{G}$ then so is $y:=x \star r$.

Let $x \in \mathbb{F}_q$.  We have:

If $r$ is drawn uniformly at random in $\mathbb{F}_q^+$ then $x+r$ (where $+$ denotes the addition in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^+$;
If $r$ is drawn uniformly at random in $\mathbb{F}_q^*$ then $x*r$ (where $*$ denotes the multiplication in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^*$, provided that $x \neq 0$ (that is, $x \in \mathbb{F}_q^*$).


Finding $f^{-1}$ in the YASHE keygen algorithm

To invert a polynomial in the quotient ring $F_q[X]/(\phi(X))$ there are two cases:

-> Either $\phi$ is irreducible modulo $q$, in which case every polynomial is inversible

-> Either $\phi$ is not irreducible, and one reasons with the Chinese remainder theorem.

In the first case, to find the inverse, just use Extended Euclides to find two polynomials $U,V$ such that

$$Uf+V\phi=1$$

(I'll let you deduce why $gcd(\phi,f)=1$) and therefore $Uf=1 \in R$.

For the YASHE parameters, $\phi$ is not irreducible, and therefore a quick answer to your question is

$\mbox{ if } gcd(f,\phi)\neq 1$ then $\phi$ is not invertible,
if $gcd(f,\phi)= 1$ use Euclides as before.


Question #1:

Is there any institution or government in the present implementing for example NTRU, SIKE or multivariate crypto schemes on their communication establishment to prevent past private information recovery?

Answer:

Currently the Open Quantum Safe (OQS) project has been launched to support the development and prototyping of post-quantum cryptography or quantum-resistant cryptography.

They have implemented liboqs, an open source C library for quantum-resistant cryptographic algorithms based on the selected NIST Round 2 candidates (such as NTRU, SIKE, and MQDSS (which is multivariate crypto scheme) at GitHub repository.

Question #2:

What would be a good estimation on time (i.e years) to move on to these post-quantum cryptographic schemes? I mean, we cannot wait until these attacks are possible on a theoretical capable quantum-computer.

Answer:

(1) The Open Quantum Safe (OQS) project co-leader, Michele Mosca published an article Cybersecurity in an Era with Quantum Computers: Will We Be Ready? in IEEE Security & Privacy (Volume 16, Issue 5, September/October 2018) to "estimate a 1/7 chance of breaking RSA-2048 by 2026 and a 1/2 chance by 2031."

(2) The Closing Remarks of Second PQC Standardization Conference held by NIST in August 2019, NIST PQC Standards - Next Steps states that

“NIST should not be aiming to conclude the process and have standards written by 2022. This is simply too fast to get proper answers.... Much more research is needed.”

(3) NIST will give a presentation at the eighth annual International Cryptographic Module Conference (ICMC20) on April 29, 2020 to report an update on the NIST Post-Quantum Cryptography Standardization process. .

Towards PQC Standardization—An Update

"As we proceed to the third-round selection, this presentation shares what has been learned in evaluating the first and second round candidates. It addresses some critical issues and discusses transition and migration strategies."


What is "Blinding" used for in cryptography?

As @CodesInChaos explains:

It might refer to blind signatures.

It also might refer to a method to harden (typically) RSA implementations against timing/side-channel attacks, by blinding the data before operating on it.
Example: suppose you are writing code to decrypt data, i.e., to compute $y=x^d \bmod n$, given the input $x$.  The naive way to do is just to compute $x^d \bmod n$; but it turns out this can be vulnerable to timing and other side-channel attacks.  One defense is to blind the data before raising the $d$th power.  In more detail, pick a random number $r$; compute $s=r^e \bmod n$; compute $X=xs \bmod n$ and then $Y=X^d \bmod n$ and then $y=Y/r \bmod n$.  You can notice that $Y/r=X^d/r=(xs)^d/r = x^d s^d/r = x^d r/r = x^d \bmod n$, which is what we wanted to compute.  However, this process makes it hard for an attacker to learn anything about $d$ using a timing attack, because the exponentiation process works on a random value $X$ that's not known to the attacker, rather than on the known value $x$.


I've looked a bit more into it and there is one PCG type with a 128 bit state, where the output is marginally decoupled from the internal state.
PCG is a suite of algorithms to generate pseudo-random numbers that have been created on top of existing lightweight random number generators so that they:

stay lightweight;
pass the various statistical randomness tests;
are possibly less predictable.

Now only the 3rd part is of interest with regards to cryptography. However, all but one of the algorithms seem to have a state of 64 bit or less (if I discount the one that has been deemed insecure by the author). That makes them directly unsuitable for cryptographic random number generation.
That leaves us with PCG-XSL-RR, the only one that makes any claim to be secure. This seems to have been accomplished by adding a XorShift on the state and a few very simple operations to derive the output of the state:
output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122)

Although there are certainly very simple stream ciphers, it seems to me that we need analysis to see if many outputs cannot be used to derive the state bits. As long as that analysis is not performed, just stating that it might be secure, and that the prediction difficulty is "challenging" doesn't make a cryptographically secure algorithm.
Personally calling it "secure" is therefore unwarranted. Listing the prediction difficulty as "challenging" means using weasel words to indicate that no sufficient analysis is performed and that the security of the algorithm is unknown. If the state can be retrieved then the algorithm would be fully predictable after all. Without knowing the details of how much output is required for such an unknown attack, how can we have any trust in that statement?

Now that was putting it very black and white, and even accuses the author of incorrect statements. However, we have to consider all the statements made by the author of the algorithm to at least partially exonerate her:

I know that if I were trying to predict a random number generator, I'd want something easier than the PCG family. But if I wanted actual crypographic security for secure communication, I'd probably want to use something that has been around longer and seen more scrutiny.
Hopefully as time passes, the PCG generation scheme will receive scrutiny from people with far more expertise in crypographic security than me, and we will have a clearer picture about how easily it can be predicted. With that in mind, I hope to offer some crypographic secuity challenges in the future to encourage people to try to break it.

So please consider it insecure until analysis has shown otherwise, and maybe use a generator where the words "cryptographic" and "security" are spelled correctly, preferably with the word "analysis" attached to it...


LSB extraction in MPC: Doubts about correctness

The protocol is only designed to work when $a$ is in the range $\{-2^{k-1},\dots,2^{k-1}-1\}$. This ensures that $c$ doesn't overflow mod $p$, as long as $p$ is sufficiently large.
In the paper they ensure this by choosing $p > 2^{k+\kappa+\log n}$, where $\kappa$ is a statistical security parameter and $n$ is the number of parties. See the discussions on p3-5.


Well, if "weak one way" means that you shouldn't be able to consistently find preimages, that is, inputs that generate a specific output, and $mult(a, b)$ is defined as the integer multiplication $a \times b$, then $mult$ would not meet that definition.

For an arbitrary output $C$, we can set $a = C$ and $b = 1$; hence $mult(a, b) = C$.


Encoding multiple fields with same AES key and vector?

Speaking in broad strokes, reuse of the key is fine - reuse of the IV: not fine.  From wikipedia: "Properties of an IV depend on the cryptographic scheme used. A basic requirement is uniqueness, which means that no IV may be reused under the same key".  You also need to decide on a mode of operation, as different modes will dictate different requirements for the IV/nonce.


Is there need for message authentication if a public key is transmitted and then used to encrypt a symmetric key?

Notice: This answer assumes the user doesn't encrypt the initial contact because I misread that part. Will update accordingly in due course.

  Is there even need for the hash in the server response so the client knows it hasn't been MITM'd (because the server has proved it decrypted the client's public key)?

Sharing the hash of a key is a bit risky in general so I'd say shy away from doing that. In your case there's another reason why you shouldn't: You are correct about MITM, anyone can generate a key and send it back to the user.

The server must sign its response so the user is sure of its origin.

  Can an adversary which doesn't know the server's private key ever change the RSA ciphertext so it passes the OAEP check routines?

The probability of that happening is negligible. Even if it does your security doesn't depend on OAEP's sanity checks, it depends on the strength of RSA. See next for details

  [...] will end up using a garbage symmetric key—is this dangerous i.e. could be exploited in some way?

No. There are two ways to spot the problem: One is by signing the message - if there's a mismatch between the signature and the message, you know you can stop there.

If there's no signature, the plaintext should conform to some format (which could be a checksum encrypted along with the plaintext). If your application decrypts an altered message which does conform to the format, you're either very lucky or the app doesn't bother checking, which would make it absolutely worthless.

In your case, let's say the client gets a garbled symmetric key. The server (conforming to the protocol) would expect the client to say Hello! and instead would decrypt something along the lines of £Gh^T-31j3mqjgeY, which is a strong hint that something's amiss.

  is my simple plaintext hash-based authentication secure?

No. See the answer to the first question. Anyone watching the user will see his public key coming along, generating a new keypair for every server won't help at all.


Comparison of values in Paillier homomorphic encryption

Can [comparison] be done using homomorphic encryption?

Not without interaction with the person with the private key.

Suppose there was a possible way; given $E_k(a)$ and $E_k(b)$, one could determine whether $a < b$.  If so, then one could use that to decrypt - given $E_k(a)$, one can encrypt various values of $b$ and then check whether $a < b$ or not - when we find a value $b$ such that $a < b$ and $a \not\lt b-1$, then we know the value of $a$.

Now, another possible meaning of comparison is, given $E_k(a), E_k(b)$ create $E_k(0)$ if $a < b$ and $E_k(1)$ if $a \ge b$.  In that case, Pallier along with that comparison operation becomes fully homomorphic; for example, to compute the NAND of $E_k(a)$ and $E_k(b)$, one just compares $E_k(1-a)$ (easily computed with Pallier) to $E_k(b)$ - once we have a homomorphic NAND function, we can construct any circuit.

  And I know subtraction can be done using homomorphic encryption, but can anyone simplify the steps?

Given $E_k(b)$, we can compute $E_k(-b)$ simply by computing the modular inverse of $E_k(b)$ - that's because $E_k(b) = g^b r^n$ and so $(E_k(b))^{-1} = g^{-b}(r^{-1})^n$, which is a valid encryption of $-b$.

Then, we can do the normal homomorphic addition to compute $E_k(a - b)$


Activation keys and asymmetric encryption

You can not compress an RSA signature much below the private modulus size. All methods that I know double the cost of either signing or verifying for each extra bit trimmed, after the first one or two which comes nearly for free.

The higher-order bit of an RSA signature can be trimmed: just use a padding scheme such that the padded message $R$ verifies $2R<N$ (the two padding schemes of PKCS#1 have this property); normally the signature would be $S=R^d\bmod N$, but rather use $\tilde S=\min(S,N-S)$, which is at least one bit less than $N$ is. On the verifier side, after computing $\tilde R=\tilde S^e\bmod N$, get back the original $R=\min(\tilde R,N-\tilde R)$.

At the expense of more work, the signer can trim more bits by using a randomized signature scheme (that is, one such that multiple signatures of the same message using the same key are different, because there is randomness in the message representative; an example is RSASSA-PSS of PKCS#1), and signing multiples times until the signature happens to be suitably small (say 16-bit less than $N$ is).

At the expense of more work for the verifier, we can trim still more bits, that the verifier can find by trial and error (says the low-order 24 bits).

So pulling every of these tricks together, the signer will need to make in the order order of $2^{13}$ signatures (I'm assuming the public modulus is chosen on the low side of the interval defined by the modulus size), and the verifiers $2^{23}$ checks (which will remains bearable, especially with $e=3$. Problem is we saved less than 4% (for 1024-bit modulus).

One thing to consider is a RSA signature scheme with message recovery, which squeezes a message in the signature. An example is ISO/IEC 9796-2 which allows about $n-h-16$ bits of message in a signature with $n$-bit public modulus $N$, and a $h$-bit hash; for 1024-bit RSA and SHA-256 that's 94 bytes of message (some of which must be scarified to remains compatible with the tricks above). If there is a message to convey that is near or above that recoverable size, and it does not matter that the message is unintelligible until after the signature has been verified, nothing beats RSA (or Rabin) with message recovery when it comes to compactness.

However, for a really short signature when message recovery won't apply (including when the message to sign needs not be transferred with signature, including e.g. a customer identifier known by the verifier), we need to move away from cryptography based on Integer Factorization

For a long time, the systems giving the shorter signatures have been the Schnorr signature scheme (description and references here), based on the Discrete Logaritm problem, which has $3b$-bit (resp. $4b$-bit) signature for conjectured (resp. proven) $b$-bit security. e.g., for 80-bit conjectured security (sometime compared to 1024-bit RSA), a signature can be 30 bytes.

There are message-recovery variants (references here) which allow to embed a $b$-bit message in a $4b$-bit signature with provable security.

And we can trim some few bits by the same tricks as for RSA, and the same curse that each bit trimmed doubles the effort of one of the signer or verifier.

There's even better, notably Boneh–Lynn–Shacham signature, which approach $2b$-bit signature for $b$-bit security. However, the parameters to use are not easy to find (hence this question), and my understanding is that computational requirements are non-trivial.


ZKP: Asymmetric encryption with confidential message and known hash

If you wanted to prove a statement like hash(a) = y, I would recommend you to use a generic  zero-knowledge protocols which proves the computation of a boolean circuit using a witness w like presented here and here. The authors first paper even published a reference implementation of SHA256 on github. Even though it's not impossible to additionally prove a statement like z = enc(a), I would recommend you not to do that for several reasons:

The performance will likely be poor due to the expected circuit size and depth.
Considering the adversary model you want to be secure against and the algorithm you choose, it may be still possible to create attacks if you don't pay attention.


how much trust can we place in protocol verifiers?

We know that traditional mathematical proofs can contain mistakes, and that these mistakes can remain undiscovered for years. Sometimes, the scheme is secure even if the proof is incorrect, e.g. RSA-OAEP. Sometimes, the scheme is mildly flawed, the flaws undiscovered because of mistakes in the proof, e.g. HMQV. And sometimes a scheme is simply insecure.

We know that formal systems can fail to describe the real world and therefore prove incorrect results, e.g. BAN logic, but nowadays formal systems seem much more complete.

Formal systems typically work with idealized cryptography. It is sometimes possible to prove that some idealization is sound, but in general this is difficult. Which means that in principle, it might be possible to design schemes that are secure in the formal system, but insecure regardless of what cryptography is used to instantiate the formal object. Similar results exist for the random oracle model and the generic group model, but still the random oracle model is considered a good heuristic for security in the real world (the generic group model less so).

Many systems restrict attention to various forms of encryption and digital signatures. This is in some sense good, because it is likely that the idealization is sound. On the other hand, you often cannot even express Diffie-Hellman in the formal system, which means that it is less useful. Where Diffie-Hellman can be expressed, the group model is often very limited, which means that the formal system might be unable to express various attacks involving subtle properties of groups, and as such it is much less clear how sound the idealization is.

The end result is that formal systems with tool support that are sound and capable of modeling the schemes you are interested in are useful and often very easy to work with. Traditional mathematical proofs are useful, but they are difficult to work with.


What is the use of segments in Cipher Feedback Mode (CFB)

Actually, s is in CFB mode to handle transmission channels for the encrypted data that can add or drop individual bytes.

In the olden times (say, the 70's), it was common to transmit data over serial channels, for example, RS-232.  These channels were not perfect, and one common error we see is that if the transmitter sent 7 bytes, the receiver might get only 6 (or possibly 8); this would happen only on occasion, but it was a definite possibility.

Now, consider what would happen if we sent CBC-encrypted data over such a channel.  The first time we drop a byte, what would happen is that the block boundaries that the encryptor and the decryptor assume would not line up; what the encryptor thought was the first byte of the next block, the decryptor would assume is the last byte of the previous block.  The decryptor would get gibberish, and (this is the important point) there is no mechanism for them to ever resync.

That is what s in CFB mode is for; if we set s=8, then after a drop (or add) error, the decryptor will get the next 8 bytes (8 assuming DES; this is the 70's after all) as gibberish, but then it will start to decrypt correctly (assuming, of course, that the transmission channel doesn't give us any more errors).

Now, times have changed; we don't deal with such channels that much any more.  In addition, we are considerably more sensitive to what an active attacker could do; if we did need to deal with such a channel, we're more likely to break up the plaintext stream into a series of records, encrypt (and MAC) each record separately, and insert a noncryptographical resyncing protocol (e.g. byte-stuffing in end-of-record markers) on top of it.  That way, an error may cause us not to receive a record or two, but nothing more (and the attacker could not introduce any bogus data).

As for the s parameter in OFB mode, that is universally recognized as a bad idea; using an s < n vastly increases the probability of OFB falling into a short loop, with no benefit in compensation.


Are there any high level memory-hard PBKDF constructions?

Are there any memory-hard PBKDF constructions that can be implemented
  using only common standard crypto primitives, like (generic) hash
  functions and/or block ciphers?

Of course there is one, and it even got a "special recognition" at PHC:
Catena.

I won't go into the details of Catena here (the paper does it much better on its 50+ pages), but it comes with pebble-game-based security reductions, rigorous security proofs, default instances and a alot of customizable parameters (namely four):

It uses a cryptographic primitive, the paper suggests Blake2b, but really any hash will do, which you can compute quickly
It uses a round-reduced cryptographic primitive, although a full-rounded version will also work
It takes an optional randomziation layer, to harden memory initialization
It takes some "memory-hard" function

Finally it uses all these parameters and a clever graph driven data flow to achieve basically all desirable properties being expected from a modern password hash.

Note: Default parameters for the latter two choices are provided, so that the user basically has the choice between two Catena variants based on their favorite hash.


repeated use of HKDF-extract on the same PRK

Taken directly from the RFC:

  The second stage "expands" the pseudorandom key to the desired
  length; the number and lengths of the output keys depend on the
  specific cryptographic algorithms for which the keys are needed.

The use of the plural here suggests (at least to me) that yes, it's ok to expand the same PRK several times with different contexts.  Can you provide any links (within SE or otherwise) that suggest otherwise?

Also from the RFC, regarding the 'info' parameter of the expand step:

  In particular, it may    prevent the derivation of the same keying
  material for different    contexts (when the same input key material
  (IKM) is used in such    different contexts).


Weakness of Hash_DRBG when entropy is mixed in gradually

It is hard to say what design rationale went into the design of the NIST DRBGs, which are ridiculously complicated ways to turn short-output PRFs into long-output PRFs typical of bureaucratic government crypto.

Certainly one can say generally that no entropy pool with incremental seeding can thwart an adversary who can witness outputs before adequate entropy has been supplied to the pool.  Here an entropy pool is a state with an ‘absorb’ and ‘squeeze’ operation (or ‘enter’ and ‘extract’); the usual notion of a PRNG or DRBG is a special case where you absorb a seed once and squeeze output forever after.

Why can't you thwart this?  Say the adversary is bounded to a budget of $2^{128}$ crypto operations.  (Here a crypto operation is, e.g., an absorb followed by a squeeze, and is some constant number of bit operations.)  If you absorb an input with 64 bits of entropy, from the attacker's perspective, and squeeze a long-enough output, the adversary can expect to try $2^{63}$ possible inputs before finding the one that matches the output.  Now the state has no entropy, from the attacker's perspective.  If you try to incrementally add another 64 bits of entropy, it's too late—it's as if you hadn't added the original input.

Why would NIST apply this warning to Hash_DRBG but not HMAC_DRBG?  I dunno, why would NIST not comment on the provenance of the standard $P$ and $Q$ base points in Dual_EC_DRBG even after John Kelsey personally asked the NSA where they came from and was rebuffed?  Government bureaucracies are formalized systems of exacerbating confusion of malice with incompetence.


Encryption Scheme & Perfect Secrecy [Katz & Lindell]

What does, say, $P(K=k)$ mean exactly?

It signifies the probability that the key $K$ selected by the key generation algorithm $Gen$ is the value $k$.

The notation he is using is that $P(condition)$ (actually, they use $Pr[condition]$, perhaps to emphasize that $P$ isn't a function on the value condition, but rather its probability distribution) is the probability that the condition is true.  For example, if I flip a fair coin, we have $P(\text{heads}) = 0.5$

  What is the domain and codomain of the random variable $K$?

The key space $\mathcal K$

  What is the set $\{K=k\}$?

It's not a set; it's an equality which is true with a certain probability.

  Also, what is the domain of Gen?

The key space $\mathcal K$


Recommended minimum entropy for online passwords in 2018

If the password is salted, pick a password uniformly at random from ${\geq}2^{128}$ possibilities.

Example: A sequence of ten words from a 7776-word diceware list.
Example: A sequence of twenty graphic US-ASCII characters.

If the password is unsalted, pick a password uniformly at random from ${\geq}2^{256}$ possibilities.

Example: A sequence of twenty words from a 7776-word diceware list.
Example: A sequence of forty graphic US-ASCII characters.

If you do this, the cost of evaluating a password hash—be it MD5, PBKDF2-HMAC-SHA256, scrypt, or argon2id—is immaterial: an adversary must perform an expected ${>}2^{127}$ bit operations to try enough guesses to find your needle among the haystack of possibilities.  Nobody can afford that, and it's not likely all of humanity could in the foreseeable future afford that.

Details. Suppose every one of $t$ users draws their passwords uniformly at random from $n$ possibilities.

If the passwords are salted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n)$ trial evaluations of the password hash.  If the passwords are unsalted, the expected cost of an attack to find at least one of the $t$ passwords is $O(n/t)$ trial evaluations of the password hash.

The expected time may be faster if the attacker spends money to power $p$ computers in parallel: if salted, $O(n/p)$; if unsalted, $O(n/(pt))$.  But powering sixty computers for a minute is not cheaper—whether accounted in joules, rubles, or bitcoins—than powering one computer for an hour.

There are always fewer than $2^{128}$ users, so as long as $n \geq 2^{128}$, the advice above guarantees that the adversary's expected cost is always at least $2^{127}$ evaluations of the password hash.

Using a password hash like argon2id raises the cost of evaluating the password hash versus a hash function like SHA-256 not designed for hashing passwords.  It is important for engineers designing systems that handle passwords to take responsibility for raising the attacker's costs using the resources available to legitimate users, and to use a password hash.  But from the user's perspective, the advice above makes it immaterial what password hash the engineer choose, whether argon2id or MD5—the cost of an attack is insurmountable for humanity.


Agreeing with @otus but adding more background and context than I think belongs in comments:

This is an OpenSSL question though you don't say so; all other SSL/TLS software I've looked at uses the RFC spellings DHE ECDHE DH_anon ECDH_anon, but OpenSSL was written yonks ago with EDH in some places (mostly the ones dating before ECC was introduced and there was no ECDH to confuse with EDH) and ADH and AECDH in all. You may not have observed the latter two because all unauthenticated suites are disabled by default and very rarely used. So far the devs have been reluctant to "fix" spelling because that could break config files, scripts, calling applications, etc. Especially since OpenSSL cipherstrings are so arcane there seems to be a whole stratum of websites confidently ordaining "the single good way to configure ciphers in openssl or $thing_using_openssl", nearly all of them different and many of them long out of date or completely wrong.

If you look at the cipher details with openssl ciphers -v [$cipherstring] you will see which key-exchange and authentication methods (and also data cipher and MAC) are used for a given ciphersuite. In recent versions if you use -V (cap vee) it also shows the code value sent on the wire, which you can match to the RFCs to be 100% certain it is really the same thing.

A few months ago there was discussion on the maillist about accepting the standard spellings while still preferring the OpenSSL ones. See
http://rt.openssl.org/Ticket/Display.html?id=3203 (guest/guest for readonly access);
it appears this made it into 1.0.2, currently in beta.

1.0.2 is also planned to add the NON-ephemeral (and non-EC) DH suites. It's not clear if anyone wants or ever used them -- I've certainly never seen any public CA offer DH certs. (Integer DH keys have slightly different encoding than DSA and thus need a different cert, whereas one EC key & cert can be used for either ECDH and ECDSA depending on KeyUsage and technically can be used for both although it is not considered best practice to use one key of any type for multiple purposes.) Adding to otus' correct statement about static-ECDH, static-DH also will not provide PFS.

A more glaring (but non-DH) spelling difference is that OpenSSL names entirely omit "RSA" for plain-RSA key-exchange (not something authenticated by RSA). Also it varies spelling of 3DES. E.g. standard TLS_RSA_WITH_3DES_EDE_CBC_SHA is OpenSSL DES-CBC3-SHA. (Technically EDE is redundant because EEE, the alternative originally considered, was rejected, but putting the 3 after CBC suggests "inner" CBC mode which also was considered but rejected in favor of "outer".)


Given a certain entrophy per character, how long should a passphrase be to guarantee key strength?

No, your formula isn't correct. I don't know how you came to it, so I don't know what's wrong with your intuition.

You can check whether your formula makes sense with dimensional observation — it's the same kind of reasoning that helps a lot in physics. Write all numbers with their units:

entropy rate = 1.5 bit/character
random key size = 128 bits
passphrase length = X characters
information content per character in a 26-character alphabet = log2(26) bits/character = 4.7 bit/character

Your formula: $\dfrac{128\text{ bit}}{4.7\text{ bit/character}} \times 1.5\text{ bit/character} \approx 40.85\color{red}{\text{ bit}}$

We expected a number of characters, so something is wrong here.

In order to achieve the strength of a 128-bit random key, we need a total entropy of 128 bits for the passphrase. It's a simple proportionality rule:
$$
\text{entropy per character} =
\frac{\text{total entropy}}{\text{number of characters}}
$$
so
$$
X\text{ characters} = \frac{\text{total entropy}}{\text{entropy per character}}
 = \frac{128\text{ bit}}{1.5\text{ bit/character}}
 \approx 85.3\text{ character}
$$
Sanity check: the passphrase length turns up as a number of characters. Since the number of characters has to be an integer, it needs to be at least 86 characters long.

The size of the alphabet is irrelevant here because the passphrase isn't chosen randomly over all possible sequences of letters. “Passphrase” implies that it is a sentence fragment in a human language, or close enough. 1.5 bit/letter is a common estimate for the entropy per character for English: the number of English sentences of length $L$ is approximately $2^{1.5·L}$, so if you pick one at random, you have a $1/(2^{1.5})^L$ chance of being right.


Signature for Identity Verificaton on "offline" P2P network

If an attacker has full access to the peer then you cannot expect security to be kept. However, you assume that if an attacker has access to a device that it is full under his control.

This assumption is not true in practice if you embed a secure element. A secure element is a device such as a smart card chip that can keep one of more secret values and perform actions on it, for instance signing so it can authenticate itself to the network.

So a secure element can be used to keep your problem from occurring. It is however impossible for a secure element to make a system moderately secure on its own. However, describing such a system is beyond what you can expect from a Q/A site.


Set membership check between untrusted parties

There is a simple and elegant solution with the additive variant of the ElGamal encryption scheme. I'll first describe the most naive version, and then discuss a bit some improvements.

First, A (who holds a database of size $N$ that is assumed to be over some group $\mathbb{Z}_p$) computes a degree $N$ polynomial whose $N$ roots are the elements of its database, in normal form. Think now of the $N+1$ coefficients $(a_0, \cdots, a_N)$ (in $\mathbb{Z}_p$) of this polynomial as the database stored by A.

B has an input $x \in \mathbb{Z}_p$. He sets up an ElGamal encryption scheme with message space $\mathbb{Z}_p$ (the message is encrypted in the exponent: $E(m;r) = (g^r, h^rg^m)$ where $(g,h)$ is the public key, and the secret key is $s$ such that $g^s = h$).

B computes encryptions $(c_1, \cdots, c_N)$ of $(x, x^2 \bmod p, \cdots, x^{N} \bmod p)$ and send them all to A. A can compute homomorphically from $(c_1, \cdots, c_N)$ an encryption of $a_0 + \sum_{i=1}^N a_i x^i \bmod p$. The latter is either $0$ (if x is in A's database) or some other value. A picks a random element $r$ from $\mathbb{Z}_p$ and homomorphically multiply this encryption by $r$. He sends back an encryption of $r(a_0 + \sum_{i=1}^N a_i x^i) \bmod p$ to B. The latter checks whether this encrypts $0$ or not (no need for efficient decryption, so the use of the additive ElGamal is not a problem here). If it's 0, his element is in A's database, otherwise it is'nt.

The problem of this method is that it requires sending $N$ ciphertext, which can be large. A slightly more involved solution is to let B send instead encryptions of $(x^1, \cdots, x^{\sqrt{N}})$ and of $(x^{\sqrt{N}}, x^{2\sqrt{N}}, \cdots, x^{N})$, a total of $2\sqrt{N}$ ciphertexts. The server now computes the coefficients of the degree $N$ polynomial whose roots are the elements of his database, written in the following form:
$P(X) = \sum_{i = 1}^{\sqrt{N}} F_i(X)\cdot X^{i{\sqrt{N}}}$, where each $F_i(X)$ is a degree-${\sqrt{N}}$ polynomial with coefficients $(a_{ij})_j$. From the ciphertexts sent by B, A can homomorphically compute encryptions of $F_i(x)$ for each $i$. Then, he generates ${\sqrt{N}}$ random masks $r_i$, and returns encryptions of $F_i(x) + r_i$ together with an encryption of $\sum_i r_i X^{i{\sqrt{N}}}$, homomorphically computed from the ciphertexts he revealed from Bob.

From the $F_i(x) + r_i$ and $\sum_i r_i X^{i{\sqrt{N}}}$, Bob can recover $P(x)$, and nothing more (this can be formally proven). The total communication was reduced to $3\sqrt{N}+1$ ciphertexts. However, I think one must now have efficient decryption for this to work, hence another scheme (e.g. the Paillier scheme) must be used.

If the encryption scheme allows to perform one multiplication in addition to many sums (there are simple schemes doing that under the LWE assumption), then this can be reduced to $O(N^{1/3})$.

I know that considerably more involved techniques allow to reduce that to as small as $O(\log N)$, but I think they are just theoretical works, not really practically relevant as of today. I do not claim that any of the solutions I discussed is the optimal one it terms of practical efficiency, I do not have a detailed knowledge of a state of the art. They are just simple solutions that come to my mind.


Where can I begin to study the math behind modern cryptography?

One of the best avenues for study is to practice breaking existing cyphers.  Start small, with classic cyphers such as monoalphabetic substitution, polyalphabetic cyphers, transpositions, etc.  Do the daily Cryptoquip in the newspaper!  Learn what makes them weak, what makes them exploitable, and what makes them strong.  Then move on to stream cyphers, to mechanized cyphers like the Hebern and Enigma machines, and then to modern electronic block cyphers.

With each cypher you attack, you first learn how to attack a simplified or reduced round variant, then apply it to the more complex and complete implementations.  Along the way, learn how some of the various protocols and implementations have made cyphers weak, or provided defenses against certain forms of attack.  Finally, study some of the advanced attacks, and replicate their results.

To implement these attacks, you'll discover new topics you need to understand in order to pull them off:  statistics, modulo arithmetic, algebra, recursion, protocols, zero knowledge proofs, bignum math, game theory, Feistel networks, whatever.  These are the same tools you will later use to understand and construct cyphers and protocols of your own.

Once you study attacks on cyphers, protocols, and implementations, you'll better understand why some of the more esoteric design decisions were made, or why certain mechanisms were added.  A fascinating case study for the value of this approach can be a found by reading the history of the Lucifer cypher.

Good luck!


How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key

Pick a random $x$ value. Calculate $y^2 = x^3+ax+b \bmod p$. Then try to form $y$ by taking the square root $\bmod p$. If the square root fails then no $(x,y)$ pair exists on the curve. If the square root works, flip a coin; if tails form $y = p-y \bmod p$.
This is how public key compression works. Only the low bit of y is saved. Form $y^2$, take the square root (which had better work). If the low bit of $y$ is wrong then form $y = p-y$.


Is there any open-source white-box implementation of AES or DES?

I add my whitebox AES implementation on GitHub in:

C++
Java

C++ version implements both Chow's (mixing bijections, input/output encodings, external encodings) and Karroumi's (dual AES in each column) whitebox AES scheme plus Billet's key recovery attack on both schemes.
Java implements Chow's scheme only.
PS: Due to low reputation I post links to schemes to the comment below.


Does ShaCrypt have the properties which make BCrypt slow on GPUs?

From the answer you linked to:

  For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).

What that tells us is that it is fairly easy to get big performance gains on SHA-256 (which also implicates SHA-512) using a GPU. The question then is, does ShaCrypt do anything special to slow GPU's down?

Looking through the example source code you liked to, it doesn't look like it. What I was looking for was a large (a few kilobytes) data structure that would be constantly accessed and modified. That doesn't exist from what I could see. Sure, there are data dependencies, which would slow down a single password calculation, but nothing to prevent parallelization of multiple passwords.

On an interesting note, there are JtR patches which would give you ShaCrypt GPU capabilties in John the Ripper. I was unable to find performance numbers, however.


If the people who generated the pre-paid card numbers did their job properly, then no, it is not possible to reconstruct these numbers.

The simplest pre-paid card number generation system is to use purely random numbers, and store generated numbers in a database. To verify a generated number, simply look it up in the database. The function which can then rebuild the numbers is the RNG -- if that is /dev/urandom from a Linux/*BSD/MacOS/Solaris system, or CryptGenRandom() from a Windows system, then there is no known weakness which would allow an attacker to merely recognize the RNG as being that specific system (as opposed to, say, someone flipping a coin repeatedly), let alone predict the next number with a non-trivial probability of success.

The method with random numbers and a database has two main drawbacks:

You can get collisions. E.g., if you use 16-digit numbers, you can expect to reach your first collision after 108 (100 millions) generated numbers. You can deal with that by checking your generated numbers against the database, but this can make the industrial process more complex (i.e. you have to talk to the database before deciding whether the card is worth printing).
Each number verification entails a database lookup. With millions of customers, this may imply an heavy load, especially if there are people who routinely try random numbers, just in case they get lucky (apparently, people do that). Database access is unavoidable at some point, if the card is genuine (if only to update the customer account), but one would prefer to have a lighter way to filter out most invalid card numbers.

So a slightly more complex method involves symmetric encryption. Namely, you use a block cipher operating over the space of $n$-digit integers. So you have a secret key $K$; let $E_K$ be the encryption function, and $D_K$ the decryption. You keep a counter $c$ of generated card numbers. To get a new card number:

Increment $c$.
Encode $c$ into a sequence of $m$ digits and pad it with $n-m$ zeros.
Encrypt the whole thing with $E_K$.

Then, when it comes to verify a number, try first decrypting it with $D_K$: if the result does not end with $n-m$ zeros, then you know that it is not a genuine number, and can be rejected without involving the database. This method also guarantees the total absence of collisions.

The tricky part in this method is having the appropriate $E_K$ / $D_K$ function. It must be a pseudo-random permutation; anything like a stream cipher is inadequate (including AES in CTR mode). If the number length ($n$) is 19 or less (but close to 19), then this is easily done with a 64-bit block cipher $B$ such as IDEA or the venerable 3DES (apparently, the IDEA patents expired, which is why it becomes recommendable again). Then, to encrypt a sequence $d$ of $n$ digits:

Encode $d$ into 64 bits (interpret $d$ as an integer, write down the value in binary); call $x$ the resulting sequence.
Set $x \leftarrow B_K(x)$ (encryption with the 64-bit block cipher).
Interpret $x$ as an integer value $e$.
If $e ≥ 10^n$, loop to step 2. Otherwise, define $E_K(d) = e$.

In plain words, we use the block cipher repeatedly until it gets us back to the appropriate space of integers between $0$ and $10^n-1$. If the block cipher is a secure pseudo-random permutation, the this process is also a secure pseudo-random permutation. The average number of iterations will be $2^{64}/10^n$; for instance, with $n = 16$, this will require on average about 1845 invocations of the underlying block cipher: a very small amount, since a cheap PC can do millions of those per second, with a single core.

With this method, predicting valid numbers with success probability higher than $10^{m-n}$ would require breaking the 64-bit block cipher (that is, there mere existence of such a predictor would be viewed as an unredeemable weakness of the block cipher). So, with IDEA or 3DES, no worry. With practical figures: with $n = 16$ (16-digit card numbers) and $m = 11$ (you have room for one hundred billions of valid numbers), then only one random number in 100000 will require actual database lookup.

If $n$ is much smaller (e.g. $n = 12$), the computational cost can become excessive, but the core principle can still be applied, provided that you design a custom block cipher which runs over sequences of digits -- this is a difficult task (don't do this at home ! I.e., do not deploy such a system in production without getting some professional advice from a trained cryptographer), but there are existing tools (see this question for details).


Is it possible to create a "digital seal" to tell if a document has been opened?

Encrypt your document, and embed a web address (and login details) in the packaging from which a reader can get the decryption key. The website must be trusted. The website logs will tell you when software has requested the key to decrypt it.
If you also want to protect confidentiality, encrypt with two keys. One is the usual private key used to protect confidentiality, that the recipient has been given securely, the other is the tamper seal that has to be obtained from the website.


AEAD cipher implementations are generally encrypt-then-authenticate internally (while the CBC ciphers in OpenSSL were not). TLS really was in need to get rid of the authenticate-then-encrypt which required special handling of the CBC code for block ciphers such as AES. The AEAD ciphers - regardless of the internal structure - should be immune to the problems caused by authenticate-then-encrypt.

AEAD algorithms generally come with a security proof. These security proofs are of course dependent on the underlying primitives, but it gives more confidence in the full scheme none-the-less.

These ciphers are often single pass (OCB, not often used), 1.5 pass (GCM, Poly1305) or 2 pass (EAX). That means that they generally have an execution speed advantage over two pass schemes using CBC + (H)MAC. Even a scheme as EAX can have performance advantages if a higher level language (Java, Python etc.) is used to implement TLS. This is because it is easier to create a fully optimized implementation for one algorithm (EAX) than for a combination of two algorithms at protocol level (CBC + HMAC). Internally EAX is simply CTR + CMAC.

Furthermore AEAD schemes generally can be (forced to) adhere to RFC 5116. That means that there is only one interface required for all of the AEAD ciphers with regards to the handling of the IV and plaintext. It is of course possible to let CBC + HMAC adhere to this RFC as well though.

Speed and security is probably the reason for Google to already support ChaCha20 + Poly1305/AES in Chrome. With such a big elephant in the room it is kind of hard to ignore this scheme by Daniel J. Bernstein (et all). It's a 1.5 pass AEAD cipher that uses a fast stream cipher underneath, so it's pretty efficient overall.


Would it be secure to use random numbers from random.org in a cryptographic solution?

The more I think about it, the less I would be willing to use Random.org for any sort of cryptographic application. My reasons are listed below.

See Q2.2, the groups listed are not cryptographic groups and potentially (or probably) don't have cryptographers on their evaluation teams
They specifically say not to use it for cryptography
It is closed source. So, I would have no way of knowing if they properly mutex their RNG so that only one person is drawing from it at a time. There are other implementation issues that I (or someone/some group much smarter than I could check for).
Using this would require an internet connection for all randomness.
Current CS-PRNGs are much faster and options are available which suffer from none of the weaknesses listed above.
The RNG could change at any time without me knowing.

That said, these reasons don't necessarily answer the question. They only give insight as to why I personally wouldn't use Random.org for cryptography. Would it be secure to use Random.org in  cryptographic solution? Possibly. There really isn't enough information to really know.


What is the time complexity of the RC4 encryption & decryption algorithms?

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit.

So:

 c = m ⊕ G(k)
 m = c ⊕ G(k)

Where c is ciphertext, m is plaintext, G is the RNG and k is the key.

As such, all stream ciphers should be O(n) against the length of input data.


How to check the strength of an encryption algorithm?

The first step is to write a new question on crypto.stackexchange.com asking for advice on how to check whether if it is secured enough (or not).

The second step is to stop, throw away everything you've done and become an expert in GPG and then port GPG to your platform.

The rationale for being so discouraging is that if you have to ask how to check whether it's secured enough you obviously don't know nearly enough to even start writing an app that encrypts text securely. Many people who would have a very good idea about how to check the security would balk at the task of writing something like GPG themselves.