RSA: large private exponent often yields large public exponent

For any integer $k>1$, the function $F$ onto $\Bbb Z^*_k$ (the subet of integers in $[0,k)$ that are coprime with $k$ ) defined by $x\mapsto x^{-1}\bmod k$ is a permutation of $\Bbb Z^*_k$.

For any finite set $\Bbb S$ and any permutation $F$ of $\Bbb S$, if $x$ is uniformly random on $\Bbb S$ then $F(x)$ is uniformly random on $\Bbb S$.

It follows that if we choose $d$ uniformly randomly in $\Bbb Z^*_{\varphi(N)}$ (which is a fair model of choosing a large random $d$ ), and compute $e=d^{-1}\bmod\varphi(N)$, then the resulting $e$ is uniformly random on $\Bbb Z^*_{\varphi(N)}$. The average of $e$ is going to be about $\varphi(N)/2$, thus not "small" in the sense that has in RSA for "small $e$".

In an RSA context, $\log_2(N)\approx\log_2(\varphi(N))$. If $N$ is $n$-bit, a random element of $\Bbb Z^*_{\varphi(N)}$ is going to be $k$-bit or less with probability less than $2^{k-n+1}$, thus very seldom "small" (e.g. for 2048-bit $N$, 128-bit or less with probability $2^{-1919}$ ). That applies to $e$ for a random $d$ (large or not).

Summary: Choosing $d$ at random and computing $e$ from that gives overwhelming assurance that $e$ is not small. There's no such thing as large $d$ implying large $e$.

Note: the question is correct when stating that choosing $e$ small then $d=e^{-1}\bmod\varphi(N)$ ensures that this $d$ is large. But it is wrong in assuming that a large $d$, or/and a large $e^{-1}\bmod\varphi(N)$, is enough that the attacks alluded to don't work (this is referring in particular to Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

For example, we could chose $r$ a random prime of $\frac27\log_2N$ bits, then $e=(\varphi(N)/2+r)^{-1}\bmod\varphi(N)$, then $d=e^{-1}\bmod\varphi(N)$. That $d$ is $\varphi(N)/2+r$, thus about 1 bit less than $N$, thus large. However $r$ is another working $d$, and is consistently small enough to allow the attack.

What matters to prevent the attack is that there exists no small positive working $d$, in other words that $e^{-1}\bmod\lambda(N)$ is not small, where $\lambda(N)$ is the the Carmichael function, with $\lambda(N)=\varphi(N)/\gcd(p-1,q-1)$ when $N$ is the product of two distinct primes $p$ and $q$. That is insured when $e$ is small and the factors of $N$ chosen randomly and mostly independently, making it unlikely that $\gcd(p-1,q-1)$ is unduly large.


multi-theorem vs single-theorem for non-interactive zero knowledge

In a zero-knowledge proof system, there are three main properties to be satisfied: completeness, soundness (knowledge soundness for zkpok), and zero-knowledge (or weaker notion such as witness indistinguishability).
one of soundness and zero-knowledge is computationally error-bounded, i.e. you can either than a (computational soundness + statistical zk) combo which is known as ZK Argument, OR a (statistical soundness + computational zk) combo which is referred as ZK Proof.
At the beginning of the protocol, there's usually a Setup step where proving keys and verification keys are generated based on the security parameter given. In NIZK, these proving keys and verification keys are part of the Common Reference String (CRS).
Depending on the construction, repetition of the protocol (i.e. run the protocol multiple times under the same proving and verification key) might hurt soundness or zero-knowledge. "hurt" as in the error bound just increase, making it prone to violation. For some proof system, repetition might violate the property and thus totally break the protocol.
single-theorem basically guarantee those three properties and their error bound for a single round.
multi-theorem basically mean reusing proving & verification keys from Setup for unbounded number of rounds/repetition/theorem without compromising the soundness or zk. (i.e. reuse CRS for many $x \in L$)


Is it safe to use the same key for different variants of the HMAC-SHA algorithm?

So, the answer to your question is that while it is recommended that you never reuse keys for different algorithms, it is quite unlikely that different hashes in HMAC would interact badly.

However, that does not mean what you are planning is the way to go. It makes little sense to change the strength of the authentication based on the length of the message, unless the message length directly correlates with the security level you expect. And even if that is something you want, there is no real advantage to using different HMAC hashes.

Instead, you should pick either SHA-256 or SHA-512 and use only that hash for HMAC. You can truncate the authentication tag to the desired length, which can vary with message length. However, you must make sure an attacker cannot simply use a shorter tag in all situations. And it is not really required, since even a 64-bit tag is usually considered sufficient. So you should likely just pick one length you are comfortable with.

Oh, and a 128-byte key is overkill. 256 bits is sufficient.


Is container format relevant to security of encrypted message inside?

Converting the comments to an answer…

Ricky Demer:

  "algorithms used" should be stored with the key(s).  "compression of plaintext used, probably a user supplied tag" should go into the MAC.

Maxthon Chan:

  That is, algorithm should not appear in the container at all, and everything that is not MAC itself should be included in MAC?

Ricky Demer:

  Yes. Also note that compression may be problematic.

Maxthon Chan:

  I forgot the asymmetrically encrypted symmetric key may appear in the file as well as key.bin. How to deal with that?

Ricky Demer:

  If you're using public keys too, then you should probably use digital signatures, possibly instead of a MAC.


Choose a random number that is different from a bunch of other secret numbers

I think this would work, although whether it's practical is another matter. For large $x$ it won't be. It's basically an application of mental-poker.

First, choose a secure commutative encryption algorithm that is not vulnerable to known plaintext or chosen ciphertext attacks.

Everyone generates a random encryption key.
Everyone but Alice uses their key to encrypt their secret unique number.
Alice uses her key to encrypt every item in the list $[0,...,x]$, except her own number. She then shuffles the list.
Everyone passes their encrypted secret number/list to the next person (e.g. clockwise), who encrypts it, shuffling the list when they have it. Repeat until all the numbers and the list have been passed around. At that point both Alice's list and everyone else's number has been encrypted by everyone.
Remove all the encrypted numbers from the list. Since the encryption is commutative, each encrypted number will match itself in the list, but because everyone has shuffled the list, they don't know what those numbers originally were.
Pick the first number from the list. Have everyone decrypt it with their key and pass the result around, until they've made a whole round. Now everyone should have the same random number, which they can verify by comparing their results.

(If the number would only be decrypted once, the final decrypter could cheat and pick any number, hoping it doesn't match the others'.)

I.e. with your example values:

Alice: key $a$, Bob: $b$, Eve: $e$
Bob: $E_b(52)$, Eve: $E_e(193)$
Alice: $[E_a(0), ... E_a(17), E_a(19), ... E_a(200)]$, shuffle.
Alice $\mapsto$ Bob: $[E_a(i), ...]$, Bob: $[E_b(E_a(i)), ...]$, shuffle.

Bob $\mapsto$ Eve: $E_b(52)$, Eve: $E_e(E_b(52))$.

Eve $\mapsto$ Alice: $E_e(193)$, Alice: $E_a(E_e(193))$.

Alice $\mapsto$ Bob: $E_a(E_e(193))$, Bob: $E_b(E_a(E_e(193)))$.

Bob $\mapsto$ Eve: $[E_b(E_a(j)), ...]$, Eve: $[E_e(E_b(E_a(j))), ...]$, shuffle.

Eve $\mapsto$ Alice: $E_e(E_b(52))$, Alice: $E_a(E_e(E_b(52)))$.
Now the list, $E_a(E_e(E_b(52)))$ and $E_b(E_a(E_e(193)))$ can be revealed and the Bob and Eve's numbers removed. Since the encryption is commutative, $E_a(E_e(E_b(52)))$ will match $E_e(E_b(E_a(52)))$ somewhere in the list, as will $E_b(E_a(E_e(193)))$.
Everyone takes the first number in the list, say $E_e(E_b(E_a(42)))$. They each decrypt it, e.g. Bob: $D_b(E_e(E_b(E_a(42)))) = E_e(E_a(42))$. They pass them around like in step 4, so that eventually e.g. Bob gets $E_b(42)$, which he can decrypt and announce, comparing to Alice and Eve's results.


Assuming as you specified that $X_1$ is $81$ and $X_2$ is $65$.
$X_1 || \ldots || X_n$ is your key stream in bits.

So you need to convert 81 and 65 into bits.

$81 = \texttt{01010001}$
$65 = \texttt{01100101}$

Thus your key stream is : $\texttt{01010001 01100101}$

You are attacking a 8 bit LFSR and we will assume Galois mode (because it is easier in this case).

The diagram of such LFSR is:

+-------------+-----------+-----------+-----------+------------+-----------+-----------+------------+
|             |           |           |           |            |           |           |            |
|            *a          *b          *c          *d           *e          *f          *g            |
|             |           |           |           |            |           |           |            |
|    +-----+  |  +-----+  |  +-----+  |  +-----+  |  +-----+   |  +-----+  |  +-----+  |  +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |  |  |     |   |  |     |  |  |     |  |  |     |   |
+--->+  x0 +---->|  x1 +---->|  x2 +---->|  x3 +---->|  x4 +----->   x5 +---->|  x6 +---->|  x7 +-------> ...
     |     |     |     |     |     |     |     |     |     |      |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+      +-----+     +-----+     +-----+

where a b c d e f g are constants set to 0 or 1 to determine whether a bit influence the next result.

You must notice that the output is actually decided 8 rounds before being seen.

Thus you can see the LFSR as following parallel formulas:

$out \leftarrow x_7$
$x_7 \leftarrow x_6$
$x_6 \leftarrow x_5$
$x_5 \leftarrow x_4$
$x_4 \leftarrow x_3$
$x_3 \leftarrow x_2$
$x_2 \leftarrow x_1$
$x_1 \leftarrow x_0$
$x_0 \leftarrow f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7)$

where
$$f(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7) = \\
(x_0 \land a) \oplus
(x_1 \land b) \oplus
(x_2 \land c) \oplus
(x_3 \land d) \oplus
(x_4 \land e) \oplus
(x_5 \land f) \oplus
(x_6 \land g) \oplus x_7$$

From this you can deduce:

$f(1,0,0,0,1,0,1,0) = 0$ and the LFSR returned $0$
$f(0,1,0,0,0,1,0,1) = 1$ and the LFSR returned $1$
$f(1,0,1,0,0,0,1,0) = 1$ and the LFSR returned $0$
$\ldots$
and finally:
$f(0,1,0,0,1,1,0,1) = 1$ and the LFSR returned $1$

Notice that the first column is the second part of the stream : $\texttt{011}\ldots \texttt{1}$ and the second column (LFSR returned) is your first part of the stream: $\texttt{010}\ldots \texttt{1}$

Intermediates steps not provided as it is your homework.

Thus this gives you 8 equations to solve with 7 variables ($a,b,c,d,e,f,g$).

Equations not provided (nor solved) as it is your homework.

From this you have will have recovered the complete state and will know the formula to compute the next outputs bit, giving you full prediction on the stream to attack $C_1, \ldots, C_n$.


Can i use Babai algorithm in q-ary lattice

No, you can't.

