Why does the DES crypto algorithm NOT use 2 rounds?

DES with 2 rounds is broken. It is trivial to find a way to get the key with much less work than for the full DES (and even that is broken).

DES is a Feistel cipher, so we have two halves, the left and the right half. For every round, we do something with the one half and a subkey, and then XOR it with the other half. After that we switch both halves, repeating the whole algorithm until we have done all rounds.

Let's say we begin with both halves before the first round, $l_0$ and $r_0$. The calculated values for the next round are, with $DES()$ as the encryption function, this:

$$ l_1 = r_0 $$
$$ r_1 = DES(r_0) \oplus l_0 $$

If we continue this for another round, we have two "randomly mixed" halves. It's not easy to get the ciphertext from this, especially if the round function is really good. The one of DES is not so good, and that's the reason why we use 16 and not 4 rounds. (4 is the minimum of rounds needed, but explaining that would be beyond the scope of this answer.)

But there's another way to solve this. We can use the chosen-plaintext attack. If we encrypt an arbitrary plaintext, and then the same plaintext with one bit in the left side inverted, we will see some interesting things in the ciphertext: The right half has changed pretty much, but in the left half only the one bit you inverted earlier did change. This works with every Feistel cipher, not just DES. If you have to determine if DES was used, then you have a bit more work to do. I can't tell you how, but searching for something like "breaking DES reduced rounds" would be a good way to find a solution.


What is a good algorithm to scramble data in a 2-D grid

It seems like you just want to permute a string.  E.g., transform the string "123456789"+ 3 blanks into the string "28_37941_5_6".  Putting it into a 2-d array is just formatting (e.g., agree its to be a 4x3 array and then after every 4 characters add a line break).

There are plenty of algorithms to randomly permute a string.  For example, the Knuth shuffle (aka Fisher-Yates shuffle) requires you to go through each element of a list and randomly swap it with itself or an earlier item in the list.  (That is for the i-th position in the list do a swap with the i-th position and the j-th position where j is a random number between 0 and i inclusive).  For example, this shuffle is implemented in python below:

import random

def knuth_shuffle(to_shuffle):
    for i in range(1, len(to_shuffle)):
        j = random.randint(0, i)
        to_shuffle[i], to_shuffle[j] = to_shuffle[j], to_shuffle[i]
    return to_shuffle

We can slightly modify this to take the random numbers as a "key" which tells us what permutation to do:

import random

def generate_key(input_length):
    key = []
    for i in range(1, input_length):
        j = random.randint(0, i)
        key.append(j)
    return key

def knuth_keyed_shuffle(to_shuffle, key):
    shuffled = to_shuffle[:] # create a copy of input to modify
    for i, j in zip(range(1, len(shuffled)), key):
        shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
    return shuffled

def knuth_keyed_unshuffle(to_unshuffle, key):
    unshuffled = to_unshuffle[:] # create a copy of input to modify
    for i, j in reversed(zip(range(1, len(unshuffled)), key)):
        unshuffled[i], unshuffled[j] = unshuffled[j], unshuffled[i]
    return unshuffled

For example in python (after defining the functions above)

In [3]: text = list("123456789***")

