From Wikipedia:

  In mathematics and computing universal hashing (in a randomized
  algorithm or data structure) refers to selecting a hash function at
  random from a family of hash functions with a certain mathematical
  property. This guarantees a low number of collisions in expectation,
  even if the data is chosen by an adversary. Many universal families
  are known (for hashing integers, vectors, strings), and their
  evaluation is often very efficient. Universal hashing has numerous
  uses in computer science, for example in implementations of hash
  tables, randomized algorithms, and cryptography.

Definition:
A randomized algorithm $H$ for constructing hash functions $h\colon U \to \{1,\ldots,M\}$
is universal if for all $x \neq y$ in $U$, we have
$\Pr_{h\gets H} [h(x) = h(y)] \leq 1/M$

From this answer:

  Let $\Phi$ be a finite collection of hash functions that map a given
  universe $U$ of keys into the range $\{0, 1, 2,\ldots, m - 1\}.$

  $\Phi$ is called universal if for each pair of distinct keys
  $x, y \in U$, the number of hash functions $h \in\Phi$ for which
  $h(x) = h(y)$ is precisely equal to $$\frac{\lvert\Phi\rvert}{m}.$$

  With a function randomly chosen from $\Phi$, the chance of a
  collision between $x$ and $y$ where $x \neq y$ is exactly
  $\frac{1}{m}$.


How do we arrive to the equation for solving D in RSA?

Are you asking "given $e$ and $\phi(n)$, how do we find $d$ such that $de \equiv 1 \bmod \phi(n)$"? (which can also be written as $d = e^{-1} \bmod \phi(n)$

The standard way of find such a value is the Extended Euclidean Method; this is a relatively efficient method that results in $d$ given $e$ and $\phi(n)$ as inputs (assuming, of course, that $e$ and $\phi(n)$ are relatively prime; if they aren't, $e$ won't work as a public exponent anyways).

Now,I do have one minor nit which doesn't have anything to do with your actual question: actually, if $d$ and $e$ are RSA private/public exponents, it's not always true that $de \equiv 1 \bmod \phi(n)$.  Now, such a $d$ and $e$ that satisfies that condition will work as RSA private/public exponents (and hence if you are constructing an RSA private/public keypair, using $\phi(n)$ won't break anything).

However it turns out that the weaker condition $de \equiv 1 \bmod \lambda(n)$ where $\lambda(n) = lcm(p-1, q-1)$ turns out to be both necessary and sufficient.  This does not affect your question (because you end up giving $e$ and $\lambda(n)$ to the Extended Euclidean Method). You did mention that you were studying RSA; you should be aware of that.


Maybe you should read up on solving congruences modulo composite moduli like $26$.
There are some examples here, or slightly easier here etc.

Note that A,E,H,X correspond to the integers $0,4,7,23$ respectively.
Suppose that $c(x) = ax + b$ where $x$ is the plain letter and $c(x)$ the corresponding encryption, $a,b \in \mathbb{Z}_{26}$.

If we assume $A \to X, E \to H$, we get the equations (for $a,b$, using $x=0,4$):

$$
\begin{align}
c(0) =& 23 \equiv a\cdot 0 + b \bmod{26}\\
c(4) =& 7 \equiv a \cdot 4 + b
\end{align}
$$

which gives $b = 23$ and $4a + 23  \equiv 7 \bmod{26}$, or $4a \equiv -16 \equiv 10 \bmod{26}$.

This last equation has two solutions as $\gcd(4,26) = 2 | 10$, and we find they are $a=9$ and $a=22$. Only $a=9$ has an inverse modulo $26$ namely $3$ ($3\cdot 9 = 27 = 26 + 1$). You can then find the decryption formula and try other letters to check whether the assumption $A \to X, E \to H$ was correct.

If however you'd assume $A \to H, E \to X$ we'd have gotten the equations:

$$
\begin{align}
c(0) =& 7 \equiv a\cdot 0 + b \bmod{26}\\
c(4) =& 23 \equiv a \cdot 4 + b
\end{align}
$$

which gives $b=7$, and $4a \equiv 16 \bmod{26}$ and this last equation has two solutions again: $a=4$ and $a=17$, of which only $a=17$ is a potential candidate as it has an inverse in $\mathbb{Z}_{26}$ of $23$. So again compute the decryption formula for this case to check this hypothesis on other letters as well.

Note that if there is at least $1$ solution to $4a = x$ modulo $26$ it has $2$ that differ by $13$, corresponding to the theory I referred to. So you either have $0$ or $2$ solutions to such linear equations in one variable. This is why you're better off working over prime fields (add a space as an extra character and some more to work module $29$ or $31$ or some such idea).


Lyra2 sponge construction and random numbers?

From what I can tell, you've found the salt input to modern password hashing schemes which indeed accepts random numbers to hash the same password to different results on distinct invokations.

Now the idea of the salt is indeed to prevent the dictionary attacks you envisioned (if you keep the salt secret, in which case it becomes pepper) or at least force you to go throgh your entire dictionary for every single salt you encounter, which will take time and slow you down in breaking large databases of passwords. However, normally, all parameters for password hashes are specified (including the salt) and as such it is an entirely deterministic computation from the password and the stored parameters to verify the stored password hash.

Finally, yes: It's impossible to directly recover the password (or a valid password) from its hash as then the function would have failed its most important role which is to make it hard to recover the password.


What is the definition of a Linear Cipher

A linear cipher is a cipher that all of its inner operations (diffusion and confusion operations) have the mathematical linear property. Linear property in mathematics is defined in such a way: f(a+b) = f(a) + f(b). But what does it mean in origin? It means that if we think a cipher like a magic box, then if we give this magic box the sum of two quantities, then in the output of this magic box we can distinguish these two quantities. But how does it relate to cipher security? This linearity property causes the transformation of any inputs properties to output properties. For example, think about one of these properties can be the odd or even of inputs. Then, if the input data to the cipher are all even, then all of the output data be even, too. As we told, every cipher operates with two operations. Each of these operations is defined with mathematical functions: Substitution function that makes the confusion property and Permutation Function that makes diffusion property. Permutation functions are originally linear or affine functions(affine function: linear function + constant value). The only part of cipher that should be non-linear is confusion parts. For example SBoxes. And choosing a good SBox that has the high nonlinearity property is very important. So if we can change a cipher to a linear or affine form(by some technics of cryptanalysis like Linear cryptanalysis), we can change the cipher to some linear equations and by solving these equations, we can extract the Key.


Why are the factors p and q (for n) secret in Fiat-Shamir Authentication?

Knowledge of $p$ and $q$ makes computing square roots modulo $n=pq$ easy.

Using the Tonelli-Shanks algorithm, one may determine square roots modulo $p$ and $q$ individually and then combine them to a square root modulo $n$ using the Chinese remainder theorem.

Therefore, anyone who knows $p$ and $q$ can compute the prover's private key (which is a square root of the public key) to impersonate them.


Correlation of an approximation over a random permutation

So $x$ measures the departure from balance in the left half of the truth table, say it is the excess number of 1's in the left half of length $2^{n-1}$. By the definition of binomial coefficients there are $$\binom{2^{n-1}}{2^{n-2}+x}$$ such vectors. This is the first factor. The second factor is the count of vectors missing $x$ 1's, since the overall truth table is balanced.

Using $$\binom{a}{b}=\binom{a}{a-b}$$ completes the argument.


We know that $b$ is 256-bit number with
$$2^d - 1 = b\cdot s$$ and
$$z \equiv s \pmod{2^{128}}$$ use the modulo knowledge
$$z = s + k\cdot 2^{128}$$ for some $k \in \mathbb{Z}$ then
$$s = z - k\cdot 2^{128}$$ combine
$$2^d - 1 = b\cdot (z - k\cdot 2^{128})$$
$$2^d - 1 = b\cdot z - b \cdot k\cdot 2^{128}$$
take modulo $2^{128}$
$$ -1 \equiv b\cdot z  \pmod{2^{128}}$$
Therefore we learned 128-bit information about $s$ with simple arithmetic. It is not a good way to hide the private key.


Randomness Testing of Cryptographic Algorithim

One of the features of a good encryption is that the cipher text should be indistinguishable from pseudo random. That means that it'll look like output from a good random number generator. Since there are only 256 possible values for any byte, of course they will repeat if you've got 300 million of them.

Repeats tend to occur at the rate of $1 \over 256^n$ where $n$ is the number of bytes within the tuple you're looking for. So you'd expect $L \over 256^n$ number of $n$ length tuples in a randomish file of length $L$.  For example, {6, 6, 6} should occur ~18 times.

  Is there any safe threshold in which there shouldn't be any repetition?

From the above, you must have repetitions otherwise the cipher text wouldn't be very good and it would in no way resemble random.  {6, 6, 6} may not have occurred 18 times (check for yourself with a hex editor).  It may have occurred 20 times. That's random again, and it can vary within expected (but squidgy) bounds.

We can obtain the probability $P$ of a certain sequence occurrence randomly via a chi-squared test. We would view the cipher text as suspicious if $P < 0.01$.  There's a more grown up example of looking for repeat sequences in section 2.7 of NIST's A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. The example there looks for "000000001", resulting in $P$ = 0.344154, which is a pass.

Consider though that this only tests the computational indistinguishability of the cipher text.  We've expect that to be virtually perfect if you've used the correct algorithms/library.  It can't test the inherent security aspects of say, constantly reusing an IV.


ECKS-PS algorithm: searching in encrypted data; bilinear maps


Need help understanding math behind Rijndael S-Box

The code is using the fact that the Rijndael's* Galois field has the following generators†:

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

A multiplicative generator $g$ means that $\langle g \rangle$ generates all of the element of $\operatorname{GF}(2^8) \text{ - } \{0\}$ or equivalently, $\mathbb{F}_{2^8}^*$. More formally, they form the cyclic multiplicative group of the finite field. The zero case handled at the end.
The choice of 3 in the code
/* multiply p by 3 */
p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0);

is simply due to the optimization that 3 enables the smallest calculations to generate all of the elements. The 3 is actually a numerical expression of $x+1 \in \operatorname{GF}(2^8)$ in polynomial representation. Therefore, the above code is the multiplication of the current $p$ with $x+1$ as p ^ (p << 1). The ^ (p & 0x80 ? 0x1B : 0) part is the reduction with the primitive polynomial of the field by the equality $x^8 = x^4 + x^3 + x + 1$, in hex 0x1B where $x^8 + x^4 + x^3 + x + 1$ is the irreducable AES polynomial to that used to extend $\operatorname{GF}(2)$ to $\operatorname{GF}(2^8)$
The code is also using the fact that ;
$$1 = pq=pq \cdot 3 \cdot 3^{−1}=3p \cdot 3^{−1}q=1$$ now call $p′=3p$ and $q′ = 3^{−1}q$ and get $p′q′=1$. In this way, $p$ and $q$ get all valus of the table - expect 0 - since 3 is a generator. Then, by using the $q$, the affine transformation is computed for the table.
What is the advantage here?

No need to find the inverse by using the Ext-GCD or its better versions.
No multiplication is used for generating the elements.

* Rijndael $\neq$ AES (Actually, Rijndael $\supseteq$ AES). Rijndael is an AES candidate that won the competition and standardized as AES. The Rijndael is designed for  128, 192, or 256  key and block sizes. The AES has fixed block size 128 and have the  128, 192, or 256 bits key sizes.
† SageMath code to find all of those generators. Need sorting.
R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = GF(2^8, modulus=x^8+x^4+x^3+x+1, repr='int')

for i,x in enumerate(S):
    if x == 0:
        continue
    if x.multiplicative_order() == 255:
        print("{} {}".format(i, x))


What is the verification algorithm for verifying RSA signatures?

I finally found an answer to this.  A simple formula to verify the signature is: $M = S^e \pmod N$.

If I take the numbers in my original post and plug them into that formula, I get $M = 4C61756E63682061206D697373696C652E$.

Then, if I use the python command below to convert the hex string back to ASCII, print("4C61756E63682061206D697373696C652E".decode("hex"))

I get "Launch a missile", which is the same as the original message.  This means I can verify the signature was correct.


How to turn adversary against encryption of zeroes into adversary against random bits?

It's actually quite simple.
Given your adversary $A$ against ind you construct an adversary $A'$ against ind$ by simply forwarding the queries and answers. (This may seem stupid but please bear with me.)

Consider now, the difference between the advantage of $A$ and $A'$:
$$\mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1]-(\mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1])$$
$$= \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1]$$