Babai's Nearest Plane Algorithm is supposed to receive a basis of the lattice, and $\mathbf{A}$ is not the basis of the modular lattice that it spans. If you give Babai's algorithm the matrix ${\bf A}$, it will work over the lattice $ \mathcal{L}({\bf A}) := \{ {\bf A}{\bf x} : {\bf x} \in \mathbb{Z}^n  \}$ instead of $\mathcal{L}_q({\bf A}) $. Therefore, it will probably output wrong answers.

For instance, if you take a vector $\mathbf{t} = (q, q, ..., q)$, then $\mathbf{t} \in \mathcal{L}_q({\bf A})$, therefore, Babai's algorithm must output $\mathbf{t}$ itself. But it is likely that $\mathbf{t} \not \in \mathcal{L}({\bf A})$, so, Babai's algorithm will output some vector different from ${\bf t}$.


If the ciphers are different, with independent keys, you can say that it is at least as strong as the first cipher. If the ciphers commute, like with stream ciphers, you can even say that it is at least as strong as the strongest. See Cascade Ciphers: The Importance of Being First.

That's really all you can say in general.

In practice, the combinations you suggest are not cryptographically secure. You would need at least one secure cipher in the mix to have reason to believe it would be. (Though that's not strictly required in theory: a particular combination of insecure ciphers could be secure.)


Output of using the same key in all 3 boxes of 3DES

Traditionally, 3DES is configured in a mode called EDE, which means "Encrypt, Decrypt, Encrypt". This means that your encryption operation looks like this: $c = E(D(E(m, k_1), k_2), k_3)$. As it turns out, if all three subkeys are independent, the security of the system is not impacted by the second operation being a decryption.

The reason for this construction is a historic one. When 3DES was being introduced, people wanted a way to fall back to a "legacy" mode which amounted to just plain DES. This is handled through keying modes, of which there are three:

Keying mode 1: All three subkeys are independent (which implies probabilistic inequality, though some implementations may enforce $k_1 \neq k_2 \neq k_3$ explicitly)
Keying mode 2: $k_1$ and $k_2$ are independent, but $k_1 = k_3$.
Keying mode 3: All three subkeys are equal, i.e.e $k_1 = k_2 = k_3$.

In keying mode 1, you get full 3DES with a 168-bit key (3 × 56-bit). In keying mode 2, you get a 112-bit version of 3DES (2 × 56-bit), though this keying mode is less commonly used in practice. In keying mode 3, the first two steps cancel out, leaving you with just DES:

$$\require{cancel}\cancel{a = E(m, k)}$$
$$\cancel{b = D(a, k)}$$
$$c = E(b, k)$$


This is very similar to establishing transport security with entity authentication. In other words, this would be much like TLS, except that in this case the client seems to require authentication rather than the server.

Still, using TLS with client authentication would probably solve your needs. Sure, it would also encrypt the streams, but that should not necessarily pose a problem. Otherwise you could replace the encryption and authentication with just HMAC and skip encryption.

Otherwise it would be a very good idea to study the TLS handshake and work out how the entity authentication works and how the shared session keys are established. Once the session keys are established they can be used to authenticate the records / messages in the stream. These are just blocks of data that together form the stream.

Beware that designing / implementing transport security is fraught with danger and should not be attempted without a very good understanding of the subject.

Note that SSH is usually more geared towards client authentication rather than TLS, which requires server authentication. So SSH might be a better transport security protocol when it comes to fulfilling the requirements. I'm however less at home with the current security details of SSH.

Another option would be to sign the data before sending (application level security rather than transport security). This would let you verify that the stream was delivered by a certain entity even after transport. If this is a valuable property depends on your usage scenario; it might be a very dangerous one as well - others would also be able to verify that it was delivered by the entity that signed it after all.

This seems to be the current road you're on; however in this scenario you might as well sign the whole stream / file rather than blocks. Otherwise you would just be designing a pretty bad transport mode security without forward secrecy, a lot of overhead and a proprietary messaging layer.


Can there be two hash functions without common collisions?

No, in general, there will always be a pair of inputs that will collide for both hash functions.  Specifically, if the hash functions have fixed sized outputs, and both take an arbitrary input which is at least as long as the sum of their outputs, then there will be bitstrings $X$ and $Y$ with $X \neq Y$, $A(X) = A(Y)$ and $B(X) = B(Y)$

Here is a simple demonstration that such a pair must exist: let us assume that $A$ generates an output which is $n$ bits long, while $B$ generates an output which is $m$ bits long, and further assume that $n, m > 0$.

Now, consider the set of all possible bitstrings of length $n+m$, along with the empty bitstring (or, if you don't like that, pick any bitstring shorter than $n+m$).  This set has size $2^{n+m}+1$.  If we apply the hash function $A$ to each member of the set, there are $2^n$ possible outputs, and hence (by the pigeon-hole principle), there must be some output with at least $2^m+1$ preimages.  Let us pick such an output, and call the subset when generates that output subset $W$.

Now, let us consider applying the hash function $B$ to each member of $W$; $W$ has size at least $2^m+1$, and $B$ has $2^m$ possible outputs; hence there must be two elements $X$ and $Y$ of $W$ with the output.

This pair $X$ and $Y$ is a common colliding pair for $A$ and $B$.


How to decrypt Pohlig-Hellman cipher if e and (n-1) aren't relatively prime

It is essentially the same as the answer I gave in How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?, with the same restrictions ($e$ assumed prime, $e^2$ assumed not to be a divisor of $p-1$), with the sole change being that $\lambda = p - 1$.
It's easy enough to cover the composite $e$ case (factor $e$ into primes $e = r_1 r_2 … r_n$, and then find solutions for $c = m^{r_1 r_2 … r_n}$ by inverting each $r_i$ individually.
The other case $e^2$ is a divisor of $p-1$ is a lot tougher, and probably needs a different approach...


The function, in this case, is collision-resistant but despite this, is it still possible to break the EUF-CMA of RSA-FDH?

Yes, because the requirement for security is the hash function acting like a random oracle and not it being collision-resistant.

To illustrate this, consider the "hash function" $H(x)=x$ which is clearly collision resistant. Yet, RSA-FDH instantiated with this hash is not secure as it literally is textbook RSA, which suffers from the usual small-exponent and homomorphic attacks (which also apply when $H(x)=3x\bmod N$).

This could of course raise the question "why, do we need this stronger assumption?". And the main reason is that the "RSA problem" - extracting $x$ from $x^e\bmod N$ for appropriately chosen $N$ and $e$ - isn't always hard. It is only hard when $x$ is chosen uniformly at random, which is kind of what the hash function is supposed to do here.


AEAD using AES-CBC and MAC: how to order the input to the MAC

This part of the standard (at the end) explains why the length of the authenticated data is at the end, namely to ensure a unique input to the MAC for all pair of ciphertext and authenticated data:

During the decryption process, the inputs A and C are mapped into the
input of the HMAC algorithm.  It is essential for security that each
possible input to the MAC algorithm corresponds unambiguously to
exactly one pair (A, C) of possible inputs.  The fact that this
property holds can be verified as follows.  The HMAC input is X = A
|| C || len(A).  Let (A,C) and (A',C') denote two distinct input
pairs, in which either 1) A != A' and C = C', 2) C != C and A = A',
or 3) both inequalities hold.  We also let X' = A' || C' || len(A').
In cases 1 and 2, X != X' follows immediately.  In case 3, if len(A)
!= len(A'), then X != X' directly.  If len(A) = len(A'), then X != X
follows from the fact that the initial len(A) bits of X and X' must
be distinct.

in your case C is just the IV and remaining cipher text, of course; in the standard IV is explicitly part of the C.


The certificate is not encrypted.  It contains signatures (basically hashes) that are encrypted with the private key.  The public key can decrypt that and the hash can be verified.  In SSL/TLS there is a signature that the client supplies via private key to prove they are the owner, and the CA has signed it the cert with their private key, which can be verified using a CA cert you mark as explicitly trusted.


Absorbing r + c bits in first round of a sponge function

Here's how to create a second preimage with your modification.

We'll assume that the original message is at least $2r+c$ bits long, and consists of an initial message segment $M_0$ ($2r+c$ bits) and the rest of the message $M_1$.

After processing block $M_0$, the sponge state will be some setting, with the public $r$ bits at some value $R_0$ and the capacity $c$ bits at some value $C_0$.

Concatenate the values $R_0$ and $C_0$ to be an initial block, and then prepend that to $M_1$, giving $R_0 || C_0 || M_1$.

When hashing that, the sponge construction will take the $R_0$ and $C_0$ bits and set the initial Sponge state to be precisely what it was after the initial processing of $M_0$.  Then, it'll process the rest of the message $M_1$; because the state is the same, it'll perform the same operations, and generate the same hash.

And, because the lengths of the two messages are different, the messages are different, and thus we have generated a second preimage.

The OP since asked about the security if the length of the input is fixed.  Well, if the length of the output $n$ is at most $r$ (i.e. one squeeze cycle), then it is easy to generate preimages.  The method is straight-forward; you start with the final state (with the known $n$ bits in the $r$ region), and arbitrarily select values for the other $r+c-n$ state bits.  Then, you run the hash backwards (using the inverse permutation, and arbitrary settings for intermediate message blocks) until you get to the initial state, and then you select a message where the first $r+c$ bits are that initial state, and the rest of the message blocks are those arbitrary message blocks you selected.

If we have $n > r$, this still can be used to reduce the amount of work to find a preimage by a factor of $2^r$

The bottom line: the entire security of SHA-3 comes from the capacity bits; letting the adversary arbitrarily select them breaks things bad...


How can I find the multiplicative inverse in the first transformation of the SubBytes() transformation in AES?

They are referring to the formula for Bézout's identity which calculates the greatest common divisor, extended to a finite field, where 1 is the multiplicative neutral element.

  From the relation $b(x)a(x)+m(x)c(x)=1$, $$b^{-1}(x)=a(x)\mod m(x)$$ I cant figure out what $a(x)$ and $c(x)$ are?

In this case, $b(x)$ is the element for which the inverse is desired, and $a(x)$ is the coefficient for some $c(x)$ that results in the equation being correct. Since $a(x)$ must be in the field, it is reduced modulo $m(x)$, becoming the inverse of $b(x)$. The actual calculation of the extended Euclidean algorithm does not require $c(x)$ to find $a(x)$, but it must exist in the formula for the reduction above to be correct:

$$b(x)a(x)+m(x)c(x)=1$$

$$(b(x)a(x) \mod\ m(x)) + (m(x)c(x) \mod\ m(x)) = 1 \mod\ m(x)$$

$$m(x)c(x) \mod\ m(x) = 0$$

$$b(x)a(x) \mod\ m(x) = 1 \mod\ m(x)$$

$$a(x) \mod\ m(x)={1/b(x)}\mod\ m(x)$$

$$a(x) \mod\ m(x)=b^{-1}(x)$$

Any resultant inverse can be multiplied by $b(x)$ to check for correctness, as the result should be 1 modulo $m(x)$. In practice, the multiplicative inverse is calculated using log/antilog tables for non zero elements:

$$a(x) \mod\ m(x)=log^{-1}(255 - log(b(x)))$$

Since the tables are calculated using exponentiation modulo $m(x)$, the resultant $a(x)$ is already reduced and within the field.

Since the inverse is only used in calculation of the sbox, it is not used in most AES implementations, since the precalculated sbox is stored as a table and not generated on the fly.


Why is password recovery so slow for Whirlpool hash, when compared with others?

how much faster can i recover my password (20+ characters) from
  knowing nothing about it (it's been years since i last used it) using
  a gpu instead?

According to this benchmark, a single Nvidia Tesla V100 (the best GPU commercially available) will hit 94kH/s on that specific mode (search for 6231 on that page) which is about 300x as fast as your CPU and of course you can just use multiple GPUs. For example on Amazon's cloud services, you can have up to 8 such GPUs per VM.

Note however, if you really used a random 20+ character password, there are at least $2^{94}$ possible passwords (if you have used 20 lower case characters only) and testing this amount of passwords is infeasible (and would require $2^{77}$ GPU-years).

  I'm just curious about why bruteforce takes so much longer on the
  whirlpool hash than it does on the others

This is hard to answer. It may be that not a significant amount of effort has been invested in optimizing the Whirlpool implementations, because it's a somewhat rarely seen hash function. It may be that the huge amounts of table-lookups that Whirlpool apparently requires slow down the operations imensely compared to the register-fitting other hash functions.


Yes, It is what you understood. You use the same key for each encryption.

If you think that they used different keys for each TDES (3DES) they need to store one million keys. This is not practical for the attacker but also for them.

It can also be written as $c = \operatorname{TDES}^{(1000000)}_k(m)$

The point in the section distinguishing these iterated from a random permutation and possible attacks that can be faster than brute-force.


What Are Advantages and Disadvantages of SHA-256?

All three of the hashes you list serve very different purposes. Asking what their relative advantages and disadvantages ar is like asking about the same about a screwdriver, hammer, and drill.

SHA-2 is a cryptographic hash function, and is typically a building block for other cryptographic constructs. In satisfying the requirements of cryptographic hash, it's a one-way function that is deterministic, fast to compute, resistant to pre-image and second-preimage attacks, and is collision resistant.

scrypt is a password-based key derivation function. It's used to turn a low-entropy password into a cryptographic key or verifier with effectively higher entropy by being intentionally slow to compute. It's tunable to require larger amounts of CPU and/or memory as technology advances, making hardware dedicated to computing it en masse expensive.

X11 from what I can gather is a proof-of-work function for blockchain-based currencies. It appears to be little more than inelegantly mashing of a bunch of unrelated hash functions together in the naïve hope that that will somehow make it ASIC-resistant and more secure. I don't think it's received any analytic attention from cryptographers.


[Copy of my answer in another community:] In the RC6 specification (see de.wikipedia.org/wiki/RC6) S[*] designates an array of 2r+4 round keys, whose size in bits you can choose in the range [0,2000]. It is not an array of 2r+4 elements (each a word of 4 bytes).


In your construction, if $H_0 = H_1$ (same function), then your $H_{\circ}$ is constant and equal to $0$. More generally, that kind of construction relies on the two underlying hash functions to be "different" from each other in a way which is very hard to define properly, let alone achieve. If $H_0$ and $H_1$ are independent random oracles, then most constructions are fine; but, there again, random oracles don't really exist.


No, A is not true.

Suppose that $G_1$ is a secure PRG and $G_2(s) = G_1(s) \oplus 1$, obviously $G_2 \neq G_1$ and $G_2$ is a secure PRG.

You can see that $G(s) = G_1(s) \oplus G_2(s) = G_1(s) \oplus G_1(s) \oplus 1 = 1$ which is obviously not a secure PRG.

Now you have a hint. You should think the rest of the problems.


Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?

What I don’t get is why the complexity became quadratic in linear case?

Well, in linear cryptanalysis, for each input, we get a bit with a bias of $0.5 \pm \epsilon$, and we need to determine if that bias is $0.5 + \epsilon$ or whether it is $0.5 - \epsilon$
If we were to query a random bit (that is, one with no bias) $n$ times and sum the results, we're going to get a value $0.5n + \lambda \sqrt{n}$, for some distribution $\lambda$ with a standard deviation around 1 [1]; it'll take around $\epsilon^{-2}$ samples for the bias that we're trying to measure to be detectable over the $\lambda \sqrt{n}$ noise that's inherent in the system.
This 'we need to get over the noise within the system' effect doesn't occur with differential cryptanalysis, because in DC, we expect the differential to hold over a number of bits, and so we can essentially ignore the case that the differential didn't hold internally, but the differential just happened to hold on the output.
Actually, if we're working with a truncated differential, this may not be quite as true, and in that case, we may need to worry about false positives, giving us an analysis that's closer to the linear cryptanalysis case...

[1]: Actually, the standard deviation is $0.5$; the slightly smaller expected amount of noise doesn't change the analysis.


What does $x^{1/e}$ mean in cryptography in this open butterfly structure?

Squeamish Ossifrage is correct. This is the power map $x\rightarrow x^t$ where $te\equiv 1 \pmod{2^n-1}$ and the underlying field is $GF(2^n).$

The subject of power maps and when they give permutations with nice properties is quite well studied, and this is a paper along those lines.


Does chaining random number generators lead to loss of randomness?

The practice you describe is acceptable and secure.  As long as each of the cryptographic PRNGs has no weaknesses and you use a seed of sufficient size, this is safe.

Whether it is desirable is a separate question.  Do you really have a valid reason why you need to do this?  If not, it's just adding unnecessary complexity and extra "moving parts" that can go wrong somehow.


Is this a novel secret splitting method, or a different view of an existing one?

I haven't seen this one before before, but keep on reading...

It would appear to work, but you need to be a bit careful, specifically with your $mxy$ multipliers; it should be apparent that not just any random set of values would work there.

I believe that a necessary and sufficient condition would be "if you logically add a $(1, 0, 0, ..., 0)$ row to the matrix, then all submatricies consisting of $N$ rows from this extended matrix must be nonsingular" (where $N$ is the threshold number of shares); if this condition does not hold, then either there is a group of $N$ valid shares that cannot reconstruct the secret, or there is a group of $N-1$ valid shares that can.  Proving it is sufficient is straightforward; proving that it is necessary would appear to require going through a number of subcases, depending on what subset of rows was linearly dependent, and whether that subset included the artifical $(1, 0, 0, 0, ..., 0)$ row.

Blom's key distribution scheme has exactly that same requirement to its internal matrix; his key distribution scheme isn't a secret sharing scheme; instead, it's a way to distribute key shares so that any two parties can agree on a key, and no set of $N-1$ other parties can recover it.

One suggestion to make Blom's scheme work was to use the matrix:

$$
\begin{matrix}
1^0 & 1^1 & 1^2 & 1^3\\
2^0 & 2^1 & 2^2 & 2^3\\
3^0 & 3^1 & 3^2 & 3^3\\
4^0 & 4^1 & 4^2 & 4^3\\
5^0 & 5^1 & 5^2 & 5^3\\
6^0 & 6^1 & 6^2 & 6^3\\
\end{matrix}
$$

(where $1, 2, 3, 4, 5, 6$ are distinct nonzero field elements)

This matrix meets the criteria I mentioned, and works great for you.  However, if you look at it closely, it you use it, well, you've just rediscovered Shamir's original method :-)


To what extent is WhatsApp's statement on secure messaging realistic?

So my question is, if they are the ones who encrypt this, then why can't they also decrypt it?

Because it’s not them encrypting your message, it’s the App on your device… which is why it’s called End-To-End encryption.

According to the security whitepaper (PDF), WhatsApp uses the Noise Protocol Framework which is based on the Signal protocol (formerly known as “Axolotl”). The Signal protocol has been designed by Open Whisper Systems (names like “Zooko” might ring a bell) and  uses strong and well-vetted cryptographic approaches like ECDH using Curve25519. Besides that, WhatsApp additionally encrypts all communications between client and server via – so called – Noise Pipes (see Noise Protocol Framework for more information on that).

Skipping the details to keep it short, it seems as if WhatsApp did its homework and chose a well-vetted approach to provide encryption et al.

But there’s that little thing with WhatsApp that indeed represents a bit of a problem when looking at it from an InfoSec and/or cryptographic point of view: WhatsApp was, is, and remains closed source up until today. Practically, this means that you can’t really review the actual sourcecode and classify WhatsApp security based on that. So, you can’t really tell how much security it practically might (or might not) offer.

If you’ve ever looked at (or used) Signal as a messaging app, you’ll notice WhatsApp and Signal work in similar ways (read: usage-flow is very alike) which hints at the fact that WhatsApp has indeed implemented what it is saying. Yet, in contrast to Signal (which is open source) you can’t tell if WhatsApp has indeed implemented things correctly and without (let’s just call it) bugs in the code, which might or might not provide room for attack vectors.

All in all, your question uses the correct term: “claim”. That’s all it is and all you can trust in. A “claim” isn’t called “proof” for a good reason… in this case, you can not verify WhatsApp security claims by looking at WhatsApp sourcecode – as that’s unavailable to the public. All you have is their words (aka publications like the security whitepaper) and the fact that close-source WhatsApp somewhat feels like the open-source Signal app. In the realms of cryptography, small errors can (and will) break your neck – which is why I personally prefer to keep using Signal instead of switching to WhatsApp. OTOH, I’m weird… and there’s no real reason to suspect WhatsApp would even think about risking their business by publishing claims they can’t hold. Yet, they don’t provide much reason to trust them either. As Tylo commented correctly: it could all just be propaganda (aka marketing). In the end, it is a company with commercial interests and a close-source product… that somewhat renders “trust” into a “personal opinion” thing.

TL;DR

So, if your question boils down to “Is WhatsApp secure?” I would tend to say “According to their whitepaper, it should be”. If your question boils down to: “Can you prove it?” I’ld have to disappoint with a “No, as proof expects the ability to verify, which we can’t.” And if you want to know the details of “how WhatsApp handles End-To-End encryption and authentication”, check the security whitepaper and the Noise Protocol Framework links at the top of my answer. That should answer all those little cryptographic nit-bits (which are a bit too broad to mention here).


Oblivious Decryption: Decrypting with a private key, without knowing the message

This can be done by exploiting the homomorphic property of RSA.  Let's say Alice's key is $(e,N,d)$ where $e$ is the public exponent, $N$ the modulus, and $d$ the private exponent.

To decrypt $x$, Bob samples $r$ randomly from $\{1,\cdots,N\}$ and computes $xr^e\mod N$ and sends it to Alice.  Alice computes $(xr^e)^d=x^dr\mod N$ and sends it back to Bob.  Bob multiplies by $r^{-1}$ to extract $x^d$.

Note that Alice does not know $r$ and thus cannot determine $x^d$ from $x^dr$.  This does lead to at least one vulnerability: Bob can send Alice whatever he likes.  In particular, he could ask for the decryptions of other private messages to Alice that he somehow acquired.


Hashing list: concatenation vs prepending

The whole issue comes from the fact that regular collision resistant hash functions are defined over binary strings. What you are trying to construct is a collision resistant hash function over a different domain, namely a set of tuples.

To construct a collision resistant hash function for some domain $D$ from a collision resistant hash function for $\{0,1\}^*$ what is necessary is to encode elements of $D$ as elements of $\{0,1\}^*$.
If $\mathsf{H} : \{0,1\}^* \to \{0,1\}^n$ is the original hash function and $\mathsf{E} : D \to \{0,1\}^*$ is an efficient encoding function then $\mathsf{H} \circ \mathsf{E} : D \to \{0,1\}^n$ is a hash function for domain $D$.

However, if it is easy to find collisions in $\mathsf{E}$, then $\mathsf{H} \circ \mathsf{E}$ is not collision resistant, since any collision in $\mathsf{E}$ directly implies a collision in $\mathsf{H} \circ \mathsf{E}$. So to show that $\mathsf{H} \circ \mathsf{E}$ is collision resistant we need that $\mathsf{E}$ is also collision resistant. Since $\mathsf{E}$ does not need to be compressing, the easiest way to ensure that it is collision resistant is to ensure that it is collision free by ensuring that it is a unique encoding.

If $\mathsf{E}$ is a unique encoding, then it is easy to show that $\mathsf{H'} = \mathsf{H} \circ \mathsf{E}$ is collision resistant whenever $\mathsf{H}$ is. Assume towards contradiction that there exists an efficient algorithm $\mathcal{A}$ capable of finding collisions in $\mathsf{H'}$. I.e., $\mathcal{A}$ outputs $x,x' \in D^2$ such that $x \neq x'$ and $\mathsf{H'}(x) = \mathsf{H'}(x')$. By definition of $\mathsf{H'}$ this implies that there are encodings $e := \mathsf{E}(x)$ and $e':= \mathsf{E}(x')$ such that $\mathsf{H}(e)=\mathsf{H}(e')$. And by the fact that the encoding is unique and $x \neq x'$ we have that $e \neq e'$. Therefore an algorithm $\mathcal{B}$ that simply runs $\mathcal{A}$ and encodes the outputs finds collisions in $\mathsf{H}$ with the same probability with which $\mathcal{A}$ finds collisions in $\mathsf{H'}$. Therefore, since $\mathsf{H}$ is collision resistant, so must be $\mathsf{H'}$.

It thus follows that all you need is a unique encoding of your tuples into binary strings. And as correctly observed, if all (or all but one) of the constituent parts of the tuple are of fixed length then simple concatenation is in fact a unique encoding.

However, it should be stressed that this requires all participants to always check that all elements of the tuple they are encoding actually have the required length and rejecting them otherwise. This a check that is easily missed (or maybe even skipped for "efficiency").
Whereas prepending the length -- even for fixed length elements -- ensures that even unchecked malformed tuples will not be able to cause collisions.


garbled circuit vs fully homomorphic encryption

Yes, standard GC are not re-usable, thus by means of GC you may outsource the computation of a single function on a single input (i.e. you delegate a function described by a Boolean circuit and later you may ask the evaluation of the function on a single input not fixed in advance).

Indeed this is the approach to Verifiable Computation proposed in a paper of Gennaro, Gentry, Parno (https://eprint.iacr.org/2009/547). Here, “verifiable” means that you also want a proof that the server computed the input on the expected function. How would you extend this idea to multiple inputs? To this scope the authors employ FHE.

But maybe this goes beyond your question since the aim of the authors is to achieve verifiability. As said in a previous post, re-usable GC have been proposed but they are indeed based on FHE.


An important thing to note is that $\mathsf{P} = \mathsf{NP}$ would not fundamentally threaten cryptography - even theoretical cryptography. What it would imply, as mentioned by Meir Maor in his answer, is that there is no one-way function, which means essentially no "traditional" cryptography.

However, one-way functions, and most of cryptography, are theoretically defined as requiring a superpolynomial gap between the best attack and the honest use of the algorithms. Still, if tomorrow you prove $\mathsf{P} = \mathsf{NP}$, there can still exist functions which take time $n$ to compute, but time $n^{10}$ to invert. This would not at all contradict $\mathsf{P} = \mathsf{NP}$. It would however suffice for all practical purposes: take $N = 2^{10}$, then evaluating your function takes $2^{10}$ steps, while inverting it takes $2^{100}$ steps. That security margin is good enough for most uses.

Such one-way functions, where the gap between evaluation and inversion is a fixed polynomial instead of superpolynomial, are called fine-grained one-way functions. They are an emerging subject of study in cryptography (see e.g. this recent paper), mainly because they can in theory be built from weaker assumptions than those known to imply standard OWF (even though exhibiting such a fine-grained OWF from a generic, well-studied assumption which is not believed to imply OWF remains, as of today, an open problem). They can be used to construct fine-grained pseudorandom generators and stream ciphers.

It does not seem absurd that, in the event that we prove $\mathsf{P} = \mathsf{NP}$, our best attack on AES would still require $n^{10}$ steps. In this case, after some appropriate key-size adjustments, everyone would just keep on using the good old AES, as if nothing had ever happened, and theoretical cryptographers would replace "assume this OWF takes $\mathsf{superpoly}(n)$ steps to break" by "assume this OWF takes $n^{10}$ steps to break".


Why do authors say conflicting things regarding leak-free stages in their paper?

I think they are saying assuming leak free is necessary to prove security for their protocol, but it would be really cool (thus an open problem) to design a protocol that can tolerate leaks in any stage.


What security flaw exists in MAC authentication scenario?

Digital signatures are used to solve this type of problem. That is, a way for $A$ to sign the message for $B$ so that $B$ is highly confident that $A$ signed the message in question. There are lots of signature schemes out there, such as RSA signing, DSA, and others.

A MAC is not strictly a digital signature, but has a subset of that functionality and may meet your stated goals. It meets the requirement that an attacker won't be able to forge a new MAC without the key, which was the second point listed. (See this tangentially related question about HMAC.)

However, a MAC doesn't strictly meet the first stated goal. The problem is that MACs are based on symmetric keys, which means that everyone with the key can "MAC-sign" a message. When verifying a MAC, all the receiver ($B$) knows is that one of the parties with the symmetric key "signed" the message, but it don't know which one did. A copy of $B$ may send MAC-signed messages to other copies of $B$ and nothing distinguishes those MAC-signings from $A$'s MAC-signings. Practically speaking, this means, at a minimum, the attack surface of which compromised hosts can impersonate $A$ is widened. You no longer have to trick $A$ into signing malicious plaintext in order to forge $A$'s MAC-signature (such as by hacking it), using copy of $B$ will suffice.

This can have horrible implications if messages from $A$ are audited later and need to be verified as originating $A$ under the assumption of foul play on the network. (Maybe a legal court audit, perhaps just verifying that data collected was collected at $A$, etc.) Since any $B$ can forge a message on $A$'s behalf, you can't prove $A$ sent the messages. However, this may or may not be a concern for you.


It should as safe as the boxcryptor encryption when I store the salts for the key derivation (for MAC & content) in the ciphertext, is it?

Yes, that's the definition of a salt, a salt is public (otherwise it is commonly called a pepper). E.g. the various text encodings of bcrypt store the salt next to the hash (which has the same security consequences as storing it next to the ciphertext).

  Do I really need two salts & keys?

And using two salts implies deriving the key multiple times. That's bad, especially if that is done by using a password derivation twice. This looks like the case for your scheme. Performing PBKDF2 twice or for more output than the hash delivers will double the amount of work you have to do while an attacker has to perform the 50K operations only once (per try).

Using HKDF or any other KDF over the output of PBKDF2 is sufficient and much more efficient. You can just use two different labels (identifiers) for the two keys - if two keys are needed. This is also present in the answer of Codes that you linked to.

Another trick is to extract 256 bits of output from PBKDF2 and then split that into two 128 bit keys (or two 256 bit keys for PBKDF2 with HMAC/SHA-512). You probably don't need to extract an IV if the salt is always different (because the derived keys would then also always be different). Or you can generate a separate IV: your choice.

No, you don't need two keys either. You could use a mode of authenticated encryption such as AES-GCM. Then you'd only need just one key. If you use HMAC with a single key then you probably cannot prove that it is secure. But the chance that you run into practical security issues is minimal.

Don't change the MAC to CBC-MAC or another MAC based on AES if you use a single key, because that could make your scheme vulnerable to attack. The protocol using a single key and separate cipher and MAC is more brittle: it could break catastrophically if you implement it incorrectly.


How to determine the exponent when using RSA

There are three main errors here:

Exponent $e$ must be chosen to be coprime with  $\phi$. In your question, exponent $e = 3$ is not coprime with $\phi = 1008$. You can choose $e = 5$ instead.
You must use integer arithmetic, not floating-point. In other words, you cannot have values expressed with decimals.
You cannot encrypt a message bigger than the modulo (in this case, $n = 1073$).

Taking these aspects into account, the remaining steps are as follows. The private key $d$ must be computed so $e \cdot d = 1 \mod \phi$. Using this online tool, we find the private key $d = 605$. Next, we cannot encipher message 121512 since is bigger than the modulo, but we can encipher the first three digits, so $m_1 = 121$. Hence, the other half of the message is $m_2 = 512$. The encryption of $m_1$ is $c_1 = (m_1)^{e} \mod n = 121^{5} \mod 1073 = 25937424601 \mod 1073 = 544$.

You can figure out the rest.


Are there any practical implementation of a homomorphic hashing or signature scheme?

There's plenty of research in this area.  I'll give you just a small sampling:

Speeding Up Homomorpic Hashing Using GPUs. Kaiyong Zhao.  ICC 2009.
Transitive Signature Schemes. Silvio Micali, Ronald Rivest. CT-RSA 2002.
Homomorphic Signature Schemes. Robert Johnson, David Molnar, Dawn Song, David Wagner.  CT-RSA 2002.
Sanitizable Signatures. Giuseppe Ateniese, Daniel H. Chou, Breno de Medeiros, Gene Tsudik. ESORICS 2005.
Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.  Dan Boneh, David Freeman. PKC 2011.
Homomorphic Signatures for Polynomial Functions.  Dan Boneh, David Freeman. Eurocrypt 2011.
Homomorphic MACs: MAC-Based Integrity for Network Coding. Shweta Agrawal, Dan Boneh. ACNS 2009.
On Homomorphic Signatures for Network Coding.  A. Yun. IEEE Trans. Computers.

Like I said, this is only a small subset of the available research in this area.  I found most of these through about 5 minutes with Google Scholar.  I recommend you start by doing a literature review to familiarize yourself with the research literature on this subject: search to find as many relevant papers as possible; read each such paper; for each paper you find, read the related work section and bibliography to try to identify other relevant papers, and also use Google Scholar or other sites to find other papers that cite that paper that might be relevant; for each additional relevant paper you find, repeat the process.

After you have done this process, you should be in a better position to ask a more narrowly targeted question with a particular set of requirements -- or, if you're lucky, you might have found a solution to your particular problem already described in the literature!


Endomorphism ring of a Elliptic Curve and $j$ invariant

If the endomorphism ring is equivalent to the maximal order of the field, why is the $j$ invariant equal to $0$ or $1728$?

The main source of all these theorems about endomorphism rings is in Deuring's Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Unfortunately, I can't find a free copy online, and I don't have a copy either. Another source besides Silverman's books is Washington's (not free) Elliptic Curves: Number Theory and Cryptography.

In any case, in those references, you can find a proof the following: The endomorphism ring of supersingular elliptic curves is a maximal order in a quarternion algebra. Silverman presents it as a starred homework assignment in the book you reference (problem 3.18), but I think going through it all is a bit too off-topic for this site.

As I mentioned in the comments, the $j$-invariant is useful in characterizing isomorphisms between curves, and if two curves are isomorphic (e.g., a curve and its quadratic twist), then they have the same $j$-invariant, but their associated endomorphism rings are isomorphic.

In general though, characterizing the endomorphism group is more complicated than the automorphism group. As Silverman notes in the section you reference:

  If an elliptic curve is given by a Weierstrass equation, it is generally a nontrivial
  matter to determine the exact structure of its endomorphism ring. The situation is
  much simpler for the automorphism group.

$j$-invariants are relevant for automorphisms because those contain invertible isogenies, but endomorphisms aren't necessarily invertible. $j$-invariants characterize isomorphisms between curves. Thus I wouldn't expect there to be a simple relationship between $j$-invariants and endomorphism rings.


Does CPA-secure means security against differential cryptanalysis?

Differential cryptanalysis is a tool which is used to analyze symmetric primitives such as block ciphers and cryptographic hash functions. So it is applicable to CPA secure symmetric encryption schemes.

ElGamal, however, is an asymmetric encryption scheme. Its CPA security essentially relies on the decisional Diffie-Hellman assumption in some group $\mathbb{G}$. Roughly speaking, under this assumption, the adversary can not distinguish the ElGamal ciphertext $C = (C_1, C_2)$ from a random element in $\mathbb{G} \times \mathbb{G}$.

Generally speaking, in the asymmetric setting, security is typically proven by showing that an adversary against some security property would imply an adversary against some underlying hardness assumption (e.g., DDH in the case of ElGamal). That is, as long as the underlying assumption holds, also the cryptosystem is secure. Therefore, one does usually not apply custom attack techniques to the cryptosystem itself, but rather analyzes the underlying hardness assumption. In contrast, in the symmetric setting, the security of the cryptosystem can typically not be reduced to breaking some underlying assumption, which is why one directly analyzes the cryptosystem regarding potential "weaknesses". Differential cryptanalisis is one such tool.


Inverse of a polynomial using long division over GF(256)

I think the root of the misunderstanding is that there are two completely disjoint notions of polynomials at work here.

First there is the finite field $\mathbb{F}_{2^8}$. It's the field where coefficients like "3" live. Following the AES notations, you represent these elements as integers, but they really are finite field elements. The definition of the finite field usually involves polynomials (of degree less than 8 and with coefficients in $\mathbb{F}_2$) but that's best viewed as a matter internal to that field.

Then the question you are trying to solve is about polynomials whose coefficients are themselves elements of $\mathbb{F}_{2^8}$. These polynomials are not at all the same polynomials as the ones used internally by $\mathbb{F}_{2^8}$.

Apparently you are trying to do computations with the coefficients (the ones in $\mathbb{F}_{2^8}$ as if they were integers, so your numbers are off. Let's see things in details:

You want to divide $x^4-1$ by $3x^3+x^2+x+2$. Not that in $\mathbb{F}_{2^8}$, addition really is XOR, so subtraction is the same as addition; thus, $x^4-1$ is also $x^4+1$. But anyway, in the course of the division, you want to "cancel out" the top coefficient of $x^4-1$ with a multiple of $3x^3+x^2+x+2$. In $\mathbb{F}_{2^8}$, $3\times246 = 1$, so you can write:

$$x^4 - 1 = 246x(3x^3+x^2+x+2) - 246x^3 - 246x^2 - 247x - 1$$

Next step is to cancel out this spurious $-246x^3$. Again, take care that this "$-246$" is not an integer; it is a field element in $\mathbb{F}_{2^8}$. Also, since (again) addition is XOR in that field, we can remove the minus sign (in binary fields $\mathbb{F}_{2^m}$, $z = -z$ for all elements $z$). Acknowledging that additions and subtractions are the same thing in a binary field, we can write this:

$$x^4 + 1 = 246x(3x^3+x^2+x+2) + 246x^3 + 246x^2 + 247x + 1$$

In the field, $246 = 82\times 3$ (yeah, for once, this matches integer multiplication, but it is fortuitous). So we can write this:

$$x^4 + 1 = (246x + 82)(3x^3 + x^2 + x + 2) + 164x^2 + 165x + 165$$

So the first "long division" in the Extended Euclidean Algorithm yields a quotient of $246x+82$, and the remainder is $164x^2+165x+165$.

Next step in the Extended Euclidean Algorithm will be to divide $3x^3+x^2+x+2$ by $164x^2+165x+165$. And that one will begin by dividing $3$ by $164$ in the field $\mathbb{F}_{2^8}$. The result of that division is $138$; that is, in the finite field: $3 = 164\times 138$. Computing out the division, we get:

$$ 3x^3 + x^2 + x + 2 = (138x + 79)(164x^2 + 165x + 165) + 79x + 168 $$

I am too lazy to finish it by hand. The crucial point to understand is that all computations on coefficients are in $\mathbb{F}_{2^8}$, which is a finite field with its own rules, which are not the same rules as integers, even though they are represented as integers. In particular, there should be no notion of "odd integer".

Here is a piece of C code that implements computations in $\mathbb{F}_{2^8}$:

static unsigned
add(unsigned x, unsigned y)
{
        return x ^ y;
}

static unsigned
mul(unsigned x, unsigned y)
{
        unsigned z;
        int i;

        z = 0;
        for (i = 0; i < 8; i ++) {
                z ^= x & -(y & 1);
                y >>= 1;
                x <<= 1;
                x ^= (0x11B & -(x >> 8));
        }
        return z;
}

static unsigned
invert(unsigned x)
{
        unsigned z;
        int i;

        z = x;
        for (i = 0; i < 6; i ++) {
                z = mul(z, z);
                z = mul(z, x);
        }
        return mul(z, z);
}

static unsigned
divide(unsigned x, unsigned y)
{
        return mul(x, invert(y));
}

In this code, every element of $\mathbb{F}_{2^8}$ is represented as an integer in the $0$ to $255$ range (0xFF is $255$). As you see, addition really is XOR (the C operator ^ is bitwise XOR). Multiplication is done bit by bit; the weird-looking code:

                x <<= 1;
                x ^= (0x11B & -(x >> 8));

is really a "left shift" of x in $\mathbb{F}_{2^8}$ (try to work out why it works, it's enlightening). Finally, inversion (invert() function) is done with exponentiation: since there are exactly $255$ invertible elements in $\mathbb{F}_{2^8}$ (all except $0$: it's a field), then the inverse of $z$ is $z^{254}$ for all elements $z\neq 0$. The invert() function computes $z^{254}$ by repeated squarings and multiplications. (Note: that invert() function will happily compute the inverse of $0$ as $0$, even though $0$ is not invertible.)


Geometric Cryptography and Zero-Knowledge Proofs

Suppose that the second approach is used, this would allow an attacker to impose Alice. The intuition is that, as long as an attacker knows what is Bob going to ask him, he will be able to make things as he wishes in order for verification to pass.

Basically, the attacker wants to give Bob a (chosen) value of $R$ such that when he gives $L'$ to Bob verification holds ($L'$ would be $L = K + X_A$ in the case of Alice). This means that $3\ast L'$ should be equal to $R + Y_A$. This is easy since he can choose at first a random value for $L'$ and then set $R$ to be $3\ast L' - Y_A$ (recall that $Y_A$ is public!), you can check that verification will pass.

Notice that this works since the attacker sends $L'$ and $R$ simultaneously. This fails in the former protocol since Alice is asked to commit to $R$ at the beginning and then compute $L$ from there depending on Bob's choice.


Key distribution and computation for homomorphic encryption

You are correct, if you do things the way you describe, A would be able to decrypt B's private data. So don't do it that way.

Instead, since B is to know the answer, let B encrypt his private input with his own public key. He sends that to A. A encrypts her private input with B's public key, then runs the computation. A then returns the encrypted answer to B. B decrypts it.

Since you added multiparty-computation, you may be interested in how this extends to more than two parties. Here is a relevant quote from Craig Gentry's PhD thesis

  Extending our application of fully homomorphic encryption from the two-party setting to the multiparty setting is not entirely trivial, since, in the two-party setting, Bob prevented Alice from seeing any intermediate values encrypted under Alice’s key simply by finishing the computation himself, and sending back the final encrypted value to Alice; in the multiparty setting, it is less clear how one prevents Alice from seeing intermediate value encrypted under her key.

A number of protocols using homomorphic encryption to enable secure multiparty computation have been proposed, the most practical of which is probably SPDZ.


What would be the most recommended AES && RSA Keys for production?

The RSA keys generated by the (Java) code in the question are 1024-bit, thus are not considered secure (even though there has not yet been any successful attack of a 1024-bit RSA key where that size was the only issue, see this). Security authorities no longer recommend anything below 2048-bit, and none that I know condones 2048-bit after 2030. Other common sizes (likely to remain safe sizably longer / against more powerful adversaries) are 3072 and 4096-bit.
The AES keys generated are 128-bit (since it consists of 16 random bytes and each byte is 8-bit), thus are appropriately sized to resist current attacks. There's consensus to consider them at least as secure as RSA-2048 when generated and used correctly. Other standard sizes are 192 and 256-bit, and give increased insurance, including against hypothetical Quantum Computers usable for cryptanalysis (which may or may not become reality before a global disaster makes earth unsuitable for human life).
It's impossible (and off-topic) to tell from the (Java) code linked if the key generators used are good or not. In particular, that depends heavily on the cryptoprovider used, which is tasked to allow use of a Smart Card or HSM. Even if the default Java cryptoprovider is used, it's quality depends on the particular JVM (including it's version), and the OS.
Practical security is also limited by many other factors. Among the most important are how the keys are stored or/and transmitted, and integrity of the platform the code runs on.

are these keys efficient?

For RSA: Yes, when it comes to use of the public key (encryption or signature verification), this is near best in class; no when it comes to use of the private key (decryption or signature generation). Other asymmetric algorithms are slower for public key, but considerably faster for private key. Yet beware that RSA is often more available. RSA is thus preferred when portability is paramount, or/and when public key operations dominate, e.g. signature of executable. ECC-based algorithms like EdDSA are preferable when available and there's an about even mix of public and private key usage.
For AES: Yes. AES-128 is typically one of the fastest symmetric-key algorithm available on a given platform.

I don't have any IV, is it good still without it ?

That's not answerable, for that depends on what good applies to. The key is still good. Using the key without IV can be anything from a disaster (e.g. for multiple AES-CTR encryption) to just fine (authentication).

If IV is good and wont affect the performance then how can I add it ?

An AES IV can be generated just like a 128-bit AES key.


Why is it that most messages seem to be expanded?

Is there a reason that expanded messages are much more difficult to crack?

When looking purely at encryption, message expansion does not really tell you anything about the difficulty to crack it.

Message expansion is often a feature of asymmetric cryptosystems. Those are not inherently more difficult to crack than symmetric systems. Block ciphers also expand the length slightly in some modes, but other equally secure modes do not expand the message length.

Weak classical ciphers often act on single symbols, so they will not expand the message, but e.g. stream ciphers can likewise act on single symbols and remain secure.

However, there are a couple of caveats:

Semantically secure encryption requires some kind of an IV if you reuse the key for multiple messages. This can expand the message if it is added as part of the ciphertext, but it does not need to be - many protocols handle the IV implicitly.
Authenticated encryption must expand the ciphertext at least somewhat. And authentication is usually necessary to prevent attacks that would be possible even with otherwise secure encryption. So in that sense message expansion is often necessary.


I have an almost identical requirement for location identifiers I use in a custom inventory system. I have a 35-bit code, which is displayed as 7 5-bit elements, which need to be human readable and unique. The method to generate the codes does not necessarily have to be format preserving, that can just be a side effect of the algorithm used.

The method I use generates a 7 character code, with each character being alphanumeric 0-9 and A-Z, omitting OIZS because they are too similar visually to 0125. Internally the algorithm is a block cipher called Bromine with 5 7-bit elements in a generalized Feistel network, which is based on the round structure of the HIGHT block cipher. The input is a numerical sequence, and the output is a pseudorandom alphanumeric sequence:

JE4HV9W
JPNJ4NE
V20MUP3
QCKCVWU
QTR7FUC
5E94W9J
4HYWH14
9W1229T
PT6JJTV
MEWTT68
91ACL19
....

Because the input sequence is numeric, there are only 10 million output combinations for the given 34.36 billion possibilities for a 35-bit value. This limits the number of ciphertexts available to reverse engineer the algorithm or determine the key used. The algorithm is simple but has enough rounds to be secure given the key size (in theory). The use environment has no requirement for this kind of security, but it allows it to be used for other applications if needed. The numeric input is a security and usability requirement, and not a limitation of the algorithm.

If used to generate coupon codes, certain input elements or bits can be fixed, and those fixed bits can define the coupon type or discount. The system would only need to keep track of used coupon codes, and decode them to determine the type and validity. Only 1/3436 codes entered randomly will decode to a valid input, and the number of coupons from valid inputs can also be limited further.

For example, your input could be structured as XXYYYYZ, where XX is the coupon type, YYYY is the value, and Z is a fixed element such as 0. Coupon 01 would be assigned to a 5% discount with only 100 allowed coupon uses before it expires. When entered into the system, it is decoded, its structural validity is determined (is numeric and Z=0), XX is determined to be a valid coupon, and YYYY is determined to have not been yet used for a given XX. If all requirements are met, the discount is given, and XXYYYY is saved for comparison with further coupons. Only 0.003% of this example format meets the required structure and only 1% of these decode to the desired coupon type.

If a longer code is required, variants of such a cipher are easily generated in other sizes. The 40-bit version extends the subwords to 8-bits, and is displayed as an 8 character code. A 42-bit version for display as 6-bit 7 character codes is created by extending the 5 subword 7-bit Feistel structure to 6 subwords, and the 48-bit version extends its subwords to 8-bits.


The classic standard assumptions (such as DDH, CDH) are not parametrized and always have constant size (are static). Consequently, the assumption when used in a reductionist proof is independent of any system parameters or oracle queries and only related to the security parameter.

In contrast, non-static ($q$-type) assumptions as already mentioned by Travis are parametrized (and actually a family of assumptions). They may be used in a static way (e.g., as 2-DBDHI), but if a reductionists proof relies on the non-static version, e.g., $q$-DBDHI, then $q$ is usually related to the number of oracle queries an adversary makes. For instance, if you have a signature scheme where a $q$-type assumption is used, then $q$ usually corresponds to the number of signing oracle queries an adversary makes and then the reduction works (you may for instance look at "Short Signatures Without Random Oracles" from Dan Boneh and Xavier Boyen, who reduce the security of their scheme to the $q$-SDH assumption). Consequently, the more signing queries an adversary is allowed to do, the larger the problem instance and usually the stronger the required assumption gets (observe that for static assumptions this does not influence the assumption itself). As Travis has mentioned some $q$-type assumptions can be converted to static assumptions such as subgroup hiding (typically in composite order bilinear groups).

Another class of assumptions which are typically seen to be stronger than $q$-type assumptions are interactive assumptions. Here, the assumption itself involves some oracle. A classic example are one-more assumptions (one-more RSA inversion, one-more CDH, LRSW assumption), where having $n$ times access to a "helper" oracle that solves some hard tasks on one of the $n$ inputs each, the assumption states that it does not help to solve the task on $m>n$ inputs. Another classic example for this type of assumption are knowledge of exponent assumptions, where solving some hard tasks implies some oracle (extractor) that extracts some value that the solver is implicitly assumed to know in order to solve the hard task. Interactive assumptions are non-falsifiable (you may read this paper) and thus people usually try to avoid them.


Linear AES : expression of K in AES(P) = AP+K

This question is taken from an old Capture the Flag competition, but I believe that there is strong didactic value in presenting a full answer. However, I'm still quite new to SE, so if anyone wishes to edit or delete this answer to make it more appropriate, I promise to accept this without complaint or resentment. Regardless of whether they agree with me or not I hope that all members of the community will assume good intent on the part of other members.
I'm going to do everything bitwise (i.e. over $GF(2)$ as you have specified that $A$ be a $128\times 128$ matrix. It is possible to rework this over $GF(256)$ in the usual AES basis by treating $8\times 8$ matrices as elements of $GF(256)$. I'll build things up to make things fit neatly into the formatting, but you should find expansion easy enough. Throughout, $O$ denotes an all zeroes matrix (of appropriate size). I've not checked any of these calculation numerically and there may be errors of endianness.
Some 8-by-8 matrices
We write $I$ for the 8-by-8 identity matrix over $GF(2)$ and
$$X=\left(\matrix{0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\1&0&0&0&1&0&0&0\\ 1&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\1&0&0&0&0&0&0&1\\1&0&0&0&0&0&0&0 }\right)$$
note that if we have an 8-long column vector representing an element of $GF(256)$ in the polynomial basis $x^8+x^4+x^3+x+1$ with the top entry being the coefficient of $x^7$ then multiplying by $X$ is the same as multiplying by $x$ in the field $GF(256)$.
Some 32-by-32 matrices
We build larger matrices from our $8\times8$ matrices. Let
$$C=\left(\matrix{X&X+I&I&I\\I&X&X+I&I\\I&I&X&X+I\\X+I&I&I&X\\}\right)$$
which is a 4\by4 matrix of 8-by-8 sub matrices making a 32-by-32 matrix. Multiplication of a 32-long column vector by $C$ is equivalent to the action of AES column mixing on a single column. We also write
$$\sigma_0=\left(\matrix{I&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$
$$\sigma_1=\left(\matrix{0&0&0&0\\0&I&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$
$$\sigma_2=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&I&0\\0&0&0&0\\}\right)$$
$$\sigma_3=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&I\\}\right).$$
Some 128-by-128 matrices
We write
$$S=\left(\matrix{\sigma_0&\sigma_1&\sigma_2&\sigma_3\\\sigma_3&\sigma_0&\sigma_1&\sigma_2\\\sigma_2&\sigma_3&\sigma_0&\sigma_1\\\sigma_1&\sigma_2&\sigma_3&\sigma_0\\}\right)$$
note that multiplying a 128-long vector by $S$ corresponds to the AES shift rows operation. We also write
$$M=\left(\matrix{C&0&0&0\\0&C&0&0\\0&0&C&0\\0&0&0&C\\}\right)$$
and note that multiplying a 128-long vector by $M$ corresponds to the AES mix columns operation. We also write $R=MS$.
For your purely linear AES, a round of encryption consists of multiplying by $R$ and adding round key apart from the last round which consists only of multiplying by $S$ and adding round key (there is also a pre-add of key before any rounds. Thus for AES-128 which has 10 rounds
$$A=SR^9$$
for AES-192
$$A=SR^{11}$$
and for AES-256
$$A=SR^{13}.$$
If we write $k_0,\ldots k_{10}$ for the AES-128 rounds keys written as 128-long vectors, we have
$$K=k_{10}+Sk_9+SRk_8+SR^2k_7+SR^3k_6+SR^4k_5+\cdots+SR^9k_0$$
likewise for AES-192
$$K=k_{12}+Sk_{11}+SRk_{10}+SR^2k_9+SR^3k_8+SR^4k_7+\cdots+SR^{11}k_0$$
and AES-256
$$K=k_{14}+Sk_{13}+SRk_{12}+SR^2k_{11}+SR^3k_{10}+SR^4k_9+\cdots+SR^{13}k_0.$$
Expressions for round keys in regular AES
Knowledge of $K$ is sufficient to recover any plaintext from its corresponding ciphertext and vice-versa. However, it might also be of interest to recover the actual master key. In the case of 192-bit and 256-bit variants, this will not be possible as the are only $2^{128}$ possible values of $K$ and so each value of $K$ almost certainly corresponds to multiple master keys.
In the 128-bit case it is possible that master keys uniquely correspond to $K$-values. To investigate this, we delve deeper into the key schedule. The key schedule itself in standard AES makes use of the $S$-box. This means that the round keys themselves are non-linear functions of the master key. Although the non-linear function for each round key is a bijection, there is no guarantee that the linear combination of them to make $K$ is bijective and in all probability it is not. In any event, the non-linearity makes recovery of the master key from $K$ considerably more onerous than we would like.
Linear round keys
On the other hand, if we assume that our linear AES also eschews the $S$-box in the key schedule, we can recover the master key. We introduce another 32-by-32 matrix
$$T=\left(\matrix{0&I&0&0\\ 0&0&I&0\\ 0&0&0&I\\ I&0&0&0}\right)$$
whose action on a 32-bit word written as a column vector is to rotate the bytes of the word left. We also introduce the 128-by-128 matrix
$$U=\left(\matrix{I&0&0&T\\ I&I&0&T\\ I&I&I&T\\ I&I&I&I+T\\}\right).$$
With this notation if we write $k$ for the master key we have $k_0=k$ and
$$k_{i+1}=Uk_i+r_i$$
where $r_i$ is the 128-long vector which is zero apart from the last 16-bits which take the values 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36 for $i=1,\ldots,10$. Thus in this case
$$K= (U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9)k+(r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1)$$
writing
$$V=U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9$$
and
$$r=r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1$$
we then have
$$k=V^{-1}(K+r).$$


From the Security Considerations -section of the RFC:

  Even
     if the host's password database were publicly revealed, the attacker
     would still need an expensive dictionary search to obtain any
     passwords. The exponential computation required to validate a guess
     in this case is much more time-consuming than the hash currently used
     by most UNIX systems. Hosts are still advised, though, to try their
     best to keep their password files secure.

So not much security is claimed in the case of password compromise. A dictionary search is possible, just deemed expensive, which it arguably was back then.

The "hash currently used" presumably means DES-crypt (bcrypt was new and as yet rare), which uses 25 iterations of slightly modified DES with only 56 bits of the password used. You can see how even two iterations of SHA-1 followed by a modular exponentiation could be better.


Linear secret-sharing scheme for four players

First, calculate the parity-check matrix $H$, whose rows generate the null space of $M^T$. $H$ is a generator matrix for the dual code $C^\bot$ of the linear code $C := \{ x \, M^T \}$ associated to your secret-sharing scheme. The access structure of your scheme is given by the minimal codewords $\mathbf x = (x_0, x_1, x_2, x_3, x_4)$ of $C^\bot$ that have $x_0 = 1$; specifically, $\{P_i : x_i \neq 0\}$ is a minimal reconstructing set if and only if there is a minimal codeword $\mathbf x$ in $C^\bot$ with $x_0 =
 1$ (Massey, 1993).


How exactly would someone crack a private key passphrase?

Typical ways include

Dictionary attack
Common modifications of dictionary words
Concatenation of dictionary words
Brute force


How to find the secret key and nonce from two messages encrypted using the same nonce?

Short answer: No, the key and the nonce cannot be recovered from a ciphertext.

Longer answer with a big "but":  The encryption in  crypto_box is done using XSalsa20 which is a stream cipher.

All stream ciphers create a Key Stream $S$ and encryption of the message $M$ is then done using XOR addition: $C=M \oplus S$. Since the key steam only depends on the key and the nonce, you will get the same one in case of a nonce reuse.

From the properties of XOR follows, that I'd you add two ciphertexts, you'll end up with the XOR sum of the plain texts $C_1 \oplus C_2$. So if you know any plain text, you can easily recover every other message encrypted with the same key & nonce combination.


Multiple (RSA) public key encryption how to verify others received the same information? Non-deterministic encryption

As long as you are not wedded to RSA, here's a way that completely solves the problem (and scales to more than two targets).

The general idea is that we do EC-ElGamal in a pairing friendly curve (that is, an elliptic curve that has a computable function $e(X, Y)$ that satisfies the identity $e(aG, bG) = e(G, G)^{ab}$, for any integers $a, b$ (and $G$ is the generator point), and for which $e(G, G) \ne 1$.  The power on the right is typically a multiplicative group of a finite field (which would depend on the curve you're using), that's not important at this point.

In any case, Bob and Oliver would select private keys $b$ and $c$ (I'll use c rather than o for Oliver, because o is too easily confused with 0), and their public keys are $B = bG$ and $C = cG$.

The encrypt, Alice takes the message $m$, and maps it in a way that is both invertable and nondeterministic to a point $M$ (it has to be nondeterministic, otherwise a third party with a guess of $m$ can verify his guess using the $e$ function).  Then, she selects a random value $r$, and generates the two ciphertexts:

$$rG, rB + M$$

$$rG, rC + M$$

(note: each ciphertext can use the same $rG$ value, or use different ones; both varieties work).

Bob and Oliver first check whether all the points in the ciphertexts are actually points in the curve (I'm not sure what can go wrong if they're not, but it's an easy check to do).

Then, Bob can decrypt his received ciphertext $X, Y$ by computing $M = Y - bX$ and then mapping $M$ back to the original $m$.

Bob can then verify that Oliver got the same message by reconstructing $rC$ (using the value $M$ he got during decryption), and then verifying that $e( G, rC ) = e( rG, C )$ (where $rG$ is the value from Oliver's ciphertext); if they received the same message, then both values are $e( G, G )^{rc}$


There is an encryption scheme called RSAES-PKCS1-v1_5, or PKCS#1v1.5 for short. There is a signature scheme called RSASSA-PKCS1-v1_5, or PKCS#1v1.5 for short. These two schemes have different security postures.

The signature scheme has no particular weakness as long as the implementation is functionally correct and the use of the private key has no exploitable side channel leak. There is a class of attacks against PKCS#1v1.5 due to Bleichenbacher, but it's due to implementations of signature verification that don't verify everything they should. Vulnerable implementations still existed in 2019, but major implementations of PKCS#1v1.5 have been safe for ages.

The encryption scheme is extremely difficult to implement correctly because decryption is vulnerable to padding oracle attacks. Some ciphertexts are invalid, and merely revealing whether a ciphertexts is valid or not, even through a very small timing difference, is enough to allow attackers to decrypt arbitrary ciphertexts. To make matters worse, revealing partial information about a plaintext after a successful decryption can also allow the attack. This class of attacks is also due to Bleichenbacher (there's also a similar class of attacks known as Manger's attack). There was a big wave of disclosures in late 2018 nicknamed “the 9 lives of Bleichenbacher's CAT”, and it's probably not the last one. PKCS#1v1.5 encryption is extremely hard to implement and use correctly and many voices are calling to stop using it altogether.

TLS up to 1.2 has cipher suites that use RSA encryption: the client encrypts a master secret, the server decrypts it, this master secret becomes a shared key for the subsequent communication, and the client knows that it's talking to the correct server because only the correct server can decrypt the master secret. TLS also has cipher suites that use RSA signatures: the two parties perform an unauthenticated key agreement to establish a master secret, the server signs the handshake data, and the client verifies the signature to ensure that it's talking to the correct server.

If a server is willing to use a cipher suite that uses RSA decryption, and there is a vulnerability that allows attackers to use the server as a decryption oracle, this vulnerability may also allow attackers to use the server as a signature oracle. If this is the case, then attackers can impersonate the server even against clients who refuse to use RSA decryption. The attack goes like this:

The client starts a handshake. The attacker is a man-in-the-middle and intercepts the handshake packets. The client and the attacker agrees to use a TLS cipher suite based on RSA signature.
The attacker needs to sign the handshake data. It contacts the server, which is willing to perform RSA decryption. The attacker uses the server as an oracle to construct a signature of the handshake.
The attacker sends the valid signature to the client, so the client believes that it is talking to the correct server.

This attack is possible even if the client uses TLS 1.3, which only has cipher suites based on RSA signature (as well as cipher suites using other signature schemes), not RSA encryption. The root of the problem is that the server is willing to do RSA decryption and RSA signature with the same key.

This is an illustration of the fact that it's bad practice to use the same key for two different purposes. A protocol definition cannot protect against this (other than to say “don't do it”, but it's not something that the other side can detect).


The Explicit Formulas Database, EFD catalogs a variety of curve forms, coordinate systems, and algorithms for arithmetic operations, along with operation counts and references to the literature.


Safe, yes, but it doesn't really give you anything.  The only use for a salt is to mitigate precomputation attacks against a password.  Since it is public, it gives you no extra MAC security.  By the property of the MAC, no adversary can forge one without knowing the key, and by the security of your KDF (which includes the salt) no one should be able to get the key.  So, it is pretty much pointless.


Can cryptography help create tamper proof voting systems?

Cryptography allows voters to verify that their ballots are cast as intended, recorded as cast and counted as recorded. This is done via a combination of primitives with the most important ones being zero knowledge proofs. Moreover cryptography allows for voter anonymity by using primitives such as mixnets, blind signatures combined with homomorphic cryptosystems for vote secrecy.

The field of cryptographically verifiable elections has been researched for almost 35 years and the literature is huge. Many systems have been proposed with an emphasis on integrity achieved through end-to-end (E2E) verifiability. The theory is sound, but I guess implementation and security concerns among others do not allow for wide scale adoption.

I recommend this talk by Ben Adida to get you started.


Secret Sharing Scheme with variable share size?

Adapt Shamir's scheme using a high degree, say degree $d$ polynomial.

Thus $d+1$ shares result. Share them out to 3 users, say giving $d/2$ shares to User 1, $d/2$ shares to User 2, and 1 share to User 3.

Edit: As noted by @Ilmari Karonen this doesn't allow you to make shares shorter due to information theoretic reasons explained in his answer.


The function $n^{-\log(n)}=2^{-\log(n)^2}$ is negligible, but $n(\kappa)$ for it is $2^{\sqrt{\kappa}}$ which is not polynomial in $\kappa$.

If we look at the functions $\mu_c(n)=n^c$, their $n_c(\kappa)$ is $2^\frac{\kappa}{c}$, so if $\mu$ is negligible, its $n(\kappa)$ must be smaller than those (at least for big enough $\kappa$, this is ok since you asked for the asymptotics). This means that $n(\kappa)$ is subexponential, i.e., $n(\kappa)=2^{o(\kappa)}$.


ROCA Implementation, Coppersmith Algorithm does not return roots

At the end of the function coppersmith_howgrave_univariate, you have

if gcd(modulus, result) >= modulus ^ beta:

You created $f$ as
$$
f(x) = x + (M'^{-1} \bmod N)(65537^{a'}\bmod M),
$$
so when you put $\mathrm{result} = f(\mathrm{root[0]})$, you do not get $p$ or a multiple of $p$, so the gcd makes no sense (and if ever you get a gcd greater than 1, you may have a factor of $N$).

I suggest that if root[0] is an integer, put it in roots and return that. That's what I did and it works fine.


Cryptography Pseudo Random Generator example question - proof

I'll be reading the problem statement as

  $G$ is a PRG. Decide for each $i$ whether $G_i$ is always a PRG and prove the answer:
  (ii)   $G_2(s):=G(s_1\ldots s_{|s|-1})\mathbin\|s_{|s|}$
  (v)   $G_5(s):=G(s)\mathbin\|G(s+1)$ where $+$ denotes addition of binary numbers.

$G_2$ is a PRG. Intuitive argument: if the input of $G_2$ is uniform random bits, then its whole output is indistinguishable from random, because the rightmost bit is directly taken as the rightmost bit of the random input, and all the others bits because they are the output of a PRG seeded with the other input bits (which, critically, are independent). That can be formalized by turning an hypothetical distinguisher for $G_2$ into a distinguisher for $G$ (and showing that the output of $G_2$ is wider than its input, and whatever other technicality is required by the definition of PRG).

The solution quoted starts with

  For every $s$ whose last bit equals zero we have that $G_2(s)\mathbin\|G_2(s+1)=$
  $G(s_1\ldots s_{|s-1|})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s-1|})\mathbin\|1$

but that comes without explanation about notation or intent, and with typos.

On notation: a bitstring $s$ of $|s|$ bits is assimilated to an element of $\Bbb Z_{2^{|s|}}$ per the big-endian convention, with bits numbered starting from 1 for the first/left/most significant:
$$s=\displaystyle\sum_{i=1}^{|s|}\,s_i\,2^{|s|-i}$$

On intent: It is computed what $G_5$ becomes under two hypothesis

it is restricted to input $s$ of $G_5$ that has its last bit equal to zero, meaning $s_{|s|}=0$ or equivalently $s$ is assimilated to an even integer, therefore $s$ and $s+1$ are the same bitstring excepts for bit $s_{|s|}$
and $G_5$ is built from a PRG of the form $G_2$, itself built from a PRG noted $G$ even though it's output is one bit narrower than $G$ of the problem statement in (v)

Replacing $G_5$ then $G_2$ by their definition, it comes

$$\begin{align}G_5(s)&=G_2(s)\mathbin\|G_2(s+1)\\
&=G(s_1\ldots s_{|s|-1})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s|-1})\mathbin\|1 \end{align}$$

On typos: in that formula we twice have $|s|-1$ where the question's solution has $|s-1|$.

It should now be intuitively clear that $G_5$ is not necessarily a PRG. That formula shows that if $G_5$ is built from a PRG of the special form $G_2$, and its input has its last bit equal to zero, then the output of $G_5$ has two identical halves, except for their last bit ($0$ for the left half and $1$ for the right half). This characteristic allows to build a good distinguisher (assuming $|s|\ge2$ at the input of $G_5$). We'll prove this in detail.

A distinguisher is a deterministic algorithm $D$ that accepts as input a bistring as wide as the output of the would-be-PRG under test, and outputs 0 or 1. Its advantage $\operatorname{Adv}(D)$ is, by definition, how much in absolute value the probability that it outputs 1 differs in two situations:

the distinguisher receives as input the output of the would-be-PRG under test, itself receiving truly random input bits as input;
the distinguisher receives truly random bits as input.

As a formula: $\operatorname{Adv}(D)=\big|\,\Pr[D(G(s))=1]-\Pr[D(r)=1]\,\big|$

The left probability is computed over all bitstrings $s$ as wide as the input of the would-be-PRG under test $G$. The right probability is computed over all bitstrings $r$ as wide as the output of $G$. The $|\quad|$ notation stands for absolute value of a real, rather than length of a bitstring $s$ as in $|s|$.

The distinguisher $D$ proposed by the question's solution outputs 1 iff the two halves of its input are identical save for their right bit. When testing a generator $G_5$ of the special form considered, that always occurs when the rightmost bit of the generator's input is $0$, hence $\Pr[D(G_5(s))=1]\ge\frac12$; while if the input of $D$ is $2n$ bits and $n\ge1$, $\Pr[D(r)=1]=2^{-(n-1)}$ (because in the experiment computing that probability, it is compared two random independent bitstrings of $n-1$ bits). Therefore $\operatorname{Adv}(D)\ge\big|\,\frac12-2^{-(n-1)}\,\big|=\frac12\left(1-2^{-(n-2)}\right)$, which is a sizable advantage (at least $\frac14$ for $n\ge3$ ).

The proposed solution states at least $\frac12\left(1-2^{-(n-1)}\right)$, which is a better advantage. That's reachable, but requires computing the advantage exactly, or/and a better distinguisher, which is left as an exercise to the reader.

  I understand that to prove something wrong you can just give a counterexample. However is there a more formal way of proving it?

Counterexample is the simplest and most formal way of disproving something. In cryptography, its the best. There are exceptions in other domains.


Signature over MAC value for a random key

Would it be possible to create a signature scheme like this:

As I understand it, your proposal is that the signature consists of the MAC key, along with the signed MAC value of the message.

In general, this would not be secure, for two reasons:

For many MACs, it is not difficult, if you know the key, to find a second message with the same MAC as an existing one.
It is not part of the MAC assumptions that it is difficult to find a second key and message pair that MACs to a specific value.

MACs that would not be secure due to these properties include CMAC and GMAC.

  If it isn't secure, are there ways to make it secure?

Well, if you limited yourself to, say, HMAC or KMAC, it would be secure (as long as you didn't truncate the MAC excessively); however that's largely because these two MACs are largely hashes (with some key bits sprinkled in), and signing a hash is safe.  These two MACs are, in fact, collision resistant, even if you select the key (which is a rather stronger assumption than is assumed by the standard MAC security properties).

On the other hand, if the goal is to use a faster MAC rather than a slower hash, this suggestion would help you a great deal.  The problem, in this case, with GMAC, is that if you know the key, GMAC doesn't actually give you any cryptographical properties; creating first preimages (for example) is actually quite easy...


Zencash uses your passphrase to identify AND unlock a wallet - how is this secure?

I don't know how Zencash works. For all I know they store all the data in cleartext. But I'm going to explain how this can be done securely to some extent, but with fundamental flaws nonetheless.

The fundamental tool here is a key derivation function. A key derivation $F(P,L)$ calculates a value from a secret key $P$ and a public label $L$ such that:

It is unfeasible to calculate any part of $P$ even if you happen to know the value of $F(P,L)$ for many values $L$.
It is unfeasible to calculate any part of $F(P,L)$ without knowing $P$, even if you happen to know the value of $F(P,L')$ for many $L' \ne L$.

The following protocol allows a site to store some data without being able to decrypt it, using your passphrase as the sole input.

You enter your passphrase $P$ on the web page. The browser does not send the passphrase to the server.
The browser calculates both $A = F(P, \mathtt{"address"})$ and $K = F(P, \mathtt{"encryption"})$.
The browser sends $A$ to the server. The server uses $A$ to retrieve an encrypted blob of data and sends this encrypted blob to the browser.
The browser uses $K$ to decrypt the data.

The server is not able to decrypt the data in this scenario. Note that you need to trust that the Javascript code sent by the server is doing the right thing. If the server is compromised, it could start sending new Javsscript code that does send the passphrase to the server.

The fundamental flaw with this approach is that someone can easily steal money by guessing someone's passphrase. This is inherent in using a passphrase as the sole identification method: it permits a mass untargeted attack. If you can guess anybody's passphrase, you can retrieve their data. You don't need to know who they are: just keep guessing potential passphrases until you find one with a non-empty wallet.

Reasonable systems that use a passphrase to secure something always include a salt in the label for the key derivation. The salt is unique per passphrase. It does not need to be secret, but when you come back to the site, you'd need to re-use the same salt. With a salt, it is not possible to carry out mass untargeted attacks. If the attacker guesses that squeamish ossifrage is a likely passphrase, they still need to try it out with every possible salt value.

For completeness, note that when deriving a key from a passphrase, in addition to using a salt, it is necessary to apply a stretching mechanism to make the computation slower. This is the same problem as password hashing. In fact, password hashing and password-based key derivation are very close cryptographic problems.

If, instead of a human-chosen passphrase, the derivation was based on a sufficiently long randomly generated string, then the protocol above would be secure. The problem with human-chosen passphrases is that they have very little entropy: it's relatively easy to enumerate all likely passphrases. This is compounded by the fact that in this scenario, the attacker only cares about the weakest passphrases, they're generally not trying to attack a particular user who may have been extra careful to pick a strong passphrase. But even a user who chooses, say, a passphrase made of 4 random words from a dictionary of 100,000 (which includes some pretty obscure words) has only reached 66 bits of entropy, whereas the standard minimum size for a random string used as a secret is 128 bits and for a financial application 256 bits would be preferred. And if the passphrase which is a grammatical sentence, the amount of entropy is vastly reduced.


How should I implement a secure recovery of encryption?

Usually, you have one important key (the master key).
This can be your private bitcoin key, your password database key, the drive encryption key, or really whatever.
Normally you encrypt this key, because you want to change it as infrequently as possible and encrypt it using some user input (e.g. a password) because of costly re-setups of the system.

You now have two ways to implement backups (easily):

Give the user the key and tell them to store it properly (probably ends bad)
Give the user another means of authentication (e.g. a password) and store a copy of the master key that is protected using this mean next to your standard encrypted key.

Method 1:
The advantage of the first way is that it probably is a full backup of the header and thus you can still recover data if the header is corrupted.
The disadvantage of course is that you have to trust the user to store extremely sensitive data of course and this data usually is highly unfriendly to humans, being a random chunk of bytes.
The usual solution to this is to follow the second approach and let the user do backups of the header.

Method 2:
This way you store two copies of your encrypted master key: One for normal operation and one for the backup case. The backup material then allows for access to the data via this encrypted backup copy of the key. Usually you'd also do a backup of the entire header containing this key to prevent data loss.

Finally there's one last method, which is much more difficult to use and may make securing a system very difficult: deterministic key generation. This way you generate your master key in a deterministic way using a password and the same password input will always yield the same key. The advantage being of course that header backups are not really required and that all it takes is a single password. The disadvantage is of course that if the user choses a bad password (if this is an option) that brute-forcing the key via this method probably is a viable attack vector.


Calculate multiplication of a cipher matrix and a plain matrix

Yes there is. It is called functional encryption for inner product (IPFE), and there are many schemes for that, with different features in terms of underlying assumption (typically DDH, DCR, or LWE), security (IND-CPA, IND-CCA, static or adaptive, etc) and compactness.
An IPFE has four algorithms:

$\mathsf{Setup}$ generates a public encryption key $\mathsf{pk}$ and a master secret key $\mathsf{msk}$
$\mathsf{Enc}$ takes as input a fixed-length message vector $\vec m$, and outputs a ciphertext $c$
$\mathsf{KeyDer}$ takes as input a linear function $f$, the master secret key $\mathsf{msk}$, and outputs a functional secret key $\mathsf{sk}_f$
$\mathsf{Decrypt}$ takes as input a functional secret key $\mathsf{sk}_f$, a ciphertext $c$, and outputs $f(\vec m)$, where $\vec m$ is the message encrypted in $c$.

In your case, the linear function $f$ would be the function $f_B: A \mapsto A\times B$.
IPFE was first defined in this paper, where it was also constructed from a variety of standard assumptions. Since this work, there has been many follow ups, achieving stronger security notions, or more features.
In your context: the matrix $A$ would be encrypted with $\mathsf{Enc}$, and the dealer would reveal the secret key $\mathsf{sk}_B$ associated to the function $f_B: A \mapsto A \times B$. This would allow anyone to obtain $A\times B$ from any ciphertext encrypting a matrix $A$.
Of course, usual safeguards apply: if your matrix $B$ is invertible, this would just reveal $A$ in clear, so $B$ better be a highly compressing, or very low rank matrix, if you want this process to preserve some security.


Solving a discrete logarithm using GDlog


Why does PBKDF2 xor the iterations of the hash function together?

The XOR is indeed meant as a protection against hypothetical short cycles. For a given password $P$, the sequence of $U_i$ should make a "rho" structure: at some point in the sequence, a cycle is entered. For a $n$-bit hash function and random password, on average, there will be a single "big" cycle of size about $2^{n/2}$ and for almost all possible salt values, that cycle will be entered after following a "queue" of average length $2^{n/2}$. However, there can exist passwords for which the central cycle is smaller than that, and there can also be some extra small cycles. Finding a password which yields a small central cycle, or hitting a salt value which leads to an alternate small cycle, is overwhelmingly difficult, and no known example of that is known. Yet the PBKDF2 designers thought that the XOR was a cheap way to cope with such a risk: in effect, this means that the $U_i$ will depend on the queue as well as on the cycle itself.

There is a potentially important point here: when you apply the PRF, i.e. jump from $U_i$ to $U_{i+1}$, the space "shrinks": not all $n$-bit values are possible as output of the PRF. The further you go, the more the space shrinks, until you reach the "central cycle". This implies that if $F$ used only $U_c$ (the last $U$ value), then the space of the generated $n$-bit key blocks would be less than $2^n$; in other words, you would use a hash function with a $n$-bit output and you would not get your $n$ bits worth of security. The XOR aims at counteracting this effect.

Nevertheless, the PBKDF2 structure has never been, to my knowledge, proven in any way, so I would recommend using it only with a hash function which outputs $2n$ bits, if $n$-bit security is to be achieved. E.g., for 128-bit security (a sensible level), use SHA-256. Thus, the big central cycle size will be, by itself, sufficient, regardless of whether the extra XOR is really beneficial or not.