In [4]: print text
['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

In [5]: key = generate_key(len(text))

In [6]: print key
[0, 0, 2, 2, 1, 1, 1, 6, 8, 2, 11]

In [7]: shuffled_text = knuth_keyed_shuffle(text, key)

In [8]: print shuffled_text
['3', '8', '*', '2', '4', '1', '9', '7', '*', '6', '5', '*']

In [9]: knuth_keyed_unshuffle(shuffled_text, key)
Out[9]: ['1', '2', '3', '4', '5', '6', '7', '8', '9', '*', '*', '*']

Some notes: first this will not be particularly secure.

Also, if you aren't particularly fond of using a list of integers as your key, you can encode it to a single integer between 0 and (n!-1) by using the factorial number system (factoriadic).  The key is essentially a number written in base factorial with the least significant digit first -- the first digit is 0 or 1; second digit 0,1, or 2; third digit 0, 1, 2, or 3, ... n-th digit is an integer from 0 to n inclusive.


how does the simulator work when the corrupted party has no input?

A simulator is a thought experiment whose purpose is to:

show that the adversary learns no more about the honest party's inputs than he's supposed to,
show that the adversary's effect on the honest party's output is consistent with a legitimate input.

If the functionality takes no input from the corrupt party, #2 is moot but we still have #1. A canonical example is the zero-knowledge functionality, which takes no input from the verifier. When the verifier is corrupt, the purpose of the simulator is to demonstrate the zero-knowledge property.

There is no general implication between semi-honest and malicious security. Take any semi-honest protocol and modify it to add the behavior "if the other person sent me the message $(\textsf{asdf}, v)$ then send my input to that party and output $v$." Adding this behavior to the protocol doesn't affect semi-honest security since honest parties never send each other $\textsf{asdf}$ messages. But the effect on malicious security should be clear, and it has nothing to do with which party has input, etc.


Can I use Shamir's secret sharing scheme for multiplicative homomorphism for secure multiparty computation?

As far as I know, you can not do multiplication with (m,m) shamir secret sharing. The typical method to do multiplication on shamir secret shares increases the degree of the sharing polynomial, which is why the parties run an additional protocol to reduce the degree. That is why the degree of the sharing polynomial must be less than $m/2$ if there are $m$ parties.

If you indeed need (m,m) (or $m$ out of $m$ parties must be present to do reconstruction and multiplication), and the only operation you need to compute is multiplication (which I'm not sure about since your comments state you want to do multiplication, but your question mentions dot product), then I'd suggest using multiplicative secret sharing.

If instead you need $m$ out of $m$ computation/reconstruction, but need to do both addition and multiplication operations, you'll have to go with some of the newer MPC constructions which achieve full-threshold security (SPDZ and some of it's references or subsequent works which cite it).


How does the sender obtain the receiver's public key?

The sender receives the public key through some other (secure) channel.

The whole security of public key encryption relies on precisely this "small detail": there must be a way for the sender to obtain the receiver's public key through some other, secure channel. The definition of "channel" is actually very broad here, and denotes simply a means of transferring information.

To name but a few real world examples of what can be used to exchange keys:

A trusted key server or repository, e.g. OpenPGP public key servers like sks-keyservers.net.
A file downloaded from a website which is trusted to belong to the person whose public key you wish to obtain, and the connection to this website is secure and properly authenticated (i.e. using HTTPS).
The receiver sends the public key on the same channel as the one it intends to receive the message, but the key's authenticity can be verified by a trusted external party such as a PKI (Public Key Infrastructure).
A USB stick, disk, piece of paper or some other type of media handed over in person.
A telephone call (!).

Of course, one should nevertheless not forget that there is a myriad of attacks which can be performed on these channels too, such as using fake certificates issued by rogue CAs in order to bypass HTTPS or also flooding public keyservers with fake PGP keys. After all, a cryptographic protocol can only be as secure as the less secure of its parts.


MD5, SHA-1, SHA-256, etc. are one-way functions: given the hash of an input, nobody knows how to find the input better than by guessing, and the best cryptographers in the world have tried.

But guessing is always a possibility. You just try a lot of inputs until you find one with the desired hash value. If the input is a member of a small set, for example if you know it's a dictionary word, this can be done very quickly. On the other hand, if the input includes enough unknown bits, it's unfeasible. For example, if the input includes 128 random bits, then it would take a billion PCs about the age of the universe¹ to get a decent chance of finding the right input.

The websites you found don't “decrypt” anything. What they do is, they calculated a lot of hash values and stored them in a database. When you ask them to reverse a hash, they look it up in the database. This only works if the hash is one that they have in the database.

¹  Say 2³⁰ calculations per second per computer, times 2³⁰ computers. The age of the universe is about 2⁶⁰ seconds, giving you a 2⁻⁸ chance of success.


How do you construct a practical full-domain hash function?

I don't know if that counts, but authors of recently selected SHA3 function Keccak mention its ability to perform Full Domain Hashing:

  Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing [...]


In order to tell for certain which algorithm is used from the cipher text alone, you have to break the key as well. It is however possible to make some educated guesses about the algorithm.

Your strings are only 88 bits long. That rules out every asymmetrical algorithm that I know of.

If it is correct, that all of those strings encrypt the same message, then it would have to be a probabilistic encryption (which is also best practice security-wise).

A block cipher in CBC mode is one of the first probabilistic encryptions, that many cryptographers learned about. However a CBC mode encryption takes up at least two blocks worth of cipher text, and I know of no block cipher with blocks as short as 44 bits. I do know a few with 64 bit blocks, but except from very special cases, such short blocks should be considered obsolete by now. AES has a 128 bit block, meaning your messages are too short for even a single block.

Every probabilistic encryption uses an IV (possibly called a nonce in some contexts). In case of CBC the IV is a full block, but other modes like for example CTR can use a shorter IV. Additionally since CTR operates as a stream cipher, there is no requirement for full blocks being used in the enciphered data. Partial blocks will work just fine in CTR mode.

Your strings are likely 3 + 8 bytes, with either 3 bytes IV and 8 bytes data or vice-versa. An IV as short as 3 bytes is ridiculously insecure (which hasn't stopped it from being used in widely used protocols in the past).

If the messages are using 3 bytes of IV and the 8 bytes for some reason is a full cipher block, then it would have to be one of the ciphers with a 64 bit block. DES is one cipher with such a block size, Blowfish is another. To the best of my knowledge among the block ciphers with 64 bit block size, DES was the most widely used, and Blowfish was the most secure.

It could also be that there is 8 bytes of IV and 3 bytes of message. When encrypting with CTR it could make sense to split the input blocks into half IV and half counter. If IV and counter are 8 bytes each, the block size would have to be 128 bits. There are many ciphers with that block size. AES is one of them. If this is how the encryption works, that message would be 3 bytes long. It might be that the message being used is always either yes or no.

Encryption without integrity is almost always a bad idea. But since people are so often told about encryption and not so often about data integrity, it is not so unusual to encrypt data without integrity. 88 bits is very short if it is both probabilistic and protects integrity, so I guess it doesn't do both. So if you believe it really does provide probabilistic encryption, I guess it has no integrity.

Feeding mangled messages into the legitimate decryptor would provide clues as to whether any integrity checks are in place. Other than that, it is probably a lot less work to simply reverse engineer the code than to break the encryption.


Finding public key out of ECDSA certificate

The 00 04 tells me, that I'm lucky and no point compression is used, which means, that the abscissa and ordinate Key are easy to find out.

Nope. The 00 tells you that no bits are unused from the bytes making up the ASN.1 BIT STRING, which is indicated by the first 03 valued byte.'

04 does of course indicate an uncompressed point, so your end result would still be correct.

  Because of my prime number (related to my prime256v1) I know, that length of X and Y Key is 32 octets. So I take the first 32 octets to form the X-Key and the last 32 to form the Y Key

Officially the order of the curve determines the key size. Often there is no difference though. The name of the curve also contains a strong hint about the key size. The public key is however within $0$ and $P - 1$ inclusive (see comment of Poncho below).

  Because my program requires 36 octets for X- and Y-Key, I add 4 leading zeros to get my result.

That should be OK, if the result is indeed interpreted as big endian (network order) value. It beats me why you need to add 4 additional zeros (to the left, I presume), but that might be a hardware implementation issue.


How can Cipher Block Chaining (CBC) in SSL be attacked?

The recently demonstrated attack against SSL (BEAST) was an IV misuse attack and not really the same thing as what happened to XML Encryption. Nonetheless, here is what happened with SSL.

Basically they found two things:

A way to get the browser to encrypt data under the session key used by an existing SSL connection and
A mistake in the way SSL was written that allowed that ability to be leveraged to read messages.

Let's says you are using AES with CBC mode. Encryption for the first block of a message is basically $AES(K, IV \oplus m)$. The IV is typically sent along with the ciphertext.  This is a simplification ignoring how longer messages are handled, see Wikipedia's CBC article for more details, but it works for this purpose.

The point of this is that multiple encryptions of the same thing don't result in the same cipher text because the IV is random and data XOR random = random, so you never actually encrypt the same message. Thus an attacker who can cause the browser to encrypt data can't simply guess at what the message was and verify that guess by causing the browser to encrypt the guess and checking if it matches the encrypted message they want to read.

Well the problem is, if I know the IV in advance, this no longer holds: If I want to guess that some previous message was "attack at dawn" (with IV $IV_1$) and I know the IV for the next message will be  $IV_2$, then I merely need to cause the browser to encrypt  a message $m$ such that  $IV_1 \oplus \text{"attack at dawn"} = IV_2 \oplus m$, and check if the ciphertext blocks match.

SSL used the last 128 bits of the previous encrypted message as the IV. Because there was time between when this message was sent and the next, the attacker could make a guess.

This is a basic overview, there still some details of how you do this efficiently to get the session cookie sent with each HTTP request, but that's the gist of it.

This attack is not possible with TLS 1.1 and 1.2 (as they generate a new initialization vector for each message), and the OpenSSL library worked around this problem already in TLS 1.0 by sending an empty message (i.e. only padding and MAC) directly before each real message, so the ciphertext of this empty message is used as initialization vector for the real one (and this is not predictable without knowing the key). (Edit: it turns out this feature is disabled in OpenSSL because it breaks large numbers of servers who assume a zero byte read  is an end of file. Instead, the deployed fix is "1/n-1 record splitting" where one byte is sent in a block and the rest of the message is in the next block)


Confused about how chosen ciphertext attacks work?

The adversary clearly can do that. But if the adversary wins with this strategy, then the scheme in question cannot even be CPA secure and is far away from reaching the goal desired from CCA security. Recall, CCA security requires that even having access to a decryption oracle (for any ciphertext but the challenge ciphertext) does not help the adversary.


Why are some websites seemingly immune to self-signed certificate MitM attacks?

The short answer is HTTP Strict Transport Security
.

  When a web application issues HSTS Policy to user agents, conformant
  user agents behave as follows:

  Automatically turn any insecure links referencing the web application into secure links. (For instance,
  http://example.com/some/page/ will be modified to
  https://example.com/some/page/ before accessing the server.)
  If the security of the connection cannot be ensured (e.g. the server's TLS certificate is not trusted), show an error message and do
  not allow the user to access the web application.

(emphasis mine)

On websites that have it configured, many browsers will not let you add an exception for untrusted certificates.


Mathematical proof of a combined hash function

Ignoring the issue of output length I mention in the comments, you should be able to prove this without intermediate steps. Here is an outline of how I would do it.

Without loss of generality let one particular hash function be the one that is collision resistant. It doesn't matter which one. Say $H_3$.
Assume that $M$ is not collision resistant. This means, you can find $m_0\neq m_1$ such that $M(m_0)=M(m_1)$.
Show how this would lead to a collision in $H_3$ directly. This leads to a contradiction, so $M$ must be collision resistant.

This is a proof by contradiction.


Finding AES ciphertext stealing test vectors?

Depends on what exactly you need.

Some test vectors can be found in the document "RFC 3962 - AES Encryption for Kerberos 5". If you take a look at page 11, you'll find some test vectors for CBC with ciphertext stealing, using an initial vector of all-zero.

Also, there are test vectors to be found at more exotic places like mozilla.org test vectors for AES CTS. They took the original test vectors for AES CTS-3 (Kerberos) and modified them for AES CTS-1 (NIST).

I'm sure that you favorite search engine will help you pinpoint the rest.


Can I measure entropy through compression only?

Can I estimate the entropy of the source producing such file using essentially the byte reduction (when compressing the source's output)?

No, at least for Shannon entropy. Entropy is a characteristic of the source, that can't be determined from a finite sample of the output of the source. It's can't even be estimated in practice without information about what the source is, and the question gives no such information.
The best we can is estimate a plausible upper bound of the entropy of the source that generated the file: $75742/1559454$ entropy bit per output bit. That's not a mathematical certainty: it's mathematically possible that a perfectly random source generated that file (the probability is $2^{-8\times1559454}>0$). And that's not a practical certainty either, unless we add a vague hypothesis that the observed characteristic goes on: a device which output consists of the $1559454$ fixed bytes followed by indefinitely many uniformly random bytes is a source with $1$ entropy bit per output bit.
We do not get any lower bound better than $0$. Proof: any deterministic program that indefinitely outputs is a source with zero entropy. And it is trivial to make a deterministic program that indefinitely outputs a sequence starting with the $1559454$ bytes (perhaps, repeated). That's not merely theoretical:

The program which output consists of the repeated sequence of two bytes a  produces output which first $1559454$ bytes matches the problem statement, even for some actual compressor; say, one that never compresses by more than a factor of 20 (that's quite plausible for e.g. an audio compressor).
Even if we restrict to files that could reasonably occur in actual use, it's entirely possible that a program designed to obfuscate a file into english words, written as an (elementary and rather poor) steganography tool, has output that matches the problem statement (for an actual text compressor) when fed as input a file of about $50000$ bytes, including if it is all-zero.

Conclusion: practical procedures that attempt to assess the entropy of a source from its output only are doomed to, at best, give a plausible upper bound of that entropy (and can do so only under the hypothesis that the output tested is representative). Computing a compression ratio is one such method.


Thoughts on secure hashing and the "mds" algorithm

That is an absolutely terrible idea, here is why.
His algorithm works as follows:

Hash the input data
Take the length of data (presumably in bytes)
TRUNCATE the hash so that the length value in bytes plus the truncated hash is the output length of a standard MD5 hash (128 bits)

Here is an example of a 1MB data file being hashed
MD5(data) = e319709e00ec584c412603b83f661b2b
len(data) = 40000000
MDS(data) = e319709e00ec584c412603b840000000

Most MD5 collision attacks are on signatures with a fixed length, this will only make it easier to create a collision, since you do not have to worry about the truncated bits at the end as part of your collision calculation.
The length of the input data for some applications is also a secret or can expose information about the data, so it is part of the input padding to the hash and not the output.


Security consequences of HMAC(m, K) instead of the correct way HMAC(K, m)

$\DeclareMathOperator{\HMAC}{HMAC}\newcommand{\ipad}{\mathrm{ipad}}\newcommand{\opad}{\mathrm{opad}}\newcommand{\xor}{\oplus}\newcommand{\concat}{\mathop{\Vert}}$Yes.  It becomes vulnerable to collisions in $H$, if $m$ is longer than the block size of $H$, because in that case $\HMAC_m(k)$ is not actually $$H\bigl((\opad\xor m)\concat H((\ipad\xor m)\concat k)\bigr).$$  Rather, it is $$H\bigl((\opad\xor H(m))\concat H((\ipad\xor H(m))\concat k)\bigr).$$  (See RFC 2104, §2 ‘Definition of HMAC’, p. 3.)

What about single-block messages?  Well, it's unlikely that an attacker could find a structured pair of collisions $(\ipad\xor m_0, \ipad\xor m_1)$ and $(\opad\xor m_0, \opad\xor m_1)$ in $H$ for $m_0 \ne m_1$, but if they could, and if $H$ is Merkle–Damgård as is assumed in the usual HMAC security reductions (and if it's in the BLAKE2 or SHA-3 family, why bother with HMAC?), then $(m_0, m_1)$ would collide under $m \mapsto \HMAC_m(k)$ for any key $k$, enabling an attacker to immediately distinguish it from a random function or to forge messages authenticated under it.


Yes you can reuse $p$ and $q$, i.e. you can have multiple key pairs using the same group, as long as the secrect keys $x_B$'s are chosen independently at random.

Essentially, what you are asking is this, given $y_B=g^{x_B} \in G$ where $G$ is the order-$q$ subgroup of $Z_p^*$ and $x_B \in Z_q$, and additional $y_i =g^{x_i} \in G$ for polynomial many $y_i$'s, is the trapdoor commitment is still secure?

Some more details:

The security of commitment requires two things: hiding and binding.

For the hiding property, note that your commitment scheme is perfectly (information theoretically) hiding, thus a commitment $g^w{y_B}^r$ is uniformly random and the uniformity comes from the fact $r$ is uniformly random. This also means the distribution of $g^w{y_B}^r$ is independent of all $y_i$'s the adversary can get, and those $y_i$'s provide no advantage for the adversary to learn $w$. So the hiding property holds.

For the binding property, you can reduce it to the DL problem such that if an adversary $A$ can break the binding property of your scheme, then we can use it to break the DL problem. Suppose a DL adversary who has $y=g^x \in G$ and needs to find $x$, he can choose random $x_i,x_2,\ldots,x_n \in Z_q$ and compute $y_1=g^{x_1},y_2=g^{x_2},\ldots,y_n=g^{x_n}$ and invoke $A$ with $y$ and the additional $y_i$'s. The adversary $A$ can break the binding property means with a non-negligible probability, $A$ can find two different pairs $(m,r)$ and $(m',r')$ such that $g^my^r=g^{m'}y^{r'}$. If $A$ returns such a pair, it must hold that $m+xr=m'+xr'$, and $B$ can compute $x=\frac{m'-m}{r-r'}$, thus solve the DL problem. Since we assume the DL problem is hard, such $A$ does not exist. Therefore the binding property also holds (as Squeamish Ossifrage also said in the comment).


You are confusing TCP packets and Signal messages.

First, TCP ensures the order of packets inside a session. TCP does not ensure the order among sessions. This means that TCP cannot be used to ensure that the Signal messages are received in the order they were sent.

Also, TCP was not build to resit active tempering by a MITM agent, unlike Signal. It would be extremely unwise for Signal to assume that the properties of TCP are reliable.

Moreover, the end client might not keep track of the previous messages: they could be deleted or the client could have been reinstalled on another device (while keeping the secret keys).


For the purposes of a bloom filter you need a number of hash functions. Cryptographic hash functions are designed so that changing a single bit in the input should change many (around 1/2) of the output bits.

So, say you have a good hash function $h$ (e.g., SHA256 though MD5 should work for your purposes too) a good option for you would be to use use:

$h_1(m)=h("1" || m)$
$h_2(m)=h("2" || m)$
$\vdots$
$h_n(m)=h("n" || m)$

Where $||$ is concatenation. Then you only need one hash function. This is basically what they are doing in this java implementation.

  Is there any existing literature that describes the loss of distribution?

Not that I am aware of. But think about it this way, if there were a significant change from the uniform distribution computable in a reasonable amount of time we wouldn't use the hash function for cryptographic purposes.

Now, is there some sort of attack you are worried about?


Brute force knowing a part of the password

We solved this problem in just 9 hours 37 minutes.

Here is how to do it.

Tools you need:

sudo apt-get install cryptsetup
sudo apt-get install dh-autoreconf
sudo apt-get install libcryptsetup-dev

1 - Dump the encryption header of your device using cryptsetup toolset, here /dev/sda1 was our device yours could change:

sudo cryptsetup luksHeaderBackup --header-backup-file headerOutput /dev/sda1

2 - Generate a dictionary with all the possible combinations of the part of the passphrase you forgot; We paid a professional solution for this but there are tons of tools and programming language to accomplish this task for free.

3 - Download and compile this free project (https://github.com/glv2/bruteforce-luks)

wget https://github.com//glv2/bruteforce-luks/archive/master.zip
unzip master.zip
cd bruteforce-luks
sh autogen.sh
./configure
./make

4 - Recover your password

./bruteforce-luks -t 6 -f dictionaryYouGenerated yourLUKSHeaderFile

Notice the step "4" will be extremely slow since it utilizes the CPU and the software is not optimized at all, that's why we bought a similar software made for GPU's and we also hired a powerful cloud distributed computing solution (I can't put names here)

In our case the cost of everything was exactly 4400 USD (developer + software + cloud service)
Lesson learned from now on we are storing the passphrase printed in a safe so this never happens again. Thank you and I hope this help someone in the same desperate situation.


BN-Curves for 256-bit symmetric security

A BN-curve over a 256-bit prime field $\mathbb{F}_p$ has, being an elliptic curve, a 256-bit group attached to it, say of order $N$. As the best known attacks take $\approx\sqrt{N}$ times, this gives us 128-bits security against discrete logarithm attacks.

The curves also have embedding degree 12. That means we can use a pairing to map a discrete logarithm problem to $\mathbb{F}_{p^{12}}$. Given that $p\approx 2^{256}$, we know that $p^{12}\approx 2^{3072}$. Hence $\mathbb{F}_{p^{12}}$ is a 3072-bit finite field, and solving a DLP there should (see warning below) take about $2^{128}$ effort. So mapping the DLP to a finite field does not help an attacker, which is great.

If we move to 256-bit security, we will need a 512-bit group on the curve. Thus, we need to choose $p\approx 2^{512}$. The embedding degree remains 12, and we can still use the same pairing to map the DLP to $\mathbb{F}_{p^{12}}$. In this case $p^{12}\approx 2^{6144}$. According to the slides you refer to, this only gives a $<192$-bit security level. Thus $p\approx 2^{512}$ is too small for a 256-bit security level.

To obtain a 256-bit security level in the finite field, we actually need $p^{12}\approx 2^{15424}$ (according to the slides you refer to). Thus, $p\approx 1285$. This is very large, and will make computation very slow. Therefore BN-curves are great at 128-bit security level, as they make an optimal trade-off there, but do worse as the security level increases.

Warning: new attacks show that finite fields of size $2^{3072}$ do not actually provide a $128$-bit security level any more, although they did at the time of the proposal of BN-curves. So currently they are on shaky territory.


Then $$g^{r\cdot s - 1} \equiv 1 \pmod N,$$ so I can calculate $r\cdot s - 1 = k\cdot\phi(N)$.

Actually, we have $r \cdot s - 1 = a / b \cdot \lambda(N)$, where $\lambda(N) = \text{lcm}(p-1, q-1)$, and $b$ is likely to be small if $g$ was chosen randomly (example what can happen if $g$ is not chosen randomly, consider $g=h=r=s=1$).

With that, here is a randomized procedure that will find the factorization of $n$ with decent probability if $b$ is not too large:

Compute $z \cdot 2^{\ell}= r \cdot s - 1$ with $z$ odd
Select a random value $u$ and compute $v = u^z \bmod n$; if $v = 1$ or $v = n-1$, this iteration fails to find the factors; try again with another value of $u$
For $\ell$ times,

Compute $w = v^2 \bmod n$.
If $w = 1$, then this iteration succeeds, the factors are $\gcd( v-1, n)$ and $\gcd(v + 1, n)$
If $w = n-1$, then this iteration fails, try again with another value of $u$
Set $v := w$

If we went through $\ell$ loops without hitting 1 or $n-1$, this iteration fails to find the factors, try again with another value of $u$.


Endless PRNG from PRNG with specific stretch?

Most PRNG constructions can generate arbitrarily long pseudo-random bit sequences (or at least, can quite easily extended to do such).

Of course, a limited internal state size means that there will be some point from where the sequence repeats itself. (We can make the size that large that this will not occur in practice.)

A simple way to have a seekable PRNG would be to apply a message authentication code on seek and seed:

$$ R_{\operatorname{seek}} = MAC(\operatorname{seed}, \operatorname{seek}) $$

The seed should be on the key position here.

In this case, the internal state (the seed) will stay constant, i.e. a random output sequence will be repeatable by providing the same (sequence of) seek(s) again. As the seek can get (almost) arbitrarily long, you will have an (almost) endless sequence.

(Of course, if using a counter as the seek value, the counter's size must be included in the PRNG's state size, so a limited size state does not allow an endless non-repeating sequence.)

A non-recoverable PRNG is build by applying some one-way function on the internal state in each round of operation, additionally to generating the output (with another one-way function) from the state. So, given two one-way functions $f_1$ and $f_2$ and previous state $S_{\text{old}}$, we do

$$ R = f_1(S_{\text{old}}) $$
   $$ S_{\text{new}} = f_2(S_{\text{old}}) $$

and output $R$.

This PRNG will cycle as soon as $f_1^n(S_0)$ reaches a cycle. For a random function on a $n$-bit state, after an expected number of around $2^{n/2}$ steps a cycle of expected size $2^{n/2}$  will be reached.

You can combine both ideas if you don't need that seeks are commutative (i.e. that $seek(a); seek(b)$ gives the same output as $seek(b); seek(a)$.


Using a single Ed25519 key for encryption and signature

The paper On the Joint Security of Encryption and Signature in EMV is very close. Section 4.4, "On the Joint Security of ECIES and EC-Schnorr", states the following result:

  Theorem 2. In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard.

Obviously, this does not apply to EdDSA/DH out of the box: ECIES is a certain application of Diffie-Hellman, and EdDSA is a slightly modified variant of elliptic-curve Schnorr signatures.
However, the proof sketches in the paper should be easily adaptable to EdDSA combined with any other reasonable Diffie-Hellman incarnation. (The details of this depend a little on how the DH shared secret is used for symmetric (authenticated) encryption, but it seems possible to modify the proof for all realistic settings.)


Does IKEv2 protocol have two modes like IKE

No, IKEv2 has nothing analogous to 'main mode' and 'aggressive mode', and they eliminated the initial 'quick mode',

When IKEv1 was originally written, they wanted a strong separation between IKE and IPsec; they had a vision where IKE might be used for things other than IPsec (other "Domains of Interpretation").  So, they completely isolated the "negotiate IKE SAs" and "negotiate IPsec SAs" into two separate series of exchanges.

In addition, they weren't sure if it would be better to minimize the number of round trip messages, or to provide identity protection; hence they designed two different modes (which would allow implementers to select the trade-off).

When they designed IKEv2, they rethought both these options.  They realized that no one really used IKE for anything other than IPsec, and that forcing implementers to support different options was the Wrong Thing.  Hence, they tried to combine the IKE SA and initial IPsec SA negotiation into a single set of exchanges (reducing the number of round trips, hence getting most of the benefit of "aggressive mode"), while retaining the identity protection (and DoS resistance) of main mode.


A bit-sliced implementation (or the algebraic normal form) of the two FIDES S-Boxes

You can build this youself in a very mechanical process, it's only optimizing circuit size which gets interesting.

Take a 5 bit to 5 bit S-box, each can viewed as 5 different binary functions on 5 variables.

You can trivially construct any such function. A simple (inefficient) approach is to build it in normal form: write out the 32 different input values, and take only those whose matching output is 1. You can construct an expression which is the Or between sub expressions one for each row with 1 output. Each subexpression is the and between all variables optionally negated. Each variable will be as is if it is 1 on the given row and negated otherwise.
This results in a binary function for the required output bit.

You can obviously optimize this to get smaller circuits. A basic method for optimizing circuits is: https://en.m.wikipedia.org/wiki/Karnaugh_map
There are many more techniques including some which reuse structure between different bits of an S box and different S boxes.


Understanding message reversible mapping function in group G

In ElGamal encryption, the key-gen starts with a cyclic group $G$, of order $ q$, with generator $g$.

Now you want to map, $M$ into $G$. The simplest one is: if $M < q$ than map $M$ to $M$-th element in the group. If $M \geq q$ divide the $M$ into blocks. Choosing the block size is one bit less than $q$'s bit size, is easier and better.  Once you divide, map each as in the first case.

The second case is similar to what we do in the block cipher as in ECB mode. However, ElGamal is a probabilistic encryption scheme, therefore we don't need IV, but you need to use a new random $y$ for each block.

Actually, one can find more mappings, for example, the permutations. Usually, that will be costlier than the simplest one.


How can an encryption scheme be indistinguishable with multiple messages but vulnerable to an adaptive chosen-plaintext attack?

If you're asking about block ciphers. Yes, it's possible.  Security against non-adaptive attacks does not imply security against adaptive attacks.  A simple example of a block cipher that is secure against non-adaptive attacks but insecure against adaptive attacks would be a random involution.  No, it doesn't need to be nondeterministic.

We say that a function $f:X\to X$ is an involution if $f$ is bijective and $f(f(x)) = x$ for all $x \in X$.  Suppose we have a block cipher $E:K \times X \to X$ where $E_k(\cdot)$ is an involution for all $k$.  Then $E$ is not secure against adaptive chosen-plaintext attack: an attacker can request the encryption of $x$, then request the encryption of that ciphertext, and check whether the result is equal to $x$.  However $E$ can be secure against non-adaptive chosen-plaintext attack.

An example construction of such a block cipher would be

$$E_k(x) = \text{AES-Decrypt}_k(\text{AES-Encrypt}_k(x) \oplus 1).$$

This is secure against non-adaptive chosen-plaintext attack (assuming that AES is secure) but insecure against adaptive chosen-plaintext attack.

If you're asking about encryption schemes. Yes, it's possible.  Security against non-adaptive attacks does not imply security against adaptive attacks.  It's easy to construct counterexamples.

For instance, consider the following encryption scheme.  To encrypt a message $m$ under key $k=(k_1,k_2)$, we first check whether $m=k_1$.  If $m \ne k_1$, then we pick $r$ randomly (subject to the constraint that $r\ne 0$) and output the ciphertext $c=(r,\text{AES}_{k_2}(r)\oplus m, k_1)$.  Otherwise, we output the ciphertext $c=(0,m,k_1)$.

This is a crazy-looking encryption scheme, but it is possible to show that it is secure against non-adaptive attacks: basically, it is just counter-mode encryption of a single-block message (since the attacker has no hope of guessing $k_1$).  However, this is completely insecure against adaptive attacks: an attacker who observes one ciphertext can learn $k_1$, from whence they can pose a chosen-plaintext message that lets them build a distinguishing attack.


Probability for Vigenere cipher given distribution of key lengths

Okay, let's take this one apart piece by piece, with $l$ indicating keylength:

You have:

$P(l=1) = P(l=2) = 0.5$
$P(m=dd) = 0.8, P(m=de) = 0.2$
You want to know $P(c=ff)$
Implicitly, we assume that the keys are uniform random (actually not true for Vigenere with actual keywords, but there is no statement in the question).So for any combination of $c,m$, we get a probability of $1/26$ if $l=1$ and $1/26^2$ if $l=2$
Implicitly, the key is independent of the message - pretty standard assumption. And of course $l$ is independent as well.

So let's look at the case $l= 1$. Formally we express that as $P(.|l=1)$. This is a conditional probability, because we place the condition $l=1$.

So: $P(c=ff|l=1) = P(c=ff| l = 1 \cap m=de) + P(c=ff | l = 1 \cap m=dd)$
$  = 0 * 1/26 + 1 * 1/26$   (the $0$ indicates "this is not possible", the $1$ indicates "this is possible with exactly $1$ combination")

Analouge: $P(c=ff|l=2) = P(c=ff|l=2 \cap m=de) + P(c=ff|l=2 \cap m=dd)$
$ = 1 *  1/26^2 + 1 * 1/26^2$ (both possible with exactly one combination, so both $1$s)

Now, we want to get $P(c=ff) = P(c=ff|l = 1) \cdot P(l=1) + P(c=ff|l=2) \cdot P(l=2)$
$= (0+1/26) \cdot 0.5 + (1/26^2 + 1/26^2) \cdot 0.5 = 0.5(1/26 + 2/26^2)$
We just use, that the events $l=1$ and $l=2$ are mutually exclusive. And they happen to be the only possibilities we have to consider.

In the end, we get to the same conclusion as your other questions: You missed the condition on $l$ in your first approach. And then in your solution you incorporated it - but missed out on expressing it in the formulas correctly.


Does the size of a file influence the randomness if used as random input?

OpenSSL will take the file and feed it into its internal PRNG(pseudo-random number generator). That PRNG has an internal state consisting of a 1023 byte buffer and a working hash value (20 byte sha1 hash)

The algorithm used to seed the PRNG goes around the buffer, modifying the buffer in 20 byte blocks while also updating the working hash value.

Q:Should I make the file bigger?

Anything much larger than the state size of the PRNG (1043 bytes) is wasteful. Feeding in more than that many bytes of random data will not improve security (by making the final PRNG state harder to guess).

Q:Where should I put a counter value If I plan to reuse data?

Putting it at the beginning of the file might be slightly better.

Supposing you put a small integer at the end of your file. That integer would be fed into the PRNG last. That means most of the large buffer would be unaffected by its value. Only the working hash is guaranteed to be affected.

This isn't a real problem. All output is dependent on the working hash and 160 bits is more than enough entropy to foil real world attackers (even ones with quantum computers).

Should I be doing this?

No. This is a brittle approach. If an attacker gets the seed file (which you plan on re-using) they can generate all the secret keys you produced. That makes it a massive liability. If the service providing you with random data is not trustworthy they could already be doing this.

If you plan on using such a file, you must also include additional randomness from another source. You could get it from the operating system (EG: reading /dev/urandom on linux) or just bang on the keyboard for 30 seconds. More entropy sources can't hurt and will prevent this sort of failure.

Also, consider, if you trust your OS not to steal the keys why don't you trust it to supply randomness? Most operating systems do a good job of capturing and supplying randomness (as long as you wait till a few minutes after booting).


Difficulty understanding 'random square root' in enhancement to fiat-shamir

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11∗19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

What they mean by "square-root of $x$" is the value $y$ that is a solution to $y^2 \equiv x \pmod n$; as there are multiple solutions (in the cases that at least one solution exists), then by a random solution, they mean to pick one randomly.

Now, in the case of $n=209$, it turns out that there isn't a solution for $v_i = 2$ or $3$.  However, there are four solutions for $v_i = 5$, namely 29, 48, 161, 180 (and for $n$ which is a product of two distinct odd primes and with $v_i$ nonzero and small (that is, $< p, q$), there will always be either zero or four solutions); the algorithm is to set $s_i$ to one of the four randomly.

As for how to compute the square root of $x$, the procedure is:

Compute $x_p = x \bmod p$ and $x_q = x \bmod q$
Compute the values $y_p$ that satisfies $y_p^2 \equiv x_p \bmod p$ and the values $y_q$ that satisfies $y_q^2 \equiv x_q \bmod q$; and if there doesn't exist either a $y_p$ or a $y_q$ that satisfies the above equations, then there doesn't exist such a $y$.  This computation can be done in the general case by the Tonelli–Shanks algorithm (and with simpler algorithms in the case that $p, q \not\equiv 1 \pmod 8$)
Usually, the above will give two possible values for $y_p, y_q$; pick one randomly (this will perform the 'random selection' logic specified.
Use the Chinese remainder theorem to find the value $y$ with $y \equiv y_p \pmod p$ and $y \equiv y_q \pmod q$; you're done


standard way to authenticate parties with public keys without certificates

Without an out-of-band channel, no.

If all Alice has only a public key , she can't tell the difference between Bob's key and Mallory's.  Hence Mallory can mount a man in the middle attack.

To prevent this you either need a certificate or a a trusted  out of band channel though which you conform the key. The channel could be something that is harder to man in the middle ( e.g. the phone network) which you use to exchange key fingerprints, it could be an in person meeting(some people of pgp fingerprints on their business cards), or it could be that you remember the key from the last time you connected ( which only prevents subsequent man in the middle attacks)

A somewhat novel  application of this is used the ZRTP key agreement protocol used in VOIP.
ZRTP generates a short authentication string(SAS) based on the user's keys.  Bob can read that SAS to Alice and assuming Mallory can't forge Bob's voice in realtime, the channel is secure and the key is authenticated.


Does a big salt have the same memory effects as Bcrypt?

So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security?

PBKDF2, yes, pretty much. The only real difference is that salt/password are used the other way around, with the password mixed in at every step.

Bcrypt, however, is different.

In your case an attacker only needs a small amount of memory compared to computational resources. For example, you can imagine a long pipeline of hashing units, which each compute one block of the salt value and then pass the output onto the next unit.

In terms of tradeoffs, say you had memory to store a million hashes long (part of the) salt. Instead of using it all on the salt, you could store a 500k hash long part of it and 500k different password guesses. Then you can calculate a huge amount of work (500k squared) before you need the next part of the salt.

What bcrypt does is have a large part of memory it modifies. That means the memory cannot be shared among different password guesses. Also, the access pattern issue (which Thomas Pornin's comment raised) can play a part – if the access pattern is non-linear, tradeoffs are worse (halving the memory used can lead to a huge slowdown).

The salt storage issue Maarten Bodewes mentioned in comments is also important. A large number of large salts would be unwieldy to store. And you cannot just store some seed or you are in a way back to square one – a fast way to generate the "full" salt could be used to avoid storing it all.


Let us begin with what is a block cipher;
A block cipher is a family of permutations $$F:\{0,1\}^\ell\times\{0,1\}^b \to\{0,1\}^b$$ where $\ell$ is the key lenght and $b$ is the block size ( DES has 64, AES has 128 bit block sizes). From the key space $\mathcal{K}$ with $2^\ell$-size, a block cipher with the given $k \in \mathcal{K}$ selects one permutation form all possible permutations from $\{0,1\}^b \to\{0,1\}^b$. That makes at most $2^b!$ permutations. With the Stirling Formula
$$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}$$ if you plug some numbers like AES-256 you will see how small the keyspace is compared to number of possible permutations;
$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!=  \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \gg 2^{256}$$
Still what we want from a block-cipher like AES that they are a Pseudo-Random Permutation (PRP), not distinguishable from a random permutation. No one is able to show a distinguisher for AES yet in more than 20 years and no-one is able to prove it. We strongly believe it is a PRP.

Why are iterated substitution-permutation product ciphers only used on fixed-size plaintext blocks?

The substitution (Sbox in AES) can be used to design a larger block size, however, when you changed the block size from 64 to 128 bits you need a new permutation. Besides, for a better design, you will need to change the substitution, too.
When block size increased more and more, the control of diffusion (MixColumns+ShiftRows in AES) will be harder, too.
The above are some theoretical aspects of such design. There are other problems with the software and hardware. You need to implement many different sizes for software and hardware. This will increase the cost and area. Besides, in the hardware, we want small designs to reduce the area size and reduce power consumption. Even using the CTR mode removes the decryption implementation of the block cipher.
Although one possibly easily implement these in software, the problems are multiplied. You need to provide countermeasures for each implementation against the side-channeled attacks. The same applies to the hardware, too. Yet we are not perfectly able to do one, we will face multiple problems. See AES side-channel attacks, including the cache-attacks on AES.
Instead, it is better to design one with a fixed block size so that we can analyze it with more concentration. There is a nice post about the block cipher analyzing methods;

What are recommended, general strategies to start block-cipher design and/or analysis?

We can use a block cipher with various modes of operation to achieve the goal of encryption of large messages up to a limit, of course. I'll not list all of them here, each has pros and cons. Some to be mentioned

the CBC mode is a chaining based mode that uses padding to achieve encrypting the long messages. You need to be careful about selecting the key uniform randomly, selecting an unpredictable IV, and applying an HMAC to authenticate against the bit flipping attacks and padding oracle attacks when possible.

The CTR mode is a counter bases mode that turns a block cipher into a stream cipher, Instead of listing all pros and cons please read here;Disadvantages of AES-CTR?. In your case, the CTR mode doesn't need padding at all, one can encrypt arbitrary long messages ( not that so long, CTR designed for PRF when using a PRP be careful).

With the above modes you can only achieve CPA security and in modern cryptography, we require more than that. One should use Authenticated Encryption modes (AE) ( and possibly with Associated Data (AEAD)), like AES-GCM and ChaCha20-Poly1305. You will achieve more than CCA (AEAD > CCA). Each has pros and cons,

What are the rules for using AES-GCM correctly?

Does ChaCha20/Salsa have the same bit strength as AES for identical key sizes?
The one real problem with these two modes is the reuse of a (key, IV) pair. Both modes have an extension;

AES-GCM-SIV: The SIV Mode of Operation for
Deterministic Authenticated-Encryption (Key Wrap) and
Misuse-Resistant Nonce-Based Authenticated-Encryption

Daence: Salsa20 and ChaCha in Deterministic Authenticated Encryption with no noNCEnse

Arbitrary block sizes are also problematic if the block size is less than 128. There is a nice page about this, see

Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN

Another solution for your case the stream ciphers, they are designed to fast and can encrypt for large block sizes. They doesn't need paddings and they are encryption bit-by-bit or more in some designs.

Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?

The above reasons, especially the design and implementation. This will be more clear if you consider that during that age, people hadn't advanced as today. And the time showed that some decisions were right.

From my laymen point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.

Hold on! they are not magical tools that like in LEGO that you may replace a 2x8 block with 4 2x2 blocks. Even there in some places, the structure will fail!
Each variation in the design needs to be designed, analyzed, and needs good implementation.


Elliptic Curve Verifiable Secret Sharing

The values

$b_i = \prod\limits_{j \in B, j \neq i}\frac{j}{(j-i)}$

are the evaluations of the so called Lagrange basis polynomials at point $0$. These terms are often also called Lagrange coefficients and can be computed by any participant and $B$ is the index set of the participants.

The formula

$a_0^{(i)}G = \sum_{j \in B}b_j f_i(j)G$

is just a Lagrange polynomial interpolation, i.e., a weighted sum of the lagrange coefficients. That's just Shamir's secret sharing in the "exponent" (not literally, because we have an additive group here, but the reconstructed value $a_0^{(i)}=f_i(0)$ is hidden due to the DL assumption).

This means reconstruction of the secret (the share $a_0^{(i)}$ of party $i$) without revealing the secret value itself (since the value $a_0^{(i)}$ is not revealed from $a_0^{(i)}G$ as this would require solving the discrete log problem in the used group and the values $f_i(j)G$ also do not reveal the values $f_i(j)$.

Basically, the verifiable secret sharing is achieved by letting every party $i$ revealing "shares" of their share value $a_0^{(i)}$ (hidden due to the DL assumption). Consequently, the participants can verify whether their shares $a_0^{(i)}$ are consistent without revealing their share values (what verifiable secret sharing is about).

Hope that helps.


If I encrypt data with two different ECC Private keys, how secure is the result?

TL;DR: If you separate the keys then you're fine.

In my answer I'll outline an encryption algorithm using two ECC keys and achieving (nearly) squared security and the general result for how to properly use two keys in group-based cryptography.

First note that a private key $a_1$ is a random integer used to multiply a base point on elliptic curves like $P=a_1\times Q$. Now observe that adding a second key $a_2$ to the mix yields $P'=(a_2\cdot a_1) \times Q$ which is equivalent to some $P'=k'\times Q$ and thus not stronger than simple discrete logarithm.

Now if you were to calculate two different public keys, security of these keys will actually multiply: $P_1=a_1\times Q, P_2=a_2\times Q$ requires you to break both instances of the elliptic curve discrete logarithm problem (ECDLP). The best speed-up for your keys only would be $\sqrt2$ which is absolutely negligible if we are talking about numbers like $2^{128}$.

On a side note it may be noted that this idea is obviously true, because you've just created two ordinary, unrelated public ECC keys (on the same key) of which you can find many, many more samples on the internet (all with the same type of mathematical relation). Also note that this independence doesn't hold for finite field discrete logarithms as the Logjam attack has demonstrated impressively.

So in (first  section) conclusion one could say: If you don't relate your public keys (and you use multpiles) you're fine.

Now, how can we use this actually for proper encryption. There are multiple ways to do this:

Do a standard KEM/DEM encryption and use ECDH twice for the KEM part
Do an ordinary ECC encryption (ECIES?) and just apply it twice with different private keys to the message.

The first approach should only be preferred if you don't already have a (working, tested and known-safe) implementation of ECIES (or some other ECC based encryption) at hand. If you dou have such an implementation, by all means use it and apply it twice (with different private ECC keys) and you're done.

If you don't have such an implementation, you have to go for ECIES. I'll leave the details to Wikipedia, but in a nutshell, ECIES works with two functions to encrypt data: $\operatorname{Encaps()}$ and $\operatorname{Encrypt()}$. Encaps will provide you with a session key which you can use to bulk-encrypt the data as well as with some data that allows $\operatorname{Decaps()}$ to recover the session key (given the private key). In ECIES, Encaps basically is ECDH: You put in the public key, it chooses a random exponent and will output you the exponent multiplied with the basepoint ($P_s=k\times Q$) and the hashed ECDH result ($s=H(x(k\times P))=H(x((k\cdot a)\times Q))$) which you then can plug-into the bulk encryption. Now what you do, is you use Encaps twice (with two different public keys obviously) and the securely combine the keys together (e.g. using HKDF).

Now the bulk encryption should also be at a comparable security level ($\approx$ 256-bit) and if it is, then you should be safe until general quantum computing is able to break ECC.


(Actually, this is about second-preimage resistance, not collision resistance)

  I expected the last two ones because they exceed the range of the hash-length. The first one however was unexpected and I simply cannot explain it. Is it because of bad chance or is it because of the function?

Actually, even for a good hash function, that has a relatively good chance at happening.

Let us assume that our hash function $F$ with an $n$-bit output is "good", that is, it acts like a totally random function.

Then, we evaluate $F(1)$ and get a specific value $z$.

Then, we evaluate $F(x)$ for $1 < x < 2^n$, and see if $z$ happens to occur a second time.

As $F(x)$ is random, then for any particular $x$, it will happen to be the value $z$ with probability $2^{-n}$; that is, it will be a value other than $z$ with probability $1 - 2^{-n}$

So, for $F(x)$ never to be $z$ for any of those $2^n - 2$ values of $x$, each probability is independent, and so the total probability is the product of the individual probabilities, namely, $(1 - 2^{-n})^{2^n-2} \approx 1/e \approx 0.368$ (where $e$ is Euler's constant 2.718281828459...)

That is, there is an about 63% chance of $F(1)$ appearing at least once somewhere else, even if you limit the range of the input to the hash-length.


Here is a great video which shows principles for public key cryptography using colors, which makes it easy to understand for everyone:
https://www.youtube.com/watch?v=YEBfamv-_do

Now what you missed is that it is possible to generate a secret key, and give away something which enables encryption but not decryption. This is the principle of public key encryption.


Can an encrypted message be derived from only keys?

No, you cannot derive the plaintext from keys if the plaintext nor the ciphertext is ever transmitted. However, to break a cipher you don't need to do that. You only have to show that you can get any kind of information about the plaintext (other than information about the message size, which is hard to avoid if any size message can be present).

Now if you see repeated "keys" then you know that the same message is being targeted, and the scheme would be considered broken. This is why ECB mode is considered broken: you cannot decrypt any message, but you can see repeated blocks.

Now in your case you don't seem to have any cryptographic keys, as keys cannot be shared with everyone - what you seem to be doing by sending them over a unsecured channel. Your lookup scheme doesn't really use cryptography in that sense. They may be database keys, but database keys are a different concept.


RSA: How close d should be to n, given default public exponent e = 65537

Is there any particular test, applied in common implementations, to verify that private exponent $d$ is less than but close to modulus $n$ ?

Yes, for some lenient definition of close. FIPS 186-4 is a de-facto standard that some implementations follow. It prescribes$$d\gets e^{-1}\bmod\bigl(\operatorname{lcm}\left(p-1,q-1\right)\bigr)\tag{1}\label{eq1}$$which implies $d<p\,q/2$ thus¹ a $d$ at least one bit less than the modulus is. And in the end of FIPS 186-4 appendix B.3.1 additional criteria 3 lies the prescription:

In the extremely rare event that $d\le2^{nlen/2}$ (where $nlen$ is the bit size of the public modulus), then new values for $p$, $q$ and $d$ shall be determined. A different value of $e$ may be used, although this is not required.

Such test is pointless from a theoretical standpoint when both:

$e$ is chosen before $p$ and $q$, as is usually the case.
The only significant dependence about the value of $e$ of the mostly independently and randomly chosen $p$ and $q$ is that $\gcd(p-1,e)=1=\gcd(q-1,e)$.

Condition 2 should always hold for a proper RSA key generation procedure. Even if $p\bmod e$ and $q\bmod e$ where fixed public constants, condition 2 could still hold for truly small $e$ including $e=65537$, up to at least say 20 bits: revealing that little information about $p$ and $q$ appears unlikely to ease factorization.
The only technically sound rationale for $d\le2^{nlen/2}$ or other test against small $d$ is to prevent the import of an inappropriately generated private key; and in an otherwise proper RSA key generation procedure with modulus bit size $nlen\ge1024$ (the minimum in FIPS 186-4), to catch a malfunction or a bug.
In a fielded security device (Smart Card, HSM), if that test fails at key generation, the Right Thing is to fall into a safe state where the gizmo needs at the very least to be physically reset before anything else goes, perhaps after metaphorically falling on one's sword, that is burninating/zeroizing all secret material. In code under development, that test should be an assertion. If something needs to be rubber-stamped, do whatever is morally defensible to satisfy the authority with the rubber-stamp.

I have noticed that using (strong primes per some criteria) the bit length difference between $d$ and $n$ is never bigger than $6$.

It was not tried hard enough, or something is broken in the key generation procedure. There is no good reason why that would hold for $e=65537$. That's even though, contrary to $\eqref{eq1}$ mandated by FIPS 186-4, $d$ is computed per
$$d\gets e^{-1}\bmod\bigl((p-1)(q-1)\bigr)\tag{2}\label{eq2}$$
As explained in that other answer, $d$ per $\eqref{eq2}$ is expected to be roughly uniform in the interval $\bigl[(1+\varphi(n))/e,\varphi(n)\bigr)$ and we should sometime see it near the bottom, thus with 15, perhaps 16 bits less than the public modulus. However we need to perform about $e$ attempts to approach that limit.
If the test against $d\le2^{nlen/2}$$\eqref{eq1}$ is used, that should be with $d$ per $\eqref{eq1}$. Absent error, that test mathematically can't fail for $d$ per $\eqref{eq2}$ with $e<2^{256}$ and $n>2^{1023}$ as mandated by FIPS 186-4. Failure of the test is at least theoretically possible when using $\eqref{eq1}$, should $\gcd(p-1,q-1)$ happen to be huge. Which is extremely unlikely for proper generation of $p$ and $q$.
Both $\eqref{eq1}$ and $\eqref{eq2}$ are allowed by PKCS#1 since the origin, thus $\eqref{eq1}$ is unlikely to cause an interoperability problem even if a private key is moved across implementations (which should be the only case when the method used for the determination of $d$ matters, since all mathematically valid $d$ for a given public key produce the same numerical results when properly used in RSA). Contrast with the use of $\eqref{eq2}$ which has fair probability to lead to failure at key import by an implementation written with FIPS 186-4 as a reference.

¹ By definition of $e^{-1}\bmod\lambda$, and given that $\lambda=\operatorname{lcm}\left(p-1,q-1\right)$, and given that primes $p$ and $q$ are large, thus $p-1$ and $q-1$ both are multiple of $2$.


If you look at it from the right direction, lattice-based crypto (and the Shortest Vector Problem) can be viewed as a 'global minimization' problem.


Brute-force attack given multiple hash prefixes

If you have two prefixes, say $p_1$ and $p_2$ assuming a well designed hash function, this will give you two lists of possible candidates $L_1,L_2$ each of size roughly $2^{24}.$ The correct value is in both of these lists. It is unlikely to also have spurious candidates since assuming uniformity o relevant variables and fixing, say the list $L_1$, the probability that a random quantity from $\{0,1\}^{56}$ is not in $L_1$ is
$$
\left(1-\frac{2^{24}}{2^{56}}\right)=\left(1-\frac{1}{2^{32}}\right),
$$
since $\lim_{n\rightarrow \infty}\left(1+\frac{x}{n}\right)^n=\exp(x).$ Thus
the probability that the $2^{24}$ elements in $L_2$ all fall outside $L_1$ is
$$
\left(1-\frac{1}{2^{32}}\right)^{2^{24}}=\left[\left(1-\frac{1}{2^{32}}\right)^{2^{32}}\right]^{2^{-8}}\approx \exp(-2^{-8}) \approx 0.9961
$$
so only in one of about 250 trials would there be a spurious candidate in addition to the correct candidate.

Edit: It is widely believed and supported by experimentation that SHA-1 is such a function. Ignore my earlier reference to universal hash functions.


Independence of answers to queries sent to a random oracle

Firstly, note that saying that the queries $u_1,\ldots,u_Q$ are distinct implies that they are not independent, for example, if $u_i=a$ then $u_j\neq a$ for all $j>i$.

Secondly, your argument indeed follows from the definition of a Random Oracle found in Stinson's book. Let $\mathcal{O}:\mathcal{X}\rightarrow \mathcal{Y}$ be a random oracle. That means that for every query $u$ that has not been queried before, it holds that $Pr[\mathcal{O}(u)=y]=1/|\mathcal{Y}|$ for every $y\in \mathcal{Y}$. Now, since $u_1,\ldots,u_Q$ are all distinct it follows that

For all $y\in\mathcal{Y}$ and $i\in[Q]:  Pr[\mathcal{O}(u_i)=y]=\frac{1}{|\mathcal{Y}|}$

$\Rightarrow$ For all $(y_1,\ldots,y_Q)\in\mathcal{Y^Q}$:  $Pr[\mathcal{O}(u_1)=y_1,\ldots, \mathcal{O}(u_Q)=y_Q]= \prod_{i=1}^Q Pr[\mathcal{O}(u_i)=y_i]=\frac{1}{|\mathcal{Y}|^Q} $


Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

Quite applicable; Shor's algorithm treats the group operation as a blackbox, hence it treats an even characteristic curve just like it does a prime curve.
  The only practical difference is the cost differential (in terms of qubits, circuit complexity and depth) between the prime curve and the even characteristic curve addition operations.

  I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.

That's a different question (because GCM/GHASH has a secret symmetric key); in terms of standard CPA and CCA attacks, GCM/GHASH (correctly used) is provably secure as long as you cannot distinguish AES (or whatever underlying block cipher you're using) from a random permutation; allowing the adversary to perform Quantum operations doesn't change that (and so unless he can use his Quantum Computer to break AES, there's nothing he can do).

The one exception is if you go outside that model, and go to a Quantum Oracle model (where the attacker is allowed to request entangled queries and get entangled responses), that's different - it's known that GHASH (that is, the authentication piece in GCM) can be broken fairly easily.  This does show that it is impossible for a white box GCM implementation to be quantum secure; however it is hard to come up with another realistic scenario where this attack is applicable.


Showing the non-pseudorandomness of a generator

This is an attempt to answer my own question based on Squeamish's helpful comments. If terminology is unclear or misleading, please tell me!

Let $D(s) = \mathbb{I}\{s = x||G(x), x \in \{0,1\}^n\}$. Then, if our putative PRG is $G'$, $\Pr[D(G'(s)) = 1] = 1$ - that is, $G'(s)$ is always in the format that $D$ looks for. However, $\Pr[D(r) = 1]$ (where $r$ is uniform from $\{0,1\}^{2n}$) is $\frac{2^n}{2^{2n}}$, to reflect that $s||G(s)$ has a range of only $2^n$ - being completely determined by $s$ - while there are $2^{2n}$ possible values $r$.

Thus $|\Pr[D(G'(s)) = 1] - \Pr[D(r) = 1]| = 1 - \frac{2^n}{2^{2n}}$, a non-negligible function.


Let (P, V) be any ZK protocol, then the protocol is WI. --> help with proof

TL,DR: there's already a quite nice proof sketch in the original paper by Feige and Shamir. Check it out here! If you want to see an intuitive explanation then keep reading!
What does witness indistinguishability mean, intuitively?
Witness indistinguishability (WI): The proof system $(P,V)$ is WI over a relation $R$, if for any instance $x$ the verifier with auxiliary information $y$ cannot distinguish which witness was used in a proof $x\in R$.

Can you define ?

$D$ is a distinguisher that tries to guess which witness was used to generate the proof. Note, that the distinguisher has only access to the proof's transcript and auxiliary information $y$.
What does zero knowledge mean, intuitively?
Zero knowledge (ZK): The proof's transcript $V_{P(w,x)}(x,y)$ and the simulated view $M(x,y;V)$ are indistinguishable.
Theorem (Feige and Shamir): If a proof system $(P,V)$ is zero-knowledge (ZK) then it is also witness indistinguishable (WI).
Proof sketch
If the success probability of distinguisher $D$ is $p$ when witness $w_1$ was used, then by the zero-knowledge property of $(P,V)$ the distinguisher's success probability remains the same, even if it runs on a simulated transcript outputted by $M$, i.e. $M(x,y;V)$, because by the zero-knowledge property we have that the simulator's view $M(x,y;V)$ and the verifier's view $V_{P(x,w_1)}(x,y)$ are indistinguishable. Since the simulator's view is independent from the used witness, therefore we also have that the ensembles $M(x,y;V)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable. By the transitivity of indistinguishability we have that the ensembles $V_{P(x,w_1)}(x,y)$ and $V_{P(x,w_2)}(x,y)$ are indistinguishable, i.e., the protocol $(P,V)$ is WI.
Note, however, that the opposite is not true. There are WI protocols, that are not ZK. An example is taken from here: Assume the existence of a length-preserving one-way permutation $f$ and define the language
$L_0:= \{y |\text{the first bit of } f^{−1}(y)\text{ is } 0 \}$. (Note that every $y\in L_0$ has the unique witness $x = f^{−1}(y)$.) An interactive proof in which the prover sends $f^{−1}(y)$ on common input $y$ is witness indistinguishable (trivially) but not zero knowledge (assuming $f$ is indeed one-way).


If you have a file and XOR every bit with a random bit, can you extract any information?

This cipher is called a one-time pad. It is unbreakable ("perfect secrecy") assuming that:

The pad (the collection of random bits) really is truly random
The pad is never reused to encrypt other messages

So, no information can be extracted from $\text{file} \oplus \text{random bits}$.

The basic idea of the proof is that an attacker can test every possible key, but they have no way of knowing which plaintext is actually correct. If I encrypt "attack" with a one-time pad, then any six-character string could just as equally have been encrypted in the first place.


What is the difference between OTR and Signal protocols?

Check out the blog post by Whisper Systems regarding the triple ratchet of OTR verses the double ratchet of Signal. Also, a prior article about synchronous versus asynchronous messaging is worth the read. Both of those should answer all of your questions.


Constructing a commitment scheme from two (possibly defective) commitment schemes

It's been over a month, and so if this was a homework question, the due data has already passed.

Both Com1 and Com2 satisfy the binding property, and one of them satisfies the hiding property (but you do not know which). In this case I do not think we could create a good commitment scheme.

Sure you can; you just do:
$$Com(m, r_1, r_2, r_3) = Com1( m \oplus r_3, r_1 ) || Com2( r_3, r_2 )$$
If Com1 does not have the hiding property, someone can learn the value $m \oplus r_3$, however if $r_3$ is selected randomly, they learn nothing about $m$.  Similarly, if Com2 does not have the hiding property, they can learn the value of $r_3$; again, they learn nothing about $m$.
The other piece we need to show is that $Com$ also has the binding property; that is straightforward with the assumption that both $Com1$ and $Com2$ do; $Com1( m \oplus r_3, r_1 )$ can be opened only as $m \oplus r_3$, and $Com( r_3, r_2 )$ can be opened only as $r_3$, and the xor of the two will have to be the original committed string $m$.


You appear to be confused by the sentence in the answer:

  If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256).

This sentence is true, but doesn't mean what you think it does.

It doesn't mean that you can't compute inverses in $GF(256)$; instead, what it means is that you can't compute the addition and multiplication as $A + B \bmod 256$ and $A \times B \bmod 256$; other algorithms need to be used.

It happens that addition is easy; you can do it by doing a bitwise exclusive or; in C, that's A ^ B

Multiplication and inverses are a bit trickier; however, I can point you to the answer here that addresses how to do with with a few table lookups


Question about Novotney's paper on Weak Curves

There is obviously missing information on both lecture projects. With a small try, I've found a curve with the required order.
If you set the field as the prime field $F_P$ where $p=9254331510119$, the curve
$$E(F_p) : y^2 = x^3 + 7x + 1$$
p = 9254331510119
E = EllipticCurve(GF(p), [7,1])
print(E.order().factor())

outputs
$$9254332285624 = 2^3 \cdot 19 \cdot 23 \cdot 67 \cdot 2089 \cdot 18913$$ as required.

Actually, I was lucky since I simply started 9254332285624-1000000  and I did not use the Hasse bound
$$|N - (q+1)| \le 2 \sqrt{q}$$ where $N$ is the number of point on the curve, here $N= 9254332285624$, and $q$ is the number of elements of the finite field, here we have the prime field $F_p$. With removing the absolute value we have this form
$$q+1-2{\sqrt q} ≤ N ≤ q+1+2{\sqrt q}$$
$$q+1-2{\sqrt q} ≤ 9254332285624 ≤ q+1+2{\sqrt q}$$
and calculating
$$9254332285625 - 4 \sqrt{2313583071406} \leq q \leq 9254332285625 + 4 \sqrt{2313583071406} $$
$$9254326201438 < q < 9254338369812$$
So, if you seek the primes in the above range ( possibly with a next_prime function of SageMath) you will definitely find your candidate primes, which are expected little ( exactly 407391 primes on this range) to satisfy the required curve order.

The SageMath code with Hasse Bound;
expected_order = 2^3 * 19 * 23 * 67 * 2089 * 18913

#This is specific to this order!
start = floor(expected_order - 4 * sqrt(expected_order/4))
end   = floor(expected_order + 4 * sqrt(expected_order/4))

p = start -1

primeCount = 0

for x  in range(start,end):
    p = p.next_prime()
    primeCount = primeCount + 1
    if p > end:
        break

    E = EllipticCurve(GF(p), [7,1])

    if E.order() == expected_order:
        print ( p)
        break

print("Finished")
print("Number of tested primes =", primeCount)

and the output;
9254331510119
Finished
Number of tested primes = 177222


Simple explanation of Miller's algorithm

Miller's algorithm maps two points in a elliptic curve into a element of a finite field. So, if you have a point $P$ and a point $Q$, then Miller's algorithm (which we'll denote $e$) will compute some value $r \leftarrow e(P, Q)$, where $r$ is a finite field element.

Recall that points can be added (e.g. $T \leftarrow P + Q$) and multiplied by a integer (e.g. $T \leftarrow kP$, which is just repeated addition), while finite field elements can be multiplied (e.g. $t \leftarrow pq$) and raised to the power of an integer (e.g. $t \leftarrow p^k$, which is just repeated multiplication).

The crucial property of Miller's algorithm is bilinearity. Assume that you have points $P$ and $Q$ and integers $a$ and $b$, and compute the points $R \leftarrow aP$ and $S \leftarrow bQ$. Then, if you compute Miller's algorithm for $P$ and $Q$:

$x \leftarrow e(P, Q)$

and for $R$ and $S$:

$y \leftarrow e(R, S) = e(aP, bQ)$,

then these values will be related with:

$y = x^{ab}$.

In other words, bilinearity means that:

$e(aP, bQ) = e(P,Q)^{ab}$.

The bilinearity property allows the construction of cryptographic protocols which were not possible before or too complicated: identity-based cryptography, short signatures, non-interactive key agreement, and so on.


I'll assume the Vigenere cipher is defined to encrypt per $c_i\gets m_i\boxplus k_{(i\bmod l)}$ where $c_i$ is a ciphertext letter, $m_i$ is a plaintext letter, $k_i$ is a key letter, $l$ is the length of the key, $\boxplus$ is the Vigenere table of dimension 26×26. I'll note $\hat k_i=k_{(i\bmod l)}$.

It is assumed
$$\begin{array}{rlcrl}
\Pr[l=1]&=\frac1 2&\quad&\Pr[l=2]&=\frac1 2\\
\Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt a]&=\frac2 5&\quad&\Pr[m_0=\mathtt a\;\wedge\;m_1=\mathtt b]&=\frac3 5
\end{array}$$
It is asked $p=\Pr[c_0=\mathtt b\;\wedge\;c_1=\mathtt b]$. That is
$$p=\frac2 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt b]+\frac3 5\Pr[\hat k_0=\mathtt b\;\wedge\;\hat k_1=\mathtt a]$$

Unfortunately, the problem statement is unclear about the distribution of key. We can reasonably assume that each of the possible $k_0$ has probability $\frac1 {26}$, but what about $k_1$ when $l=2$? It is reasonable to assume one of

Each of the possible $k_1$ has probability $\frac1{26}$. That yields
$$p=\frac2 5\left(\frac1 2\frac1{26}+\frac1 2\frac1{26}\frac1{26}\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{26}\right)=\frac{57}{6760}\approx0.0084$$
(rounding to the nearest, that is down)
Each of the possible $k_1\ne k_0$ has probability $\frac1{25}$. That yields
$$p=\frac2 5\left(\frac1 2\frac1{26}+0\right)+\frac3 5\left(0+\frac1 2\frac1{26}\frac1{25}\right)=\frac{53}{6500}\approx0.0082$$
(rounding to the nearest, that is up)

Note: Bet on 1 to maximize the probability of scoring a correct answer, even though 2 is the less unsafe cryptographically.

The question's attempted resolution has reading 1, but each of the probability that it sums is missing the multiplication by the probability that $l$ has the value considered.


Lightweight primality certificates for untrusted DH parameters

Well, one possibility to generate a moderately lightweight certificate would be to use this theorem:

If we have values $p, q, g$ such that:

$1 < g < p$
$q > \sqrt{p}$
$q \mid p-1$
$g^q \equiv 1 \pmod p$
$q$ is prime

Then $p$ is prime.

So, for a certificate, we would have a list of $(p_i, g_i)$ values such that $p_{i-1}, p_i, g_i$ meet the above conditions (as $p, q, g$), with $p_0$ is the value $p$ we're actually interested in proving, and the final $p_n$ value is a prime small enough to make primality proving trivial (e.g. it may less than 16 bits long).  Each line in the certificate (almost) halves the value of $p_i$, and so the total number of lines is managable.

As for verifying the certificate, it should be fairly obvious, for each line in the certificate, we would check the first four conditions directly, and then step to the next line to verify the last condition; as the last step, you'd do a quick check that $p_n$ is prime.  The expensive part is the $g^q \equiv 1$ condition; if you total it, it's a bit less than a single Miller-Rabin computation (but has the advantage that it is deterministic; if it validates, there is no need to do a second iteration).  Whether this counts as 'significantly less' is something you'll need to decide.

As for generating the certificate, you can't select a random $p$ and try to generate the certificate.  Instead, you would create the certificate (and the prime) from the bottom-up; select a $p_n$, and then at each step, given $p_i$, you would search for a prime value $p_{i-1}$ (and $g_i$, but that's easy), eventually ending up with a $p_0$ value of the desired size.  The FIPS 186-4 Shawe-Taylor algorithm does exactly this (you'll just need to record the intermediate $p_i, g_i$ values).

As a side effect, $g_1$ is an appropriate generator for the DH group (as it generates a large prime-sized subgroup).

On the other hand, I would second Future Security's suggestion to the ECDH instead; that uses less resources, and doesn't have any known 'solve this problem and break the entire group' attacks


Does the ability to influence the key of a MAC effects its security?

If a PPT adversary can influence the key of a MAC function, is it still secure?

In general probably no if you make no restrictions on the ways the key can be influenced. In particular the answer is "no" when you rely on your MAC actually being a PRF for your security proof (like HMAC does). This means that if your MAC relies on this then you need some additional argument for related-key security, as PRFs cannot be secure against all classes of related-keys. For a proof and more background on this see Proposition 8.4 of the original paper that introduced this (PDF).

  If the adversary has oracle access to $f$, how likely he can predict the key $k$?

Cryptography isn't about "can you predict the key" because you can usually build schemes that don't use their key-input and are thereby trivially secure if all you want is the key.

A more interesting question would be, if an attacker has access to (this concrete) $f$, how easy is it to forge tags? This has in fact been studied for HMAC and keys related by a constant leading to an attack that runs in time $2^{n/2}$ with $n$ being the HMAC's output length.


Creating hash data signatures using RSA-CRT

The question's formula dP= d^-1 mod (p-1) is in error. Rather, $d_P=d\bmod(p-1)$, or more directly $d_P=e^{-1}\bmod(p-1)$, which makes it unnecessary to compute $d$. Same for $d_Q$. See this answer for proof of the formulas.
Use of CRT in RSA is an alternative computation modality for the transformation¹ $x\mapsto x^d\bmod n$. The conditions for the choice of $p$, $q$, $e$ remain unchanged. They depend on reference. Something common for theoretical work would be some small $e\ge3$, and $p$ and $q$ distinct large random primes such that $\gcd(e,p-1)=1=\gcd(e,q-1)$ and of about the same bit size.

Note: the question's computation is an illustration with small parameters of one of the steps of actual digital signature with RSA. But

The primes used are way too small for security. Actual RSA keys use primes $p$ and $q$ with hundreds of decimal digits, so that the public modulus $n=p\,q$ is hard to factor.
In an actual RSA digital signature, the input of the private key function is not the message. Rather, the message (an arbitrarily large piece of data) is hashed and padded to form the input of the $x\mapsto x^d\bmod n$ transformation.

¹ That private-key transformation is the inverse of the public-key transformation $y\mapsto y^e\bmod n$ when $n=p\,q$ and $e\,d\equiv1\pmod{\lambda(n)}$ or $e\,d\equiv1\pmod{\varphi(n)}$. These transformations are over the set $\Bbb Z_n$ or $\Bbb Z_n^*$. That depends on reference.


There are several kinds of quantum key distribution (QKD) protocols as of today. Are you looking for a particular one?
The best-known QKD protocol goes by the name BB84 after its inventors Bennett and Brassard and the year in which they presented their work. Searching on the Internet, I found this link http://fredhenle.net/bb84/demo.php with a simulation that looks fairly nice and introductory.
As such, programming (at least) an ideal version of the BB84 protocol is not difficult. By ideal, I mean that Alice's source, Bob's receiver are perfect, and the channel is not only without Eve but also does not absorb or distort the information carriers (in case you do not have any background in quantum physics, you could also read section 2 of this paper http://arxiv.org/abs/1206.7019 that serves to explain the operation of BB84 to even non-scientists).
Otherwise, with the following steps you can simulate BB84 on your own:

Generate two random bit-sequences of length 2N and N for Alice and Bob, respectively. At the end of the protocol, Alice and Bob would share a symmetric and secret key of length n $\approx$ N/2 distilled from these bit sequences. The next 3 steps can be assumed to operate in a loop from 1 to N.

Alice uses 2 bits at a time to generate one of four quantum states denoted by Q and having the values H, V, D, A randomly (use the mapping H=00, V=01, D=10, A=11 for the BB84 protocol).

A state prepared by Alice arrives in Bob as it is, i.e., without being subjected to loss or noise.

Bob uses his bits to choose the basis B randomly, i.e., B=0=HV basis or B=1=DA basis with equal probability. Now comes the only piece of logic you need to understand. In a given instance, assume Bob's chosen basis shares a non-empty string with Alice's chosen state, e.g., Q=D and B=DA (this technically means they used the same basis). In such an instance, Bob's outcome, or the bit obtained by him due to the measurement on the quantum state, is deterministic and equal to the 2nd bit of Alice (which would be 1 in this case). On the other hand, if the basis does not match, e.g., Q=V and B=DA again, Bob's outcome could be either 0 or 1.

After Bob has finished measuring all N states, he publicly reveals his basis choice but not the outcomes he obtained. Alice applies the same logic as in the previous step -- she examines all N instances to locate those where her basis matched with that of Bob. She then informs Bob to keep these outcomes only in such instances while choosing the corresponding bits from her bit-sequence. This is the secret key.


Why is EdDSA collision-resilient with SHA-512?

The relevant part of Neven et al is this:

  What this means for practice is that one should not instantiate the hash function with a Merkle-Damgård iteration of an $n$-bit compression function. Instead, one should probably simply truncate the output of a $2n$-bit hash function to $n$ bits. (Such a method would in our situation be reminiscent of Lucks’ wide-pipe hash [Luc05].) Therefore, using for example the first 128 bits of the SHA-256 hash should in practice provide a security level of 128 bits.

Ed25519 uses SHA-512, a 512-bit hash function. If the herding attack applies but the hash function itself is secure, its security level should be at least about 256 bits (the collision resistance of the hash function). That is way more than the security of the overall algorithm and so not relevant here.

Even if some collision attack on the ~256-bit number that results from the multiplication (after reduction modulo $l$) would allow breaking the signature scheme, that would still not break the claimed ~128-bit security level.

I.e. rather than running into problems due to using a half length Merkle–Damgård hash, Ed25519 uses a conservative double length hash and should not be affected.


How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions?

So this feels like a homework question, as such I"m not going to give you the full answer, but yes, yes you can.  https://en.wikipedia.org/wiki/Homomorphic_encryption#Unpadded_RSA
Is the best starting point I can give without giving away the barn, but essentially rsa is homomorphic, and you can exploit that and repeated calls to the oracle to do what you want.


Cube attack is the name given by Itai Dinur and Adi Shamir to a general attack on cryptographic schemes considered as multivariate polynomial equations, in their paper Cube Attacks on Tweakable Black Box Polynomials (in proceedings of EuroCrypt 2009). The origin and applicability of the attack has been challenged by Daniel Bernstein.

The attack aims at key recovery from plaintext/ciphertext pairs, with chosen plaintext. It is applicable to encryption and MACs using vulnerable block or stream ciphers.

For example, if one used a modified Trivium with only 767 initialization rounds instead of the prescribed 1152, the key could be recovered under a chosen-plaintext attack; that would compromise confidentiality and integrity of messages protected by that same key.

Thus, 1/3/5 in the question apply to some degree, for that modified Trivium.

It seems that 2/4/6 in the question do not apply (I'm reading 6 as trying to break encryption under known plaintext).

Addition following comment: In good practice, neither of 1/2/3/4/5/6 apply. A standard cipher design criteria has been (for over 20 years) to avoid the conditions that allow higher-order differential cryptanalysis to work; modern ciphers that survived analysis by competent cryptographers are thus practically immune to the cube attack (including AES in all key sizes and standard modes). As an aside, the cube attack requires chosen plaintext, thus typically does not apply if all that gets encrypted using a key is chosen by legitimate holders of that key, which seems to be the hypothesis made here.


PKCS #1v1.5 signatures are basically signed hashes. Therefore, it is possible to extract hash and applied hash algorithm (in ASN.1 DigestInfo format) from properly signed signature.

In some old terminology, this operation may have been referred to as "encryption with private key". However, this terminology should be deprecated as the private key operation does not provide security you would expect from encryption (confidentiality) but instead it allows to ensure that signing has been made with private key matching public key used in verification (authenticity).

See RFC 3447 / PKCS #1 v2.1 for new version of PKCS standard. It calls the underlying signature primitive RSASP1.

Quoting that document:

  The main mathematical operation in each primitive is exponentiation,
  as in the encryption and decryption primitives of Section 5.1. RSASP1
  and RSAVP1 are the same as RSADP and RSAEP except for the names of
  their input and output arguments; they are distinguished as they are
  intended for different purposes.


Using bad generator in ElGamal Encryption

The attacker can distinguish $\langle C_1, C_2 \rangle$ from a random pair if the attacker knows a value $q < p-1$ such that $g^q = 1 \mod p$.

Here's how the distinguisher would work: he simply computes $C_1 ^ q$ and checks to see if that value is 1.  If this $C_1$ corresponds to a valid ciphertext, then that value will always be 1.  If this $C_1$ is part of a random pair, then the value will be 1 with probability $q/(p-1) \le 1/2$ (remember, $q$ will always be a divisor of $p-1$).

On the other hand, just because we show distinguishability against a particular random source doesn't mean that we have shown that it is insecure.  In this case, that would depend on what is the order of $g$ (and whether it is "smooth", that is, has no large prime factors).  If the order of $g$ is smooth, then solving the discrete log problem is easy, and hence the system is insecure.  On the other hand, if the order of $g$ has a large prime factor $q$, I believe that it is still safe.


Is there a need to encrypt data when send over https?

Maybe, but it would not be practical for widespread consumer use.

In order for this extra encryption to be effective against man-in-the-middle attacks, the client and server would already have had to agreed upon a pre shared secret out of band.


Are there comprehensive alternatives to RSA?

Yes.

You can use RSA for both signatures and encryption, but you need different algorithms for that. E.g. RSAES-OAEP is an encryption algorithm, while RSASS-PSS is a signature algorithm. Both use the RSA cryptosystem and have similar keys, but otherwise the algorithms differ. Textbook RSA has the "same" algorithm for both but is not secure.

There are alternatives where something similar is possible. Elliptic curves are the most practical and widely used option. The same curve can be used for encryption (e.g. ECIES) and signatures (e.g. ECDSA).

Note that using the same key-pair for both encryption and signatures is not necessarily secure, even if the algorithms allow it. So in practice you could use completely different algorithms for signatures and encryption without too much overhead, but you may save e.g. code size by using related algorithms for both. And you may rely on fewer hardness assumptions that way.


What does the symbol $W_t$ mean in the SHA-256 specification?

It is in SHA-256 message schedule (NIST-FIPS 180-4);

The message $M$ with length $l$ is first padded as the usual way;

append 1 to the end of the message,
then, add $k$ zero bits such that $$l+1+k \equiv 448 \mod 512$$
finally, add the length of the message in 64-bit. Now, the total padded length is divisible by 512.

After padding, the padded message parsed into $M^{1},\ldots,M^{N}$ where each has size 512-bit.

The sub index $t$ represents 32-bits in 512 bits. Thus, The $M_t^{(i)}$ is the $t$-th 32-bit in the $M^{(i)}$ for $0 \leq t \leq 15$

The $W_t$ is defined as your equation;

$$W_t = \begin{cases}
M_t^{(i)} & 0 \leq t \leq 15 \\
&\\
\sigma_1^{256}(W_{t-2}) + W_{t-7} + \sigma_0^{256}(W_{t-15}) + W_{t-16} & 16 \leq t \leq 63
\end{cases}$$

Where
$$\sigma_1^{256}(x) = \operatorname{ROTR}^{17}(x) \oplus  \operatorname{ROTR}^{19}(x) \oplus  \operatorname{SHR^{10}(x)}$$
$$\sigma_0^{256}(x) = \operatorname{ROTR}^{7}(x) \oplus  \operatorname{ROTR}^{18}(x) \oplus  \operatorname{SHR^{3}(x)}$$

$\sigma_1^{256}(x)$ and $\sigma_0^{256}(x)$ operate on 32 bits and produce 32 bits.

Note: the 256 above the $\sigma$ represents the 256 in SHA-256. Similarly, there is $\sigma_0^{512}(x)$ and $\sigma_1^{512}(x)$ for SHA-512.


Encrypt symmetric session key with asymmetric or symmetric master key?

Symmetric cryptography could well work here, to be honest.

The main advantage of public cryptography in this setting is that you can encrypt by just using a public key. So you'd get the following operations:

Setup:

create public / private key pair;
encrypt private key with password.

Encryption:

create random session key;
encrypt session key using public key;
encrypt data with session key and random nonce.

For decryption:

decrypt password-encrypted private key;
decrypt session key using private key;
decrypt data with session key using random nonce.

In other words, during encryption you  don't need access to the private key and therefore you don't need a password either. You just need to make sure that you don't leak your temporary session key.

This seems to be particularly useful for backups where backing up is frequent and commonly automated, while the restoration is commonly manual and infrequent.

Notes:

the private key may also be otherwise protected, e.g. stored on a USB-stick or generated within a smart card (exporting the public key after key pair generation);
instead of deriving a key per session you might also want to generate a symmetric key per file - beware that some modes such as GCM have clear restrictions about the amount of data that can be processed by one key;
restoration is often too infrequent, don't forget to test your restoration initially and frequently thereafter.


Can ChaCha be turned into a collision resistant hash function by xoring keystreams?

The only expectation for each $c_i[m_i]$ is that it's independent and uniformly random. ChaCha20, with the nonce/counter words acting as table index is perfectly fine here, under standard assumptions about ChaCha20. Furthermore, the $m_i$ are expected to be small—in RFSB, they are 8-bit wide—so you can put the message in the counter just as well.

As an example of using a larger message as input to each function, you may also look at Rumba20, $$\text{Rumba20}(x_1, x_2, x_3, x_4) = f_1(x_1) \oplus f_2(x_2) \oplus f_3(x_3) \oplus f_4(x_4)\,,$$ which instead uses different constants to differentiate between the 4 different input blocks, and uses 384 bits of each Salsa20 block as input.

Note that if you let the number of xors ($w$ in the RFSB paper) grow too much relatively to the output size ($r$), the compression function can become weak. This is discussed at length in Section 4.

Note also that either of these compression functions only attempt to be collision-resistant. Other properties, such as preimage resistance, need to be ensured by some other mechanism, as the papers stress.


Can you explain the counter in the Key derivation function of PACE?

The counter is used to distinguish the different (session) keys used in the protocols. A relatively standard KDF is used, KDF2. Note that only a single iteration is needed and that no OtherInfo has been defined, so the specification of KDF2 may look more complex than it is in the PACE protocol. A 32 bit counter is of course overkill for the protocol, but that's just how the counter has been defined.

So you have the counter valued 1, encoded as 00000001 in hexadecimals as input for the encryption key, and a counter valued 2, encoded as 00000002 for the MAC key.

Some of this is explained in the very first sentence of A.2.3, page 33 (the definitions of KDFMAC and KDFENC).

Note that this counter is entirely different from the Send Sequence Counter used within the secure messaging protocol. That counter is either 64 or 128 bits in size.