If this distance were non-negligible, we could build a successful adversary $A''$ against ind$\mathrm{$}$ as follows: Whenever $A$ queries a message, $A''$ queries $0^{|\cdot|}$ instead and returns the answer to $A$.

It's easy to see that the advantage of $A''$ is excactly the difference from above. Therefore you get $$\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}}  - \mathbf{Adv}_{\Pi}^{\mathrm{ind$}}$$
$$\Rightarrow 2\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$
$$\Rightarrow\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \frac{1}{2}\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$


Why is it secure to reuse key and nonce in ChaCha20-Poly1305 AEAD construction?

Actually, by your own criterion, the same nonce is routinely used much more than twice, because each call to the ChaCha20 core function reuses the same key and nonce, except with a different counter value.

Here's the problem that's tripping you up: the prohibition on using the same key/nonce pair to encrypt more than one message applies to the construction's callers, not the construction's internals. The implied tension you're reading between the external requirement and the internal details just isn't real.

But, internally, the fact that each call to the core function within an invidual encryption operation uses a different counter value is relevant here.


Why are modes of operation used, what attacks do they prevent?

Block ciphers map bit strings of fixed length to other bit strings of the same length. Hence, using only the block cipher primitive, you can't encrypt more than one block (typically 16 bytes), which is of course undesirable.
The straight-forward (but bad!) way around this limitation would be to split up the message into chunks of block length and individually encrypt those: this is exactly the description of electronic code book mode (ECB), which is easily seen to be broken under modern security requirements (specifically, it fails indistinguishability under a chosen-plaintext attack since equal plaintext blocks map to equal ciphertext blocks).
Hence, other constructions suggest themselves. A good block cipher mode should fulfill at least the following requirements:

Each block must be encrypted in a different way. Since we want to reuse the same encryption function every time, the variation needs to be introduced somewhere else: For instance, cipher block chaining incorporates the preceding ciphertext block (which is pseudorandom if the cipher is secure) to mask each plaintext block, hence each $\mathit{block}$ is encrypted using the slightly modified cipher $\mathit{block}\mapsto F_k(\mathit{prev\_block}\oplus\mathit{block})$, thus satisfying the requirement.
Note that in CBC, the first block has no $\mathit{prev\_block}$, hence we need to substitute something else for it — this is what is known as an initialization vector (IV). One might be tempted to just use some fixed value, like $0$, but this is bad: The first block is not masked, hence an attacker can detect if two messages' prefixes are equal by comparing their corresponding ciphertexts' first blocks. This breaks indistinguishability under a chosen-plaintext attack (for multiple encryptions).

Encryption must be nondeterministic due to the problem described in the previous paragraph. The easiest way to achieve this for CBC is to just plug in some random value for the IV and transmit it alongside the message. Just like the pseudorandom ciphertext blocks, the randomized IV masks the first plaintext block (and therefore all subsequent since each block depends on its predecessor), hence it hides equal messages and effectively avoids the problems that a fixed IV has.

(Note that while the example describes CBC, about the same arguments could be made for any other block cipher mode.)


Does having a hash of a password jeopardize the security of plaintext that was encrypted with that password?

As usual in password-based cryptography, we'll consider that the password was chosen from a relatively small set, small enough that password enumeration by an adversary can generate passwords including the one of a target user with fair probability, but large enough that additionally computing the (purposely slow) password hash for each password enumerated is too costly for the attacker.

Three cases must be distinguished.

If the password hash is directly the key of an encryption algorithm, having that password hash is having the encryption algorithm's key, and the security is compromised.
If the password (rather than its hash) is directly the key of a fast encryption algorithm, then the security is jeopardized by that, not by the disclosure of the password hash. Problem is, an adversary can enumerate passwords and test each to find the right key, under the standard assumption of availability of a suitable plaintext/ciphertext pair, or just ciphertext if plaintext is redundant.
If the password is processed thru a purposely slow password-to-key derivation function, either different from the one used for the password hash, or the same parametrized for independent results given the same password, then the encryption system is not compromised by the disclosure of the password hash, under the "large enough" hypothesis in preamble, which implies in practice that the password hash is quite slow, and [passwords are imposed to users, or [users are motivated to not have their password guessed, and neither lazy nor stupid]].

(There could in theory be something intermediary between 1 and 3, where the password hash gives a little usable info about the key; but that's unlikely. The closest is that, in a nightmare scenario, the only difference between the password hash and the key is more iterations for the later, and somewhat re-hashing the password hash gives the cipher's key; but neither PBKDF2, nor anything I have studied, has such weakness).

In conclusion:

Try hard to not let the password hashes leak: password hashing should be a second line of defense.
Make the results of the password-to-key derivation function and password-to-password-hash function independent (in the sense that one can't be efficiently found from the other). One way that works for most purposely-slow key-or-password derivation functions is to use a different salt, or different prefixes to the same salt (empty being a valid prefix).
Especially if you must use password-based encryption, take the password-to-key derivation seriously: use a memory-hard construction such as Argon2 or scrypt, and parametrize generously.

Addition per comment:

  Are there techniques to use password based encryption but at the same time, have confidence in 128 bit security ?

The best we have combines

Sensitizing users to the choice of good passwords, perhaps starting with calling these "passphrase" instead. That simple and unobtrusive thing has gone miles in PGP.
Using Argon2 or other well-thought memory-hard iterated hash to transform password into key, before using it for standard encryption. Merely using a hash requiring sizable memory makes attack using GPUs, FPGAs and ASICs decimal orders of magnitude less attractive than they are to well-funded attackers targeting users of a plain iterated hash like PBKDF2. Password cracking is commonly assisted by GPUs, sometime by FPGAs. I have no hard evidence for ASICs, but technology and greedy mentality in cryptocurrencies are perfect fit.

See this for an exploratory idea: in addition to the above, with a lot of ifs, a memory-hard all-or-nothing transformation of plaintext to ciphertext could force the adversary to decipher the whole file (or a sizable part of the start) in order to test a password. This could be useful to a degree for files of large but still common size.

Regarding the memory-hard iterated hashes: there are iteration, memory, and parallelism parameters to choose.

When we double the iterations (e.g. increase the user-perceived delay from 4 to 8 seconds),

Attackers are hit by a double of energy cost, and of time at constant investment.
Legitimate users also are hit by a sizable increase in energy cost/battery drain, beyond the delay. Thus that adds next to 1 bit of cryptanalytic resistance, but is a pain.

When we double the memory (e.g. from 4 to 8 GiB), and that whole memory can be put to use within the delay, and a number of plausible assumptions hold, then

Attackers using specialized hardware are hit by a double of the time at constant RAM cost, and a RAM cost increase at constant time to a possibly lesser but still sizable degree.
Legitimate users gain some sizable fraction of a bit of key, quite painlessly until they hit the limits of available memory.

When we double the number of CPUs used, which is possible to small (but increasing) degree, this has a chance of decreasing the user delay to some degree, and shouldn't harm much more than making the machine less responsive for other tacks, and noisier/hotter. Thus that can allow raising the iteration count, see 1. Also, for small delay, that may allow to increase the amount of memory actually used, see 2.

I wish I could rationally tell how better it is to use Argon2d vs directly using (a very fast hash of) the password in AES-128. But can't. Using hypothesis so wild that I won't state them, I get anywhere from +20 to +50 bits. One thing is sure: that can't stretch anywhere near to true 128-bit-ness most passwords chosen by a large sample of computer users.

  Is it time to move on to ECIES ?

It does not solve that issue. Any good public-key encryption scheme solves the problem of confidentiality in key distribution, but not the problem of integrity in key distribution. And go figure how to use public-key to authenticate a human to a machine.


Are there lower bounds to how efficient one can make obfuscated code?

tl;dr-  No, in a general model, there's no lower bound except simply that $\alpha \ge 0.$   The easiest way to see this is to consider the fact that, in the general case, the property of one program being an obfuscation of another implies that the first program is also an obfuscation of the second.  Likewise, two differently generated obfuscations of the same programs are also obfuscations of each other.

To get a more practical bound $\alpha$ for use in real-world analysis, a more restrictive model for allowed programs and computers would have to be adopted, as the general case doesn't offer any such bound.

Proof that obfuscation doesn't imply a performance hit in the general case

An obfuscated program can be arbitrarily more efficient than a non-obfuscated one, i.e. $\alpha \to 0 .$

The quick proof is to consider the symmetry of obfuscation.  For example, consider a family of mutually indistinguishable obfuscations of the same program, e.g.$$
C_{i+1}~=~\mathcal{O}\left(C_i\right) \,. {}^{\phantom{-1}}
{\rlap{\qquad \forall i \in \mathbb{N}}}
\tag{1}
$$Now we've got an infinite set of programs that're mutually indistinguishable; and, assuming that $\mathcal{O}\left(\phantom{C}\right)$ tends to cause a hit in performance, then the performance of an obfuscated program $C_i$ becomes arbitrarily poor as $i \to \infty .$

We can then redescribe this family as$$
C_{i}~=~\mathcal{O}^{-1}\left(C_{i+1}\right) \, ,
{\rlap{\qquad \forall i \in \mathbb{N}}}
\tag{2}
$$where we're basically flipping which programs we describe as obfuscations of the others.

While that symmetry argument's probably the easiest, we can also note that obfuscation can include a robust optimization step or something to get $\alpha$ down.

So, in short, no, there's no practical lower bound for $\alpha$ beyond $0$ in the general case.  If you're interested in finding practical bounds for $\alpha$ for use in real-world scenarios, then special-case models will need to be assumed rather than the general case.

Pedantic:  Obfuscation could cause a program to be instant

Consider a program

DoHaltingProblem();
Print("Done!");

If an obfuscator can prove that the halting problem doesn't halt (noting that the issue of halting is incomplete, such that the property of being a halting problem is observer-subjective), then it knows that Print("Done!"); will never execute, allowing it to produce an empty-program

// Literally no instructions to perform

that an observer that perceives the program as containing a halting problem can't knowingly determine to be equivalent.  Then, technically, $\alpha = 0 .$

Kinda pedantic, but I guess that I just felt weird writing $\alpha > 0 .$


This is not quite an answer, because what I'll discuss is only about as powerful as the attack in the question, which refers to section 3 onwards in: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (preliminary 2015-05 eprint).

The method I'll discuss is acknowledged in section 2.3 of the above article. It was exposed in the seminal: Don Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, in proceedings of Eurocrypt 1996; and in section 11 of his Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities in Journal or Cryptology, 1997 (paywalled; or try blind Googling).

The idea is to consider RSA moduli $N=pq$, with $N$ of $n$ bits, $p$ and $q$ prime, perhaps $q<p<2q$; and within that consider the moduli with a "weak prime factor" $p$ having the top $n/4$ bits matching some known arbitrary value (that also works with the low bits). Using a lattice attack (that is, based on the Lenstra-Lenstra-Lovász lattice basis reduction algorithm), $N$ is factored in polynomial time, and efficiently so for common RSA key sizes.

A preliminary version of Nitaj and Rachidi article stated (page 9 below table 2) that for  $N=pq\in[2^{1024},2^{1026}]$, the $\ge2^{759}$ moduli that their new method can factor

  is much larger than the number of RSA moduli with a weak Coppersmith
  prime factor in the same interval, which is actually $N^{0.25}\approx2^{256}$.

Fact is, the authors had grossly miscounted; their exponent $256$ in this quote is too small by a factor of nearly $3$. We get $>768$ is we assume all integers are prime (which in the circumstance is a fine approximation); or $>751$ if we consider that among 513-bit integers, one in about $2^{8.5}$ is prime. So the new method is at best claimed to improve Coppersmith's by a mere $8$ bits. Further, the set of weak Coppersmith prime factors can be trivially extended by a factor of $2^k$ by varying the low $k$ bits of the known arbitrary value.

As noted by poncho, neither method is likely to succeed for randomly seeded $p$ and $q$, for there are $>2^{1008}$ RSA moduli in the interval considered, and odds that a weak one is selected by chance are entirely negligible (in the order of $2^{-248}$).

What's notable with Nitaj and Rachidi's method is that it extends Coppersmith's attack to a more flexible set (not a much wider set) of RSA moduli; and has found applications in factoring more moduli actually deployed (that have been poorly generated) than in:  Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange: Factoring RSA keys from certified smart cards:
Coppersmith in the wild aka smartfacts, initially in proceedings of Asiacrypt 2013.

Update: the issue pointed above was promptly corrected in a revised version: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (2015-12-31).


Why isn't Rabin-Williams cryptosystem widely used?

At first I want to cite Lindell and Katz book:

  A "plain Rabin" encryption scheme, constructed in a manner analogous to plain RSA encryption, is vulnerable to a chosen-ciphertext attack that enables an adversary to learn the entire private key. Although plain RSA is not CCA-secure either, known chosen-ciphertext attacks on plain RSA are less damaging since they recover the message but not the private key. Perhaps the existence of such an attack on "plain Rabin" influenced cryptographers, early on, to reject the use of Rabin encryption entirely.

For RSA and Rabin systems encryption/decryption and signing/verification are similar, so I guess the Rabin digital signature system was rejected due to the same reasons as in the encryption case. But if you look at the IEEE or ANSI standards, you'll find that both RW and RSA systems are standardized. I also think, the RSA scheme became more popular as Rivest, Shamir and Adelman set up the "RSA Data Security" company, so they had more opportunities to implement their system in their security solutions and bring these solutions to customers.

Anyway, the reasons are more "historical" than "technical" and now it's easy to securely implement both signature systems. Nowadays cryptographers have been paying their attention to elliptic curves as the systems based on them usually provide the same or higher level of security, but are more effective in a number of applications. So it's unlikely that Rabin's system will have a second chance agaist RSA though it will be used in applications where the fast signature verification is the main requirement.


Most binary network protocols are already bounded. So if you just send the ciphertext (or the IV and the ciphertext) then the length will be known by the transport mechanism. Otherwise the method of communicating the length is entirely up to your imagination as long as you can map it to a presentation that is acceptable to your transport protocol.

Null termination characters within ciphertext or tag are not an issue for binary connections; null termination characters are only an issue for C-style null terminated strings. You don't want to send binary data directly over a text-based connection; you need a form of encoding such as base 64 encoding if you want to do that. The output size of base 64 encoding is determined during decoding, although the base 64 input must of course be bounded as well.

Note that you need some form of integrity protection of the IV and ciphertext if you want to securely send/receive ciphertext. So you need an authenticated mode of encryption or an authentication tag created by a MAC.


Proof of a key agreement protocol based on bilinear pairings

however... I can't see how they deduce $Pr[A_k] ≥ η(k)$ from the last expression.

They use the upper bound $Pr[E\text{ succeeds}|A_k]Pr[A_k]\leq Pr[A_k]$, which follows from the fact that $Pr[E\text{ succeeds}|A_k]\leq 1$.


Mathematical proof or any reference of "Deterministic random bit generator cannot produce more randomness than the randomness of seed"

Define the Mutual Information of a pair of random variables.
$$I(X; Y) = H(X) - H(X\mid Y)$$
For discrete random variables we hae that $H(X\mid X) = 0$, so:
$$I(X; X) = H(X)$$

The Data-Procesing Inequality states that for any function $f$, we have that:
$$I(f(X); f(Y)) \leq I(X; Y)$$
While we won't need it here, this includes randomized functions, provided they use randomness independent of either $X$ or $Y$.
Combining these two, we get that:

$$H(f(X)) - H(f(X)\mid f(X)) \leq H(X) - H(X\mid X)$$
If $f$ is deterministic, I believe the conditional entropies become 0, giving us:
$$H(f(X)) \leq H(X)$$
So the output distribution of a DRBG is always lower entropy than the distribution that its seed is drawn from.


Would XDES be more secure than 3DES, where X is a number > 3?

Would XDES be more secure than 3DES, where $X > 3$ ?

Yes. This answer about if 4DES / 5DES is possible illustrates it quite well.

It would however make more sense, if you really want to make it more secure, to have $n$-DES, where $n = 2k-1 \space | \space k \in \mathbb{N}$, or in simple terms: $n$-DES, where $n$ is an odd number.

This comes from the Meet-in-the-middle attack (MITM attack).

Example:

DES has a keylength of $2^{56}$. Double DES only has a keylength of $2^{57} (= 2 \times 2^{56})$. Only by using 3DES you start to really improve the security from single-DES: $2^{56} \times 2^{56} + 2^{56} \approx 2^{112}$.

  Why aren't we using XDES with large X?

Because of AES. It's not feasible to have MITM-attack on AES.

Using XDES instead of AES would have more drawbacks than benefits, especially from a computational view.


Why do we apply the concept of circuit in homomorphic encryption schemes?

We use circuits because they are universal (any function you want to compute can be expressed as a circuit) and because they are convenient (because we know how to solve the problem of fully homomorphic encryption for circuits but not for other models).  In particular, circuits are in some sense simple: all you need to do is find a way to implement an AND gate and a NOT gate, and that's enough to be universal.  This helps avoid inessential detail and helps us focus on the core of the problem.


I don't believe a hash function would be a promising looking approach.

For one, you state that The point of the hash is to not reveal the valid memory range, however you really can't do it.  If the attacker can see the program (and knows all the inputs to the hash, except for the destination address), he can simply evaluate it for all plausible destination addresses, and see which ones the hash allows access to.  Even if there were as many as a billion plausible addresses (and that's a truly huge program), that's still quite feasible.

You also state that you're interested in indirect branches whose legitimate target is within a small range; one example where this may come up with the compilation of a switch/case construct.  However, the memory addresses this uses are typically stored along side the program space, and so if the attacker could modify those addresses, they could also modify the instructions themselves, and so adding protection to this case doesn't really add much real protection.

Of course, there are the larger case, where the branch could legitimately go to a number of different locations throughout the program.  Examples where this might happen include:

Function pointers
Object method invocations
Exception handling
Function return (which, from a CPU standpoint, is a branch)

These cases are much harder; a pure range-based check might end up being "somewhere within the program executable code", which isn't a great help.  Encoding the actual legitimate addresses within the hash is going to be on the same order of magnitude as the simple concatenation of the address list, and so that'd be slow (as the CPU will need to load a nontrivial fraction of that data structure to check if the branch is legitimate).

Now, there's been a lot of work in this space (that is, how do we make sure that program branches are as intended by the correct program); this specific approach doesn't look promising.


Attack against modular inversion operation using side-channels?

Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continuous fraction), there may be some leakage there.
It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting by is $p$, and that the value you want to invert is $x$:

Select a random number $r$ that is $0 < r < p$ and is relatively prime to $p$ (and the latter condition is trivial if $p$ is prime)

Compute $blind = r \times x \mod p$

Compute the modulus inverse $blindinv = blind^{-1} \mod p$ (using the Extended Euclidean algorithm)

Return the value $result = r \times blindinv \mod p$

It is easy to see that this computes the modulus inverse correctly, and the value given to the underlying modulus inverse function is uncorrelated to the original value $x$ (and that the additional cost of the two modular multiplications is trivial compared to the cost of the modular inverse).
Is this really required?  I don't know; however, it seems to me that the above is so cheap that even if there is a chance of weakness, this randomization looks warranted.
Now, this hides the value being inverted from the attacker, but it doesn't apply a blinding factor to $p$; however while the time taken on average (given unknown inputs) by the EE algorithm does vary somewhat based on the modulus, it is a much weaker function (and gives far less information).  Blinding $p$ would be considerably more expensive; whether you would want to do so depends on the risk of any such leakage (e.g., if it's the country's missile defense codes, you probably will be willing to pay the additional costs), as well as how much you can afford additional costs.
If you are willing to pay the additional cost, the obvious way would be to select a value $r'$ that's relatively prime to $x$ (e.g., a prime larger than $p$), and in steps two and three, compute
$blind = r \times x$
$blindinv = blind^{-1} \mod (p \times r')$
(and the rest of the algorithm stays the same; the $\bmod$ operation in the next step will discard the extra information included by the $r'$ factor)
Assuming you pick $r'$ values about the same size as $p$ (or slightly larger), you would approximately double the cost.


How to authenticate two devices with CA?

The problem asked is not easily solved. To authenticate using cryptography as Dev1 in a way that a rogue Dev3 does not allow to imitate, Dev1 must know some secret key (or private key) that Dev3 does now contain (or does not allows to either extract or misuse), but that the CA can verify because it knows it (or knows the corresponding public key). Conventional cryptography (including public key cryptography, but perhaps not PUF-based cryptography or/and novel uses of quantum cryptography, which I won't consider further) has nothing else to offer.

The easiest workaround is to consider that Dev1 is whatever can prove being able to use the private key associated to the first public key for which the CA computes a certificate for something allegedly named Dev1, and have the CA reject any further attempt at obtaining a certificate under the name Dev1 (possibly: with the exception of duly authenticated certificate renewal requests if these are in the picture). When done properly, that can prevent Dev1 from working at all when it can be impersonated, which is better than nothing.

One method of solving the problem rather than working around it is to perform step 2 in an assumed secure location (e.g. factory) where the authentication of Dev1 is performed by non-cryptographic means.

Another method is to inject a secret key in Dev1 at a secure location, known also to the CA, so that step 2 can be performed with authentication using secret-key cryptography. That secret key can be a random octet string assigned at the secure location, and securely communicated (associated to the identifier Dev1, or the public Media Access Control address (MAC) of Dev1 if it has no name at that stage) to the CA, or the other way around.

As a more convenient variant of the above, the secret key can be a so-called diversified key, obtained using a key derivation function from a master key (known to the entity operating the secure location and the CA) and whatever identifies Dev1; the benefit is that only the master key needs to be securely communicated from/to the CA, which can recompute the diversified key of all devices. Note: for key diversification we do not need an entropy-streching key derivation function, and can use e.g. HMAC or AES (with the master key as key, and the identification as the other input); or any of the functions in NIST SP 800-108.
The key can be a Message Authentication Code of the Media Access Control address. The collision in TLA is accidental.

There are other methods, like embedding the same secret in all devices, and hoping it will not be extracted or misused; but they tend to have no operational advantage compared to the previous one when there is a CA, and be more brittle.


In my opinion your choice should come down to whether you want to hide the ID or not. If not, the use of encryption is just extra complexity and not useful. Most AEAD schemes allow decryption without authentication if the programmer really tries, so even that benefit is not very convincing to me.

A MAC, on the other hand, fits the problem perfectly well.

(Of course HTTP and plaintext email mean that your system has holes. Especially the former, since any eavesdropper to the connection will get to know both the URL and the content if you do not use TLS.)


State of the art low memory arbitrary-domain PRP?

Okay, here's the algorithm for "a fixed security level of 2128":

If  n ≤ 2^(2^128)  then sometimes-recurse shuffle with 128 bits of security.

If  2^(2^128) < n  then encryption just outputs the

plaintext and decryption just outputs the ciphertext.

The identity function can trivially be computed in O(1) space, so that algorithm

also uses only O(1) space.  (That's why, for true asymptotic analysis, one must

usually  assume some relation between n and the security parameter.)


I am fairly certain, that your proposed secret sharing scheme is actually not secure in any way:

If a party receives $s_i(x)$, then the secret polynomial is of the form $f(x)=s_i(x)+m_i(x) \cdot r(x)$ for some polynomial $r(x)$. And that is not equivalent to all possible polynomials. Even worse: If you allow the parties to choose $m_i$ themselves and of arbitrary degree, the parties can choose it do that they basically get $f(x)$ in the clear.

Example: $f(x)$ has degree $d$, then $m_i(x)=x^{d+1}$ gives back $f(x)$. Even if the degree is restricted, not all polynomials are possible.

But even if we assume, the secret sharing was secure, then your proposed algorithm would break it:

If the party can verify if their share was created properly, then the party can use this very procedure to learn something about $f$ instead. For any secret sharing scheme, giving the parties additional knowledge on top of their individual share will most likely break the information theoretic security (and otherwise it has to be proven). And since you have no computationally hard problem at all in your construction, it can't even have computational security.


Cryptographic security is not a one-dimensional spectrum. Increasing the key size increases keyspace, which is the maximum number of possible keys that must be iterated through to complete a brute force attack. Increasing rounds, on the other hand, reduces the chances that novel cryptanalysis, which allows an attacker to break the cipher faster than brute force, will be successfully applied to the cipher.

Cascading encryption
Cascaded encryption, even with stream ciphers, is vulnerable to a meet-in-the-middle attack, which reduces the effective keyspace from 512 bits to 384 bits. It is further reduced because layered stream ciphers commute (the order of the stream ciphers doesn't matter, so two keys whose first and second halves are swapped are equivalent). However, it will not reduce security and the keyspace will be larger than 256 bits, even if it won't reach the theoretical 512-bit maximum that you want. Regardless, no one is going to brute force a 256-bit key and doubling it to practically improve security is a quixotic endeavor.
In order to avoid the meet-in-the-middle attack, you would need to redefine AES to use a 512-bit key. This would require a deeper knowledge of the Rijndael key schedule, but if you successfully do it, you would be able to take full advantage of the larger key, even if it's unnecessary. This is a lot more difficult than just increasing the number of rounds though, and without heavy analysis, something may break.
Increasing rounds
Increasing the rounds has a bigger effect, although it does not increase the keyspace at all. Increasing the rounds from 14 to 28 would drastically improve security. But that doesn't mean you should do it! It's not necessary, because 14 rounds is already considered sufficient. You'd be decreasing performance while increasing the security from "excessive" to "even more excessive". There's no reason to do it. If you did have to, you would need to make sure you adjust the round constants correctly through $\text{rcon}$. Rijndael is able to generate up to 255 extra round keys, in theory, without modifying the key schedule.
AES with 256-bit keys was defined with 14 rounds (12 and 10 rounds for AES defined with 192 and 128-bit keys, respectively). This number was selected based on extensive analysis from many experts all over the world. During the AES selection process by NIST, the best attack was found to only penetrate 6 rounds. The designers of the cipher (called Rijndael at the time) decided to add four extra rounds at a minimum as a "security margin" to hedge against future attacks. It has held up extremely well so far.


Vigenere ciphertext encrypted with another vigenere cipher

Applying another round of vigenere would make the ciphtertext (in nearly every case) harder to break, yes. The problem is: This "new" algorithm is just a normal vigenere algorithm with a longer key (if the key lengths of both keys are not equal and not 1). You don't need to apply vigenere a second time, you can just calculate the new key in advance.

Example: We encrypt the plaintext "hello world hello world" with the key "ABC". (Encryption with A doesn't change the plaintext, it's like adding 0.)

hello world hello world
+
ABCAB CABCA BCABC ABCAB
=
HFNLP YOSND IGLMQ WPTLE

Now we encrypt the intermediate result again with the key "DDBC":

HFNLP YOSND IGLMQ WPTLE
+
DDBCD DBCDD BCDDB CDDBC
=
KIONS BPUQG JIOPR YSWMG

The length of the first key is 3, of the second key is 4. The least common multiple of both numbers is 12. If we now repeat the first key 4 times and "encrypt" it with the second key, we get a new key which eliminates the need for a intermediate result:

ABC ABC ABC ABC
+
DDB CDD BCD DBC
=
DED CEF BDF DCE

If we encrypt the plaintext with this new key we immediately get the final ciphertext:

hello world hello world
+
DEDCE FBDFD CEDED CEFBD
=
KIONS BPUQG JIOPR YSWMG

You see, double encryption (or more generally, multiple encryption) with vigenere doesn't add extra security by itself. You could just use a longer key from the beginning on. Search for generals attacks on vigenere to break this "double encryption".

What about the one-time-pad? You need a fully random, never before used key, which has to be as long as the plaintext for the one-time-pad. If you really use this scheme, you also don't need a double encryption: The one-time-pad is always fully secure if you tell nobody the key.


The best option you have is TLS_ECDHE_ECDSA_WITH_AES_256_CBC_SHA. This is likely to provide most security, as the AES keylength is maximal and ECDSA keys tend to provide more security than RSA keys, as a 128-bit security level is quite common with ECDSA (field size: 256 bit) whereas 112-bit is the standard with RSA (keylength: 2048 bit).

However in practice TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA may be easier to deploy as RSA certificates are usually a lot cheaper and easier to get.

To get even further you're also fine with TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA and TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA as a 128-bit key is quite common today and chances are your ECDH group also provides "only" 128-bit security, meaning you can get higher speed without sacrificing security.

As explained in the comments by CodesInChaos you should definitely avoid RC4, which is also officially banned from TLS as per RFC 7465. To repeat what CodesInChaos said:
 The CBC-suites are less an issue than RC4 because ...

modern browsers mitiagate BEAST (CBC-based attack) even on TLS 1.0
BEAST is an active attack, whereas RC4 already falls due to passive attacks
BEAST is hard to exploit in practice and relevant features seem to have been removed.

This removes the TLS_ECDHE_RSA_WITH_RC4_128_SHA and TLS_ECDHE_ECDSA_WITH_RC4_128_SHA ciphersuites from the list. You should also avoid 3DES, as it provides "only" 112-bit security, but is significantly slower than AES making it inferior in every aspect, so you shouldn't choose TLS_ECDHE_RSA_WITH_3DES_EDE_CBC_SHA nor TLS_ECDHE_ECDSA_WITH_3DES_EDE_CBC_SHA.

However, if possible you should migrate to TLS v1.2 (or newer). There you should avoid all cipher suites not finishing with ..._SHA256 or _SHA384 as the other ones use SHA-1 which is deprecated. Furthermore TLS v1.2 (or newer) allows (v1.3 will force) you to use non-CBC mode ciphers, especially AEAD ciphers, which don't suffer from BEAST or similar attacks. This means that as of now the best choice (in terms of security) for the cipher suite is TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384, with TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 not being a lot weaker. If possible you should prefer ECDSA (or EdDSA) over RSA although RSA can be sufficiently secure when using appropriate keylengths.


Is this SHA256 hash implementation secure from rainbow table, brute forcing attacks?

TL;DR: 64-bit entropy is nowhere near enough against a serious attacker.

Yes, you have calculated the worst case correctly.
Your second calculation isn't about rainbow tables, but about a full hash table.

Now for "how long can you stop a serious attacker" if you hash a fully random 8 byte string with SHA-256. If the attacker has enough money, they can design their own ASICs for this or ask nicely at companies like AntMiner to produce such ASICs. So assuming you pay a little more, you can probably get 1GHash/s for 1000 USD (AntMiner's S7 is at 4.7THash/s for 575USD + energy, network,... at the moment). So to break the hash using one miner (with 1THash/s), you need 213 days, whereas if you buy 427 of them, you can break the hash in at most half a day and expect to break it in a quarter of a day on average and at this point you wouldn't even be egligible to the highest discount they offer (at 500 pieces and more).

Rainbow tables should allow for quick breaks of the security and normally reduce the storage required to $2^{2n/3}$ and the computational requirements to $2^{2n/3}$ per look-up or more generally, given $2^m$ storage, the lookup time will be around $2^{2(n-m)}$.
If you want to defend against rainbow tables, salts are inevitable, because you need a full rainbow table per unique salt, which is computationally and storage-wise intense. As for the efficiency of rainbow tables, you need a full pass over the complete space (all $2^{64}$ values) to build the table. For the original (first) publication of rainbow tables, see "Making a Faster Cryptanalytic Time-Memory Trade-Off" by Oechslin (PDF)


If $m\|r$ is assimilated to the integer $m+2^{l}r$, with $m\in\{0,1\}^{l}$, then little-endian convention is being used.

More precisely: under (unsigned) little-endian convention, a bitstring of $k$ bits $b=b_0\|b_1\|\dots\|b_{k-1}$ where each $b_i$ is a single bit is assimilated to the (non-negative) integer $\tilde b\,=\,\displaystyle\sum_{i=0}^{k-1}b_i2^i$ . It follows that if $m$ and $r$ are bitstrings, the bitstring $m\|r$ is assimilated to the integer $\widetilde{m\|r}\,=\,\tilde m+2^{|m|}\tilde r$ (where $|m|$ is the number of bits in bitstring $m$ ).

For example, if $m\,=\,\mathtt{'00110101'}$ and $r\,=\,\mathtt{'1010'}$ , then $|m|=l=8$ , bitstring $m$ is assimilated to the integer $\tilde m=2^2+2^3+2^5+2^7=172$ , bitstring $r$ is assimilated to the integer $\tilde r=2^0+2^2=5$ , bitstring $m\|r\,=\,\mathtt{'001101011010'}$ and is assimilated to the integer $\widetilde{m\|r}\,=\,2^2+2^3+2^5+2^7+2^8+2^{10}=1452$ , and indeed $172+2^8\cdot5=1452$ .

Under (unsigned) big-endian convention, $b=b_0\|b_1\|\dots\|b_{k-1}$ is assimilated to the integer $\hat b\,=\,\displaystyle\sum_{i=0}^{k-1}b_i2^{k-1-i}$ . It follows that $m\|r$ is assimilated to the integer $\widehat{m\|r}\,=\,2^{|r|}\hat m+\hat r$ .

For example, if $m\,=\,\mathtt{'00110101'}$ and $r\,=\,\mathtt{'1010'}$ , then $|r|=4$ , $\hat m=2^6+2^5+2^2+2^0=101$ , $\hat r=2^3+2^1=10$ , $m\|r\,=\,\mathtt{'001101011010'}$ , $\widehat{m\|r}\,=\,2^{10}+2^9+2^6+2^4+2^3+2^1=1626$ , and indeed $2^4\cdot101+10=1626$ .

The notation $\tilde{}$ for little-endian and $\hat{}$ for little-endian is entirely made up for the purpose of that answer, and omitted in practice. Endianness is considered too mundane to be made explicit, but/thus is a cause of endless headaches, incompatibilities, frustrations, and conversion code.

It is possible to use one convention for bits in $m$ and $r$, and the formula of the other convention for $m\|r$ , that is assimilate $m\|r$ to integer $\hat m+2^{|m|}\hat r$ or $2^{|r|}\tilde m+\tilde r$. That's mixed endianness, and surprisingly common, often with change of endianness at regular intervals, e.g. at the octet (8 bits) or/and word (e.g. 4 octet) level. In that case, the formula converting bits to integer grows hairy (the practitioner's hair looking at bits with a debugging tool are correspondingly pulled out).

Most humans (including cryptographers unless otherwise stated, perhaps obliquely by throwing $m+2^{l}r$ in) tend to use big-endian convention, for natural reasons: when we are told twenty-five predators are approaching, twenty goes before five because that gives the order of magnitude sooner. The same ordering is kept when writing 25.

Little-endian is often used for transmission of individual bits in bytes, historically because it eased interoperability between equipments using asynchronous communication and different character width. However network byte order, or network order for short, refers to big-endian convention at the upper level (if you look at how a 16-bit IP port number is physically transmitted on a network, e.g. with an oscilloscope across the contacts of the LED transmitting into optical fiber, a 10Mbit/s Ethernet twisted pair, or an old modem, you'll find that's with little-endian convention within an octet, and with the high-order octet first, that is big-endian at a higher level).

Intel's convention is essentially opposite: it uses little-endian byte order (the low-order octet of a word has the lowest address, and documentation shows it first whenever octets are separated from each others); but when documentation shows an octet, that's with big-endian convention (always for decimal and hexadecimal, often for binary; however bits remain numbered with 0 for the low-order bit; ISO standards often start at 1 to make things worse, but I digress).

Little-endian convention removes the need for buffer memory when adding integers represented by bitstrings, octet strings, or vectors of limbs made available sequentially or by increasing address (serial memories or CPUs favoring index increment over decrement; ironically, the later applies to the Motorola 68000 CPU, which use big-endian octet order). That makes little-endian popular for implementation of multiple-precision arithmetic, together with the fact that realloc() can be used to adjust storage without changing the value represented.

Big-endian and Little-endian refer to names of the two camps in a fictional war, which wanted to impose on the other side the opening of eggs by the big or little end; see Gargantua Gulliver's Travels for details. This should remind us that "more sensible xxxx endian" should be taken like eggs: with a grain of salt.

The two most common conventions for signed integers are nowadays:

Two's complement, where signed integer $x$ is represented by bitstring $b$ such that $-2^{|b|-1}\le x<2^{|b|-1}$ and the unsigned integer $\tilde b$ or $\hat b$ is $x\bmod2^{|b|}$ , lying in interval $[0\dots2^{|b|})$.
Sign and magnitude, where signed integer $x$ is represented by bitstring $b$ such that $-2^{|b|-1}<x<2^{|b|-1}$ and the unsigned integer $\tilde b$ or $\hat b$ is

$2^{|b|-1}-x$ when $x<0$
$x$, otherwise

Under both sign conventions, one of the bit of $b$ (the first when combined with big-endain convention, the last with little-endinan) is the sign bit, with $1$ for negative.

Under two's-complement, the result of addition modulo $2^{|b|}$ can be obtained using the same rules for unsigned and signed integers (only overflow detection varies). This explains why two's-complement is common in modern CPUs.


On modeling a random oracle hash function which maps $\mathbb{G}_1 \rightarrow \mathbb{G}_2$

Assuming that you insist that $H$ preserve the group operation, that is, if $H(A) \times H(B) = H(A+B)$ for any $A, B \in \mathbb{G}_1$, then it would be difficult to come up with an explicit representation (and in any case, the random oracle model doesn't appear to be a great fit).

I'll take the last point first: a random oracle is intended to be something that gives random answers that are consistent with answers that it previously gave.  The problem here is that once this Oracle gives one output (e.g. $H(P) = Q$, then (assuming $P \ne 0$), then this determines all other outputs that the random Oracle is allowed to give.  Any other input can be represented as $kP$ for some integer $k$ (because all nonidentity elements for a group of prime order are generators), and we insist that $H(kP) = Q^k$.

As for an explicit model of the random Oracle which can be evaluated, well, the problem that runs into is if we select a $\mathbb{G}_1$ where the discrete log problem is hard, and a $\mathbb{G}_2$ where it is easy -- any explicit representation of an Oracle (except for the trivial one $H(P) \equiv 1$) would allow us to solve the discrete log problem in $\mathbb{G}_1$; which we assumed was difficult.

If you don't care whether the model can be evaluated, then it's easy; have the random oracle pick an arbitrary $P \ne 0 \in \mathbb{G}_1$ and a random $Q \in \mathbb{G}_2$; then, whenever it gets a query for $H(kP)$, it just returns $Q^k$.


How would one go about adding key commitment to an AEAD like AES-GCM or ChaCha20-Poly1305?

First off, let us start by reviewing how AES-GCM/Poly1305 works internally (and how these key commitment attacks work).
Here's a top level overview of how they work (and AES-GCM and Poly1305 work largely the same at this level): first the ciphertext and AAD are combined to form a series of field elements $M_n, M_{n-1}, ..., M_1$; the details of how they are combined differ between the two; however they both have the property that they can control the value of a specific message block $M_i$ by adjusting a specific ciphertext block.
Then, the take a key dependent value $H$, and compute in some finite field the polynomial:
$$M_n H^n + M_{n-1} H^{n-1} + ... + M_i H^i + ... + M_1 H^1 + F(key, nonce)$$
And that is the tag (well, not quite in Poly1305; the final addition is done modulo $2^{128}$, however that is only a minor complication for this attack).
The finite fields differ between the two (GCM uses $GF(2^{128})$, while Poly1305 uses the prime field $GF(2^{130}-5)$), but that doesn't matter.
Now, the attacker who is trying to find a message that has the same tag for two different keys (and hence would be accepted as valid under both keys) controls the ciphertext, and knows everything (the AAD, the key, the H values, and the values of $F(key, nonce)$.  So, what the attacker can do is fix the entire ciphertext (except for the part that contributes to $M_i$), and combine those parts of the tag computation into known constants $C, C'$, and then look for a value of the remaining ciphertext block that gives rise to an $M_i$ value that satisfies:
$$M_i H^i + C = M_iH'^i + C'$$
(where $H, H'$ are the internal $H$ values of the two keys).  This is an easily solved problem, leading to the message that would have the same tag value for both messages (and since the attacker knows everything, he can easily compute that common value).  Actually, it's a bit more complicated for Poly1305, as not all $M_i$ values can be obtained from a ciphertext block, however a nontrivial fraction can, and so the attacker can find such a value by adjusting another ciphertext block with not that much effort.
Ok, now that we have reviewed the attack, let us examine how well these three ideas would fare:

Key identifier in the nonce

In the above attack, this would modify the value $F(key, nonce)$ values to be dependent on the key; however that is already dependent on the key, and so the attack would proceed exactly as planned.

Key identifier in the additional data.

In the above attack, this would modify some $M_j$ values (the ones that are dependent on the AAD); however $j \ne i$, and because the attacker would know these $M_j$ values, this would just modify the $C, C'$ values that appear in the above attack, and so would not complicate this attack at all.

Zero padding prepended to each message that gets verified after decryption

The above attack doesn't address this at all.  Instead, this defense happens during the actual decryption step; in this step, the crucial plaintext block would be computed $P_i = C_i \oplus F( key, nonce, i )$, and to find two different keys that decrypt the $P_i$ block to all zeros (which is required for the message to be accepted with both keys), the attacker would need to find two keys where $F( key, nonce, i ) = F( key', nonce, i )$; there is no known weakness in either AES or ChaCha20 that could be exploited, hence the best attack known would be a birthday collision attack.  This indicates that to get a security strength of $2^k$ against this attack, we would need to prepend $2k$ zeroes (which may involve a collision attack across several blocks; this doesn't change the analysis).


How do Hash functions work under the hood?

There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(dated 1979), and suffers from length extension attacks. New hashes might opt for the sponge construction, as it is immune to that particular attack.
As for how they work, they both contain an internal state and operate on that state using a function that is actually invertible.
The Merkle–Damgård construction
In the case of the Merkle–Damgård construction, the function used is usually a block cipher. Normally, the go-to example of a block cipher is AES, but because of a related key attack, you would not want to use it to make a hash with this particular construction.
Basically, in the Merkle–Damgård construction, successive blocks of the hash input are used along with the internal state as the inputs to a block cipher; This is also how the construction compresses large inputs into a finite state. This is another requirement of hash functions: the ability to operate on (effectively) arbitrarily sized inputs and produce a finite-sized output.
As for collision resistance, the MD construction has a proof: "... that if the one-way compression function f is collision-resistant, then so is the hash function constructed using it.".
However, according to wikipedia,  the MD construction itself, has generic vulnerabilities that are not the result of an unsatisfactory compression function:

Unfortunately, this construction also has several undesirable
properties:

Second preimage attacks against long messages are always much more efficient than brute force.
Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.
"Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more
work than finding a collision, but much less than would be expected to
do this for a random oracle.
Length extension: Given the hash H(X) of an unknown input X, it is easy to find the value of H(pad(X) || Y), where pad is the padding
function of the hash. That is, it is possible to find hashes of inputs
related to X even though X remains unknown. Length extension attack
was actually used to attack a number of commercial web message
authentication schemes such as one used by Flickr.

It is possible to use the MD construction with a sort of capacity, similar to a sponge, by not outputting the entire state. This is where the ideas of SHA-224 and SHA-384 fit in, for example. They are simply truncated outputs of SHA-256 and SHA-512 (with other small modifications). By not revealing the entire state, length extension attacks may be foiled, depending again on the "capacity", or number of bytes dropped this way. However, usage of a capacity/truncating the state does come at the price of a reduced output rate.
The sponge construction
The sponge construction operates in a different manner. The sponge has an internal state, too, and it uses an invertible permutation to mix the state. Basically, the sponge "absorbs" a message block into its internal state, then applies the mixing permutation, and repeats this until all message blocks have been consumed into the state. This is how the sponge compresses data. The absorption of data either happens by XOR'ing the message block into the state or simply replacing a section of the state with the message block.
The sponge construction being uninvertible, resistant to length extension attacks, and preimage resistance is related to the use of a "capacity" section of the state. Basically, there is an imaginary line dividing the internal state into two sections, a "rate" section, and the capacity section. The output stage of the function only "squeezes" bytes from the rate section of the internal state. Since the capacity is never output directly, length extension attacks are resisted. The security of the sponge against attacks is related to the capacity size of the state, along with how well the mixing function resists things like differential cryptanalysis.
Padding
There is a little bit more to hashing then a confusing/diffusing primitive that compresses data. Since we require that it be infeasible to generate any preimage for a given output, and prevent anyone from finding collisions, things like padding of the input become very important, in order to prevent trivial collisions from being created. This is a contributor as to why the construction of a hash is more complicated and oftentimes requires more applications (rounds) then simply encrypting some data.
Other compression functions
There is actually an entire Wikipedia article about one-way compression functions, and there a few constructions one could use:

Some methods to turn any normal block cipher into a one-way
compression function are Davies–Meyer, Matyas–Meyer–Oseas,
Miyaguchi–Preneel (single-block-length compression functions) and
MDC-2, MDC-4, Hirose (double-block-length compressions functions)


Exact mathematical definition of simulation based security?

Suppose Alice has $x$ and Bob has $y$ in your scenario, and let $\pi =(\pi_A, \pi_B)$ be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice.

Define the following algorithms / random variables:

${\sf Real}(\pi, y,\mathcal{A},1^k)$:

Internally simulate an instance of $\pi_B$ on inputs $(1^k,y)$, interacting with an instance of $\mathcal{A}$ on input $1^k$.
$\pi_B$ will eventually terminate; call its output $q$ (note, this is supposed to be the output of $f$, or it can be an error indicator). Likewise $\mathcal{A}$ will eventually terminate; call its output $t$.
Output $(q,t)$.

${\sf Ideal}(f, y,\mathcal{S},1^k)$:

Internally simulate an instance of $\mathcal{S}$ on input $1^k$ until it generates an output $\tilde x$.
Calculate $p = f_A(\tilde x, y)$ and $q = f_B(\tilde x, y)$.
Give $p$ to $\mathcal{S}$ and keep running it until it finally terminates; call its output $t$.
Output $(q,t)$.

Then we say that the protocol is secure if:

  For all PPT machines $\mathcal{A}$ there exists a PPT machine $\mathcal{S}$ such that for all $x,y$, the ensembles $\{ {\sf Real}(\pi, y,\mathcal{A},1^k) \}_k$ and $\{ {\sf Ideal}(f, y,\mathcal{S},1^k) \}_k$ are computationally indistinguishable.

I'll assume you're comfortable with the notion of computational indistinguishability.

Some general observations:

The value $t$ is whatever $\mathcal{A}$ decides to output. One reason why it's difficult to understand at first is that we are not specifying a "goal" that $\mathcal{A}$ wants to achieve. It's more general than that. Instead, we're saying that: Any value $t$ that $\mathcal{A}$ can generate by participating in the real interaction, is possible to generate when the only thing you are allowed to do is choose an input $\tilde x$ (once) and get back $f_A(\tilde x, y)$.

Without loss of generality, $t$ can be the entire view (private randomness along with all of the messages received in the protocol) of $\mathcal{A}$, since $t$ would have been efficiently computed from the view. Sometimes the terms view and transcript are used synonymously, though the term view better entails that private randomness is included as well. Also, this is why $\mathcal{S}$ is referred to as a simulator, since it must be able to simulate everything that $\mathcal{A}$ would have seen.

We also include the output $q$ of the honest party Bob in these distribution ensembles. This models the fact that $\mathcal{A}$, in addition to learning no more than is possible in the ideal world, has an effect on Bob that is possible in the ideal world. In particular, $\mathcal{A}$ can't force Bob to output a value that is inconsistent with $f$ (other more subtle attacks are also ruled out in this way).

Of course, even this fairly detailed definition does not include everything tha there is to say. To be absolutely precise you have to specify how the protocol interaction works, whether the adversary has control over delivery of messages, whether the multiple components (adversary, protocol) should be executed in series or parallel, etc.. But once you have conventions for these things, the $\sf Real$ and $\sf Ideal$ processes are well-defined, and everything else written here is pretty sound.

More sophisticated definitions allow $\mathcal{A}$ (and hence $\mathcal{S}$) to communicate online (i.e., during the protocol execution) with an external "environment" ... that introduces a whole lot of other complications. So for the purposes of this response, we'll leave it as a static interaction.


As @SEJPM notes, the primary purpose of rotating encryption keys is not to decrease the probability of a key being broken, but to reduce the amount of content encrypted with that key so that the amount of material leaked by a single key compromise is less.

However, for signing keys there is a concrete reason: say it takes $X$ months of computation (expected value given your threat model) to crack a key, and you rotate your signing key every $X-1$ months and revoke the old one, then by the time an attacker has cracked the key, any new signatures produced by the attacker will either be A) rejected by clients because of key expiry, or B) back-dated to before the key revocation (which should also raise warning in clients).


Is p#1v2.1 still not supported by outlook/microsoft or am I just crazy?

PSS seems still not introduced to Microsoft, please see here. It's a long discussion, but in the end it seems that you cannot select PSS as a signature scheme when sending, I presume that also means that PSS signatures are not accepted.
RSA-OAEP based encryption is generally supported earlier than PSS. There are padding oracle attacks against the PKCS#1 v1.5 encryption scheme. The PKCS#1 v1.5 signature scheme is still considered secure, so there is much less need for upgrading it.


Are IVs and salts the same and usable for each other uses?

No.

A salt for a PBKDF is to prevent a bruteforce search to be able to target multiple passwords at once. You generally choose one salt for a password per user, and store it. So you do not keep generating salts, only when the password is set/changed.

The role of an IV depends strongly on the mode. In some modes it is only required for semantic encryption (the same message encrypted twice is still different). For other modes such as CTR it's absolutely required for security. In general the IV should change for every message, which is the most important difference.

Note that "generate an IV which must be completely random and not predictable" is not always true. For example the IV, or nonce, for the ChaCha cipher does not need to be random nor predictable - just always different.


Tweak per message offers good security like IV per message .

Basically a tweakable block cipher with same tweak for all messages is same as non-tweakable block cipher. It is deterministic in nature and not considered secure enough in itself. You need to apply a mode of encryption that has been designed for non-tweakable block ciphers to make it secure.


Key generation for DH key exchange - benefits of using KMI

Using a Diffie-Hellman key exchange is best using keys generated on-the-fly. The reason comes down to a historical issue...
Let's say we contact a web server. The server uses the key pair $S_{pub},S_{pri}$, and out client uses key pair $C_{pub},C_{pri}$. If the web server never changes its key pair, and we don't either, the handshake will always yield the same result. Let's hypothesize, the server could possibly have a hard-coded key pair (web servers and browsers used to have a vulnerability where the DH key pair was literally hard-coded. This has since changed but we don't wanna revert to old mistakes). Now, if I contact 2 web servers with the same keys I will always get the same private key. Thus, now each server can read my communications with the other, assuming they get the ciphertext.
Even if only one side has an unchanging DH key, a compromise of that key would result in the compromise of every message between the parties. However, if the key is generated randomly each time, by both sides, you get a system with perfect forward-secrecy.
However if we want to use an IPS with DPI on our communication, it would allow the IPS to make sure the data isn't loaded with exploits and malware and all sorts of nasties. That's the only reason I can think of to use an unchanging key pair.


What does pseudo pre-image of a hash function mean?

The pseudo-preimage is the problem of finding $(IV, M)$ given $t$ such that $H(IV, M) = t\ $.


What is the significance of the value $1/2$ within the first property of a LLL-reduced basis?

The case considered in the suggested notes is in fact Gauss-Lagrange algorithm.
You can also see the notes here.

According to the terminology considered in the notes, you have :

${\bf \tilde{b}}_2={\bf b}_2-\mu_{21}{\bf b}_1$

${\bf b}'_2={\bf b}_2-\lfloor \mu_{21}\rceil{\bf b}_1$

${\bf \tilde{b}}_2-{\bf b}'_2$ is parallel to ${\bf b}_1$ and
$||{\bf \tilde{b}}_2-{\bf b}'_2||=|\mu_{21}-\lfloor \mu_{21}\rceil|\ ||{\bf b}_1||.$ But $|\mu_{21}-\lfloor \mu_{21}\rceil|<1/2$ so $||{\bf \tilde{b}}_2-{\bf b}'_2||\leq ||{\bf b}_1||/2.$ Also the length of the projection of ${\bf b}'_2$ over ${\bf b}_1$ (denote it by $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||$) is  equal to $||{\bf \tilde{b}}_2-{\bf b}'_2||,$ so you get $||{\rm proj}_{{\bf b}_1}{\bf b}'_2||\leq ||{\bf b}_1||/2.$

The $1/2$ guarantees  that the vectors of the new basis of the lattice will have always smaller lengths than the previous.

In fact, if you repeat the previous steps, you will end up with the minimum vectors (with respect to the Euclidean length) in polynomial time bit complexity.
In general LLL (for dimensions $> 2$) provides two small vectors (not the minimum ones) in polynomial time bit-complexity.


The main complexity of attacks using a quantum computer with Grover's attack is explained here. I'll use the remainder of the answer to indicate some possible misconceptions in your question.

  It's hard to say exact QC specs, but let's assume we have decent a quantum computer using Grover's algorithm that is able to half AES-128 keyspace to that of AES-64.

Quantum computing won't change the dynamics of the cipher itself. Although the complexity of the attack may be altered, it won't magically change AES-128 into AES-64.

  How long will a bruteforce attack take on a AES-64 protected key? What about AES-128 or AES-256? Also, would we be able to increase to AES-512 and still maintain the same level of security?

Neither AES-64 or AES-512 is well defined. With AES the number of rounds and the key schedule are both dependent on the key size. It's therefore wrong to even talk about AES-64 and AES-512 as you wouldn't know the number of rounds or key schedule, and the security of a cipher depends on those parameters.

  Since the keyspace is halved, does it also introduce any other possible vulnerabilities to attack vectors (in addition to any attacks that can be done on a QC)?

I don't see how it would be able to do that. This would only be the case if additional attack vectors or a better understanding is retrieved from a GC attack. That doesn't seem all too likely.

AES-256 is considered safe against quantum computing attacks; a security margin of 128 bits is considered unbreakable. So there is not much need for AES-512 as currently foreseen.

In general - especially for symmetric algorithms - an increase of key size, block size, internal state and/or output size does seem to satisfy most crypt-analists with regards to attacks based on quantum computing. Instead of just increasing the key size it would probably be wise to use a larger block size and internal state as well (you could use one of the SHA-3 finalists such as Keccak/Keyak or Skein/Threefish as base).


About the memory requirement

Your target is 8 bytes long i.e. $2^{64}$ possibilities.

The probability to have a collision is given by the formula:
$$P(n,N) \approx 1 - e^{-n^2/2N}$$
Where $N$ is the size of the output space and $n$ the number of values you try. By inverting the equation you get:
$$n \approx \sqrt{-2N\ln (1 - p)}$$
For $p = 0.5$, you get :
$$n \approx 1.2\sqrt{N}$$
Thus with $N = 2^{64}$, $$n = 1.2\times 2^{32}$$
Therefore you will need to generate about $5\ 000\ 000\ 000$  values of 8 bytes. The memory requirement is therefore of $40 GB$.

If you target $p = 10\%$ in order to reduce the memory requirement (you will just need to do the experiment a bunch of times), you will need $0.46\times 2^{32} \approx 2\ 000\ 000\ 000$ values and about $16 GB$ (which is a bit less constraining.

What you are doing is actually called a multi-target attack. I would also suggest you to have a look at this question : What are the memory requirements for this type of search if the hash function has an output length n bits?

Some optimisations:

You might want to avoid the random generation part. You could just take a seed $s$ and iterate from it using an array of values such that
$$\forall i, h[i] = \mathop{SHA}(s + i)$$
This will divide the memory space required by 2 (as you don't need to store the value because it is the array index of the hash).

You might also want to consider the time complexity of your search (for each value you need to check that there are no previous collision). From my point of view, this really looks like in $O(n^2)$...

Another possibility would require you to look at differential cryptanalysis of $\mathop{SHA1}$ and look for differential trails where the 8 first bytes of the last difference are being composed only of $0$.


In my limited understanding, cache attacks should be consider the most. In AES encryption, one need to subBytes using S-Box. So, for data that has been used and saved in cache, it will takes less time to subBytes. So, Mallory can learn about the pattern of plaintext.

https://cr.yp.to/2005-590.html


Key derivation of public key without knowledge of private key

For public key encryption, there's an easy solution using a variant of Elgamal. (If you want to do authentication, you can use standard algorithms. If you specifically want signature schemes, say so.)

Recall that the security of Elgamal is equivalent to DDH, which is talking about indistinguishability of certain subgroups, namely given a cyclic group $G$, a (arbitrary) generator $g$ and an element of the group $y$, decide if the pair $(x,z)$ lies in the subgroup of $G \times G$ generated by the pair $(g, y)$.

We can phrase Elgamal as follows: To encrypt using the public key $(g,y)$, choose a random number $r$, compute $x=g^r$, $z=y^r$ and $w = zm$. The ciphertext is the pair $(x,w)$.

Deciding if $(x,w)$ is an encryption of $m$ is equivalent to deciding if $(x,w/m)$ lies in the subgroup.

Now observe that if $(g,y)$ is a public key, then $(g',y') = (g^b,y^b)$ is just as good a key.

Finally, to decide if $(g',y')$ and $(g'', y'')$ represent the same public key is equivalent to deciding if one lies in the subgroup generated by the other.

Most tricks you would use to improve the security of Elgamal would work for this variant as well, even with randomized keys.

With a bit of thinking, I am sure you can come up with lots of variations of this general idea.


Alter plaintext through IV in block cipher AES in CBC mode

Each bit you flipped in the IV changes the same bit in the decrypted plaintext. So if you want to change the first E character of ENCRYPTED into a T of THE then you need to XOR the binary representation of E and T (probably ASCII) and XOR that with the byte in the IV. This will of course only work for the first block of 16 bytes. Fortunately "SEND THE DATA" is small enough for that (13 bytes if I count correctly).

That leaves the problem of the padding. The original block contains the padding in the second block because of the size (19 bytes). However, you just have to adjust the padding of the first block by performing the XOR as displayed above. Instead of XOR'ing the final 16 - 3 = 3 plaintext bytes with a letter you XOR them with the value 03 in hex and XOR that with the IV. Now you've also generated the required padding.

Finally, you need to leave out the second block. And that's all me wrote, happy programming.


What is the meaning of "probabilistic encryption algorithm"?

Informally, in probabilistic encryption random values are used to encrypt a message. Thus, each time we encrypt a message we pick a fresh random value; as a result if we encrypt the same message twice we would get different encrypted value (or ciphertext).This means that the ciphertext does not depend only on key and plaintext.


Zero-knowledge proof using quadratic residue: why two options?

Let me attack if you (the verifier) always select $b = 1$ as a random challenge.

The zero-knowledge proof for QR.

Let us recall the zero-knowledge proof for QR.
The common inputs are $y$ and $x$ and the prover possesses a witness $w$ which satisfies $w^2 \equiv y \pmod{x}$.

The prover generates a randomness $r \gets \mathbb{Z}_x$ and sends $a = r^2 \bmod{x}$.
The verifier rejects if $a \equiv 0 \pmod{x}$; Otherwise, the verifier sends a random challenge $b \gets \{0,1\}$.
The prover sends a response $z = w^b \cdot r \bmod{x}$.
The verifier checks if $z^2 \equiv y^b \cdot a \bmod{x}$.

An attack for a fixed challenge $b$

If you always select $b = 1$,
I can deceive you while I do not know $w$.

I choose a random value $\tilde{z} \gets \mathbb{Z}$ and compute $\tilde{a} = \tilde{z}^2 \cdot y^{-1} \bmod{x}$. I send $\tilde{a}$ to you.
You select a "random" value $b = 1$ and send it to me.
I send $\tilde{z}$ as a response.
You finally obtain $\tilde{z}^2 \equiv y \cdot \tilde{a} \bmod{x}$, since I select $\tilde{a}$ to satisfy this equation.

This attack shows that the protocol cannot be sound if the challenge is unique.
Hence, the verifier should flip at least one coin.

Why $b \in \{0,1\}$

In the soundness proof, we retrieve a witness as follows:
Running the (cheating) prover twice with distinct challenges, we obtain two accepting transcripts
$$(a, b_0, z_0) \text{ and } (a, b_1, z_1).$$
Since they pass the verification, we have
$z_0^2 \equiv y^{b_0} \cdot a \pmod{x}$
and
$ z_1^2 \equiv y^{b_1} \cdot a \pmod{x}$.
Therefore, we have $z_0^2 \cdot y^{-b_0} \equiv a \equiv z_1^2 \cdot y^{-b_1} \pmod{x}$
and $(z_1/z_0)^{2} \equiv y^{b_1-b_0} \pmod{x}$.
If we select a challenge from $\{0,1\}$, the difference $b_1 - b_0$ is $1$ or $-1$.
Hence, we obtain $z_1/z_0$ (or $z_0/z_1$) as a quadratic residue of $y$.

The point is that the difference $b_1 - b_0$ is always $\pm 1$.
This means that you can choose $b$ from another set, say, $\{2,3\}$ or $\{3,4\}$.

You can read explanations in the textbooks, e.g., Barak's lecture note.


The scheme you described is not a sensible scheme for 2-way client/server communication.

The new RSA public keys are not authenticated, thus you are not safe against active attackers, who could intercept the connection (or replace one of the partners). Those could read all the content, and/or replace it with their own.
If you would be using authenticated public keys (e.g. by certificates), the privacy would be given (i.e. an attacker couldn't read messages). But your messages have no authentication, and an active attacker could replace messages with their own ones, insert his ones, or drop messages.
You are using "ephemeral RSA key pairs" for each connection – this incurs a slight performance overhead, as generating new RSA key pairs is slightly expensive.
Using RSA for bulk encryption (and even more decryption) is really expensive, compared to a same-security block or stream cipher. Don't do this.

This is not essentially the same as what TLS is doing with RSA (assuming RSA key exchange):

In TLS the server's public key is accompanied by certificates, which allows the client to verify that it is really speaking to the right server. (The client is normally not authenticated.)
In TLS the client generates some random data and sends it by RSA to the server, to this some more random data from both client and server is mixed and used to produce symmetric keys for encryption and authentication using a symmetric cipher and a (symmetric) MAC algorithm. These are used for the actual communication (after some check to verify that both have the same keys).


I don't think there is a direct between the type of norm and whether $\delta=0$. For example, this crypto.SE answer mentions a mechanism that is pure $\varepsilon$-DP and scales with $L_2$-sensitivity. Conversely, some $(\varepsilon,\delta)$-DP mechanisms scale with $L_1$-sensitivity, like the truncated geometric distribution from this paper.
However, the most commonly used noise mechanisms used in DP are Laplace noise and Gaussian noise, which respectively scale with $L_1$ and $L_2$ sensitivity; the first one is pure $\varepsilon$-DP while the latter only provides $(\varepsilon,\delta)$-DP. You can find a "visual" representation of why that's the case by looking at the density function of a multi-dimensional Gaussian (top) vs. Laplace (bottom):

This picture is taken from this blog post of mine about Gaussian noise.


Does AES use different keys for each block of plaintext?

TL;DR no it doesn't use different keys for each block; the key stays the same. AES has been designed to be able to encrypt many blocks with the same key.

AES is a block cipher. As a block cipher it can only encrypt / decrypt (or permute) one block of plaintext / ciphertext at a time. How you encrypt 4 concatenated blocks of plaintext isn't specified by AES. So in that sense it is impossible to answer your question.

Generally the block cipher AES is however used in a block cipher mode of operation such as CBC. These modes of operation take an already keyed block cipher as parameter. So in a mode of operation the key stays the same. This also goes for the derived sub-keys or round keys that are calculated during initialization of the block cipher that performs the key schedule.

In principle you could create a mode that uses different keys for each block encrypt (probably using some kind of calculation to calculate each "block key" from a key seed). That would however require you calculate the key schedule for each block. Furthermore, it would likely allow related key attacks, to which at least AES-256 is susceptible.

Proposing such a mode during a crypto conference is probably not advisable.

If the 16 byte blocks are separate messages then it is of course also possible to use the same key. If you're not concerned about leaking information about equality of the plaintext then you can also simply use the block cipher directly.

The modes of operation specified for block ciphers such as CBC, GCM (and so on) also work for smaller messages. Note that you need to use an IV if you want to reuse the key for most modes of operation. Using an IV is required for modes of operation that provide CPA security.

If you want to use different keys then that's also possible, for instance by deriving keys from a master key using a KDF.


According to 7-Zip,

  Use ZipCrypto, if you want to get archive compatible with most of the ZIP archivers. AES-256 provides stronger encryption, but now AES-256 is supported only by 7-Zip, WinZip and some other ZIP archivers.

So really there is some balance to be played with. Do you require better security at the sacrifice of compatibility or more compatibility at the sacrifice of security?

According to the Info-Zip FAQ, it sounds like ZipCrypto is pretty weak. Keep that in mind when making your decision.

Note: The link on Info-Zip FAQ to the publication is broken, you can find the file on A Known-Plaintext Attack on the PKZIP Stream Cipher


How do I multiply a Twisted Edwards point in Montgomery space?

I finally got the answer from Hacker News.  My mistake came from the conversion code.  I used a formula from Wikipedia, which is slightly different from the correct one. Simply put, I missed a multiplication by a constant (specifically, the square root of -486664,  or 6853475219497561581579357271197624642482790079785650197046958215289687604742 —the other square root also works.)

The correct code for converting to Montgomery format is this (note the inversion, needed to ensure that z1 == 1, which allows a faster Montgomery ladder):

// sqrt(-486664), in 26/25 bit limbs.
fe K = { 54885894, 25242303, 55597453,  9067496, 51808079,
         33312638, 25456129, 14121551, 54921728,  3972023 };

// Actual conversion
fe x1, y1, z1, x2, z2, x3, z3, t1, t2, t3, t4;
fe_sub(z1, q->Z, q->Y);  fe_mul(z1, z1, q->X);  fe_invert(z1, z1);
fe_add(t1, q->Z, q->Y);
fe_mul(x1, q->X, t1  );  fe_mul(x1, x1, z1);
fe_mul(y1, q->Z, t1  );  fe_mul(y1, y1, z1);
fe_mul(y1, K, y1);  // missing multiplication
fe_1(z1);

(Even though we use projective coordinates, the Montgomery ladder is faster when it can assume z1 is equal to one.  This compensates the cost of the inversion.)

The correct code for converting back to Twisted Edwards format is this:

fe_sub(t1  , x1, z1);
fe_add(t2  , x1, z1);
fe_mul(x1  , K , x1);  // missing multiplication
fe_mul(p->X, x1, t2);
fe_mul(p->Y, y1, t1);
fe_mul(p->Z, y1, t2);
fe_mul(p->T, x1, t1);


I figured out an Answer, https://pypi.org/project/eciespy/, this library uses private/public key generated from Sep256k1 curve for encryption and decryption.

from ecies.utils import generate_eth_key
from ecies import encrypt, decrypt
k = generate_eth_key()
prvhex = k.to_hex()
pubhex = k.public_key.to_hex()
data = b'this is a test'
decrypt(prvhex, encrypt(pubhex, data))
b'this is a test'


Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$?

We hope that there is no efficient method (without using knowledge of $x$ or $y$)
Here's why: if you can solve that problem, you can solve the (computational) Diffie-Hellman problem; here's how:

Suppose that you did have an Oracle that, given $g, g^x, g^{xy}$, returned $g^y$

Then, you can use that to create an Oracle that, given $h, h^x$, returned $h^{x^{-1}}$
Here's how, you'd call your Oracle with $g=h, g^x=h^x$ and $g^{xy} = h$.  These conditions hold only if $x^{-1} = y$, and so when your Oracle returns $g^y$, that's also $h^{x^{-1}}$

With that Oracle, you can generate a squaring Oracle (given $h, h^x$, return $h^{x^2}$, and with that, computing DH is straight-forward.


Minimizing size of signed message with discrete-log scheme

This only answers part of the question, but here goes:

Classical Schnorr signatures start (in my notation, which I think will be helpful here) with a field $\mathbb F$, a linear map $f: \mathcal W \to \mathcal V$ over $\mathbb F$-vector spaces and a hash $H$ with codomain in $\mathbb F$. For simplicity let's take $\mathcal W = \mathbb F$. I'll use capital letters for elements of $\mathcal V$ and small ones for field elements. Intuitively, elements of $\mathcal V$ take more bits to represent than field elements.

The finite field implementation is to take primes $p, q = (p-1)/2$ and set $\mathbb F = \mathbb Z_q$,  $\mathcal V$ is an order-$q$ subgroup of $\mathbb Z_p$ generated by some $g$, vector addition is $v \oplus w := v \cdot w \pmod{p}$ and scalar multiplication (that makes the whole thing into a vector space) is $(x, V) \mapsto V^x \pmod{p}$. The linear function is $f(x) := g^x \pmod{p}$ for vanilla Schnorr.

For elliptic curve implementations (DSA, ECDSA, EdDSA) $\mathbb F$ is a finite field and $\mathcal V$ is a group defined over an appropriate elliptic curve, with point addition serving as vector addition and scalar multiplication of $x$ with $V$ is point-adding $V$ to itself $x$ times.

In both cases,

A keypair is a pair $(x, Y = f(x)) \in \mathbb F \times \mathcal V$.
To sign $M$ (which can be any bitstring), you pick a random $r \in \mathbb F$, set $A = f(r)$, $c = H(Y, A, M)$ and $s = r + cx$.
The "$4w$" version of the signature is $(A, s) \in \mathcal V \times \mathbb F$ whereas the "hash compressed" or "$3w$" version is $(c, s) \in \mathbb F \times \mathbb F$, since field elements are smaller than $\mathcal V$ elements.
The verification equations in both cases are $c = H(Y, A, M)$ and $f(s) = A + c \cdot Y$.

Which brings me to two recommendations.

In the hash-compressed version, the signature consists only of field elements, so it should not matter for signature size if you choose a finite-field or EC implementation: the size of keys (field elements) is the same for both at the same security level on keylength.com. What EC buys you is shorter $\mathcal V$ elements, which is irrelevant here. I'd personally go with Ed25519 just because I like it.
The probability of forging a proof is commonly given as $1/|\mathbb F|$ but really it's the inverse of the size of the codomain of the hash. While $s$ has to be a full field element, you can truncate the hash value $c$ to any smaller number $k$ of bits as long as you're happy with a lower soundness factor of $2^{-k}$.

EDIT: You can also do the $z_s + z_v$ bits thing here of course, but it seems like it doesn't buy you much. I thought for a bit how I'd prove the security of the version where the verifier iterates over $z_v$ "omitted" bits and the best I could come up with is a union bound, so by omitting $z_v$ bits you lose $z_v$ bits of security and force the verifier to do $2^{z_v}$ times the work, in exchange for transmitting $z_v$ fewer bits. Shortening the hash output by $z$ bits also loses you $z$ bits of security, but doesn't cause anyone more work.
(If you can prove that you can fix or omit some bits without losing that many bits of security, then of course this option becomes attractive again.)


Using the security definition in the malicious model to prove security in the semi honest model

No, you cannot do this, because, as explained further in the book, security against malicious adversaries does not imply security against semi-honest ones.


What's the difference between block ciphers and symmetric-key encryption?

Symmetric-key scheme just means use a key to encrypt and decrypt the same message.

Block ciphers just means encrypt your data in many small bits blocks (which can vary in size with padding randomized technique).


Does the size of a ECDSA key determine the hash algorithm?

No, in general the hash isn't determined by the curve definition by NIST. Reasonable mappings of course exist (for a 224 bit curve you would probably use a hash with output size of 224 such as SHA-224). The hash used should however be specified by the protocol itself.

The ECDSA key size as indicated by the -b of the openssh argument is linked to the hash algorithm used. This is defined in section 6.2.1 of the RFC 5656:

  The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified
     for use with the SSH ECC public key algorithm.

  The hashing algorithm defined by this family of method names is the
     SHA2 family of hashing algorithms [FIPS-180-3].  The algorithm from
     the SHA2 family that will be used is chosen based on the size of the
     named curve specified in the public key:

+----------------+----------------+
|   Curve Size   | Hash Algorithm |
+----------------+----------------+
|    b <= 256    |     SHA-256    |
|                |                |
| 256 < b <= 384 |     SHA-384    |
|                |                |
|     384 < b    |     SHA-512    |
+----------------+----------------+

Note that currently you can only use the P-256, P-384 and P-521 (secp256r1, secp384r1 and secp521r1) prime curves defined by NIST in SSH. So the argument for the bit size also determines the domain parameters used.