Implementing AES MixColumns with fewest XOR gates I'm playing with Contiki (O.S. for constrained devices such as sensors and micro-controllers) and particularly with the AES encryption in software (the one available in Contiki source code).

I'm trying to  complete the code by adding the decryption operation, but   I'm confused with the inverse MixColumns operation.   They are using the paper Lightweight MixColumns for it (because it can reduce the number of XOR gates in hardware).   On the page  257 they state that:

QUESTION: Would be correct to say that the first line is  equivalent to the following  code? (inspired by a similar question) :

 //buf1 * 9 =  ((( buf1 x2) x2) x2)+ buf1
 buf1  =  state[buf4] ^ state[buf4 + 1] ^ state[buf4 + 2] ^ state[buf4 + 3];
 buf2 = galois_mul2(buf1);
 buf2 = galois_mul2(buf2);
 buf1 = galois_mul2(buf2) ^ buf1;

Currently, my decryption function is not working, but not sure if it's because I'm screwing up in another part of the code or at this point.

many thanks to everyone. When I was reading originally the FIPS 197 document I made one big mistake: I assumed that the appendix C had only the cipher portion, similar to the appendix B, and missed the uncipher portions.

Answering my own question, yes, translation of the variable temp to the one I proposed initially was correct. However, my error come from another part: For ciphering, you can save directly the results in the state array, but for the decryption you need 3 auxiliary variables more.

I'll clean the code a little more and try to suggest an update to the Contiki repository with my part.

Again, many thanks to everyone by guiding this misled soul


Prime numbers of the form $(2^k)p+1$, for a given prime $p$ Let $p$ be a prime. (say 256 bit)

Does there a exist a prime $q$ such that $q = (2^k)p + 1$, for a large $k$ (something like 256), if it does exist, is there a way to find out for which all $k$ such a $q$ exist.

[I know it exists for k =1, I am looking for a large $k$]

There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715.

The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be shared across multiple $k$.

An overly crude approximation of the probability that $q=2^k\,p+1$ is prime is that probability for an integer of same magnitude divisible by neither $2$ nor prime $p$, that is for $p>2$ and by the Prime Number Theorem roughly $\displaystyle\frac{2-2/p}{\ln(q)}$, which we can approximate as $\displaystyle\frac2{\ln(p)+k\ln(2)}$ for our large $p$. A numerical experiment shows that's in the right ballpark, but sizably too high.

A better analysis is that for random large prime $p$, and a small prime $r>2$, the quantity $p\bmod r$ is about uniformly distributed on $[1,r)$, thus $2^k\,p\bmod r$ also is, thus $q=2^k\,p+1$ is divisible by $r$ with probability $1/(r-1)$, rather than $1/r$ for a random integer. It thus contributes to reducing the probability to be prime by a factor $\frac{r-2}{r-1}$ rather than $\frac{r-1}r$. We can correct for that effect, yielding
$$\begin{align}
\Pr(2^k\,p+1\text{ is prime})&\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2<r<\sqrt p}\frac{r\,(r-2)}{(r-1)^2}\\
&\approx\frac{2\,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots
\end{align}$$
since the product quickly converges to the twin prime constant $C_2$ (see A005597). That improved approximation is excellent for large $p$ as in the question.

We move to estimating the probability to find a prime $2^k\,p+1$ for a given $p$ and $k\in[k_0,k_1]$ with $k_0$ and $k_1$ close and commensurate with $\log_2(p)$.

As a crude approximation we can pretend that the probabilities to get a prime for one $k$ are independent of $k$, and approximate the probability that there is one prime $2^k\,p+1$ for $k\in[k_0,k_1]$ as the easily computed
$$1-\prod_{k=k_0}^{k_1}\left(1-\frac{2\,C_2}{\ln(p)+k\ln(2)}\right)$$

For $p\approx 2^{256}$, $k\in[248,264]$ that gives a probability $0.061403\ldots$, meaning we'd need to test about one in $16.286\ldots$ primes $p$ to find a suitable one¹.

This approximation could likely be improved by taking into account that the probabilities for $2^k\,p+1$ to be divisible by a small prime $r$ for a given $p$ are strongly dependent on $k$, since $2^k\bmod r$ is a cyclic function of $k$, and worse of period $(r-1)/s$ often with $s\ge2$ (e.g. for $r=7$).

¹ What I got experimentally is close: $\frac{3395526}{208621}=16.27\ldots$ and $\frac{2116707}{130242}=16.25\ldots$ (scanning primes $p$ starting from $\left\lceil\frac7{22}\,\pi\,2^{256}\right\rceil$ and $\left\lceil\frac{113}{355}\,\pi\,2^{256}\right\rceil$ ).


In Elgamal, the generator g is always quadratic non-residue modulo p where p is a safe prime and inverse of g can be also generator? In Elgamal, the generator $g$ is always quadratic non-residue modulo $p$, where $p$ is a safe prime and the inverse of $g$ can also be generator?

Can I prove it? I can't come up with it at all.

Ok, I assume that you speak of ElGamal working in $Z_p^*$ and you mean that $g$ is a quadratic residue modulo $p$.

The problem with ElGamal, when taking some arbitrary prime $p$ is that you cannot achieve IND-CPA security.

Recall, in the IND-CPA security game, the adversary chooses two messages $m_0$ and $m_1$, obtains the ciphertext of $m_b$, where $b$ is the result of a coin flip, and has to guess with non negligible probability better than $1/2$ which message has been encrypted.

The problem is that you can use the Legendre symbol to efficiently decide quadratic residuosity modulo $p$. Now, if an attacker chooses one message to be a quadratic residue and one to be a non-residue, then the adversary with the knowledge of the quadratic residuosity of $g$ has non negligible advantage to guess the correct message (I guess this is homework so I do not discuss this in details).

If choosing $p$ to be a safe prime of the form $p=2q+1$ where $q$ is also prime, then the order $q$ subgroup of $Z_p^*$ represents the cyclic subgroup of quadratic residues (this is not hard to see). Then, if you choose $g$ to be a generator of this subgroup and restrict the message space to be quadratic residues, for obvious reasons, you achieve IND-CPA security.

Now, to your last point (inverse of $g$). Note that in a group of prime order ($q$ in our case) every element is a generator. This group of quadratic residues of order $q$ is a subgroup of $Z_p^*$. If you recall basic group theory then you may remember the definiton of a subgroup: Let $G$ be a group and let $H$ be a nonempty subset of $G$. If for all $a,b\in H$ it holds that $ab^{-1}\in H$, then $H$ is a subgroup of $G$. This means, that the inverse $g^{-1}$ of $g$ is in the subgroup and since every element in the subgroup is a generator you have what you want so show.


AES Password Based Key Derivation Iterations I have been writing my own implementation of the Advanced Encryption Standard with cipher block chaining in python3 for the last several months, mimicking the OpenSSL command line interface. I can successfully encrypt a message or binary with the OpenSSL implementation of AES and then decrypt it with my python3 program (and vice versa).
I am currently working on PBKDF1 SHA-512 Key Iterations.
OpenSSL generates the key and IV for the password “Sparky” using PBKDF1 SHA-512 like so:
OpenSSL command to use to follow along is this:
printf "hi" | openssl enc -aes-128-cbc -md sha512 -p -S 436172616D656C00 -k “Sparky”

which means that
salt=436172616D656C00
key=D0F4428B02B161F125FF3FA1FDD98AFE
IV=6F26A9F743FAD01BBC68417A398359A6

In python3, the same Key and IV can be obtained like this:
import hashlib

salt = "436172616D656C00"
passwd = "Sparky”.encode(“utf-8")
salted = passwd + bytes.fromhex(salt)
Key = hashlib.sha512(salted).hexdigest()[0:32]
IV = hashlib.sha512(salted).hexdigest()[32:64]

The key and IV can be found in substrings of the SHA-512 hash.

So I’m not having trouble obtaining the Key and the IV without iterations, but I can’t figure out how to generate the next iteration of the Key (-iter 1)
According to several sources on the internet the iteration function hashes the resultant hash n times. I think something else or something additional is going though because I have tried to hash Hash#0 and the resultant hash does not contain the expected strings for the Key and IV.
So the result of the same OpenSSL command above but with -iter 1 added yields:
printf "hi" | openssl enc -aes-128-cbc -md sha512 -p -S 436172616D656C00 -k "Sparky" -iter 1

results in:
salt=436172616D656C00
key=6354F3AE1EEF92EAE4406759A5882B46
IV=8ACE6C6AE7E1EBDEE45342D0C9087422

Hash0 (the SHA-512 hash without iterations) in this example is
d0f4428b02b161f125ff3fa1fdd98afe6f26a9f743fad01bbc68417a398359a675fe9c7bbf87315f7e4d2b8ef40e578a86eec2acdd95511329af2a9d69f59e76

If I were to take this hash which I know to be good for the 0-th iteration, and hash it again, I would get:
35841649790d6ce2d0ac2b3fe338aba5121858494006aa098f84e06f21587b77adf14f1c5c0a1530db628acfd5d6123d46e449b9619a41a5a6e32ab9230a31e4

And according to the OpenSSL command with -iter 1 set, the hash should start with
6354F3AE1EEF92EAE4406759A5882B468ACE6C6AE7E1EBDEE45342D0C9087422

If you would like to see my code, I can upload it to github or my virtual private server and share it.

Thank you all for all of the excellent help. I am happy to say that with your help I have found the answer to my initial question and more.
The code below accepts a [string] password, [hex string] salt, [int] key size, and [int] iteration count, and returns a tuple containing the correct key and IV for PBKDF2. OpenSSL PBKDF2 uses 10,000 iterations by default. Leave the salt in the command as double quotes if there is no salt.
Proof:
printf "Today is a good day!" | openssl enc -aes-192-cbc -md sha512 -pbkdf2 -S 436172616d656c73 -k "Sparky" -p
results in:
salt=436172616D656C73
key=37A12300EF8D3442B266B41172154DFE0836803C4257AFB6
iv=E2FC1F1DF27AB4A6F303EDD6537EEE53
The same salt, key, and IV can be obtained by using the code and class below:
from pbkdf2 import kdf
key, iv = kdf.pbkdf2(“Sparky”,”436172616D656C73”,192,10000)
results in:
key=37A12300EF8D3442B266B41172154DFE0836803C4257AFB6
iv=E2FC1F1DF27AB4A6F303EDD6537EEE53
“Sparky” is the password
“436172616D656C73” is the salt
192 is the AES-CBC key size
10,000 is the number of hmac iterations (pbkdf2)
And here is the Python3 code (pbkdf2.py).
Import hashlib
import hmac
class kdf:
def pbkdf2(passwd, salt, size, iterations):

    dictionary = {128:((0,32),(32,64)), 192:((0,48),(48,80)), 256:((0,64),(64,96))}

    k = b = hmac.new(passwd.encode("utf-8"), bytes.fromhex(salt) + b'\x00\x00\x00\x01' if len(salt) > 0 else b'\x00\x00\x00\x01', hashlib.sha512).digest()

    for i in range(2, iterations + 1):
        b = hmac.new(passwd.encode("utf-8"), b, hashlib.sha512).digest()
        k = bytes(i ^ j for i, j in zip(k, b))

    key = k.hex()[dictionary.get(size)[0][0]:dictionary.get(size)[0][1]]
    _iv = k.hex()[dictionary.get(size)[1][0]:dictionary.get(size)[1][1]]

    return key,_iv


Symmetric Encryption in the P=NP world I expected to find answers along the lines of quantum-computing insight into attacking AES; however, answers on this question aren't applicable because "Quantum computers give a quadratic speedup on a (sic) general search problems".

Let us suppose the very worst case: P=NP by constructive proof. Therefore, 3-SAT and direct polynomial attacks on AES and all other standard-model symmetric ciphers.

How do we construct something that takes a serious attack to break besides using ECB and sending one block per key? Do quantum-proof symmetric ciphers with properties other than those of the one-time pad actually exist?

I think I can prove that if you use any kind of MAC other than polynomial evaluation MAC (or something else with its characteristic deniability) your cipher must fail.

I can prove that ciphered random data is possible because you can't break ECB over random data, but that proof is useless.

I am aware of the implausibility of ending up in this world of P=NP. I am also aware of this old post describing very good reasons why P=?NP is a poor model for breakability. I am interested in this problem because I am reasonably certain that any solution must use an encryption method that is, of itself, deniable.

The one-time pad has this property; however, I'd rather have an answer that offers something less unwieldy, if possible.

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".


Build Encryption Method from Decryption (Reverse Modulo) So I've been analysing some Javascript Obfuscator. I understand how the strings are decrypted, my interest is now into building the actual encryption method for those strings. I'm not going to post the full decryption method as my only concern is the actual cryptography part, but basically the algo just swap character indexes all around, so my goal is to make an encryption method that swap the characters to the proper places.
My question is related to this part:
for (var r = 0; r < x; r++) {
    var f = g * (r + 72) + (g % 30846);
    var y = g * (r + 104) + (g % 25098);
    var d = f % x;
    var l = y % x;
    var n = k[d];
    k[d] = k[l];
    k[l] = n;
    g = (f + y) % 2012852
}

It loops over all the characters, starting g value is 1245836.
After one cycle, the value of g becomes 1907150, I'm wondering how you can go from that new g value back to the original one.
What are the maths to inverse those operations:
var f = g * (r + 72) + (g % 30846);
var y = g * (r + 104) + (g % 25098);

Not looking to be spoon fed with code. I'm actually trying to understand the maths.
Thanks a lot

so my goal is to make an encryption method that swap the characters to the proper places.

If that's the goal, that's what you do.
You were thinking about "how do I generate the $g$ (actually, the $l, d$ values) in the reverse order"; actually, there's no need.  You just compute the successive $l, d$ values generated by the algorithm, storing them in an array, rather than using them to do the exchanges.  Then, once you have generates all $x$ $l, d$ pairs, then perform the swaps in the reverse order (that is, starting with the last $l, d$ pair generated).


Is it possible to correct the exponent of an RSA public key if it has been altered? Is it possible to change the exponent of an RSA public key?

Yes, it is possible to change the public encryption exponent of an RSA key.

Indeed, this requires no special computation.  An RSA public key consists of two numbers: the modulus $n$, which is a product of two large (secret) primes $p$ and $q$, and the encryption exponent $e$, which is usually a small fixed prime (most often, 3 or 65,537 = 216+1).  If you want, you can simply pick (almost) any other exponent instead of $e$ and encrypt with it.

(You'll have to somehow let the owner of the key know which exponent you used to encrypt the message, but that's easy enough to solve: since the encryption exponent is public information, you can simply send it alongside the message.)

Of course, in order to decrypt the message, the recipient needs to know the corresponding decryption exponent $d$.  If they kept the original primes $p$ and $q$ used to calculate the modulus (which most RSA private key formats do store, if only because knowing them allows the use of more efficient decryption algorithms), then they can easily calculate the correct decryption exponent $d^*$ for any valid encryption exponent $e^*$ simply by taking the modular inverse of $e^*$ modulo $\lambda(n)$ $=$ $\operatorname{lcm}(p-1, q-1)$, just like they calculated the original decryption exponent when they generated the RSA key pair.  Indeed, even if the recipient only knows the modulus $n$ and the original public and private exponents $e$ and $d$, they can use the fact that $ed \equiv 1 \pmod{\lambda(n)}$ to factor the modulus and then proceed as above.

All that said, not quite every encryption exponent is valid.  Obviously, the choice $e = 1$ would be totally insecure, since the encrypted message would just be identical to the decrypted one.  Slightly less obviously, in order for the modular inverse to exist (and thus for the message to be uniquely decryptable), the encryption exponent must be coprime to both $p-1$ and $q-1$.  This could be a problem if someone other than the owner of the private key wanted to change the exponent, since both $p$ and $q$ have to be kept secret for the RSA key to be secure.  A fairly safe choice, in this situation, would be to pick $e$ to be a random large prime less than the modulus; the odds of such a prime being a factor of either $p-1$ or $q-1$ is vanishingly small.  Indeed, even smaller primes could be fairly safely chosen, provided that they're not too small; using $e = 2$ would obviously be a bad idea (since $p-1$ and $q-1$ are always even), but anything over, say, 1,000 should be reasonably safe.

In particular, if you happened to know that $p$ and $q$ were both safe primes (so that $(p-1)/2$ and $(q-1)/2$ are both also prime), and differed by no more than a factor of, say, four (as they should, if the RSA key is generated in the usual way), then any prime strictly greater than 2 and less than $\sqrt{n}/4$ should be safe to use as the public exponent.


One Way Function - How to Prove? Function $f$ is a length shortening function. It reduces to log of size of input, i.e $|f(x)|/\log(|x|) \leq$ $a\ positive\ constant$. Is this a one way function?

Edit: $f$ is any function. Unknown definition, only constraint on the ratio being constant for all $x$

F(x) = 1 matches your requirement and obviously isn't one way. It is trivial to find a pre image for this function as any value is a pre image of 1.
One way function doesn't mean it's hard to find the original value. It means it's hard to find any pre image which leads to the requested output value.
Finding the original value of a compression function is obviously impossible to do with high confidence if the original data is chosen uniformly. This for information reasons regardless of computing power.


Zero-knowledge transfer of value protocol inspired by EC El Gamal This is a follow up on the question I asked here. I designed a scheme that allows the following:

Alice has a value $a$ which she wants to keep secret
Bob has a value $b$ which he wants to keep secret
Alice can "transfer" a part of her value to Bob such that whatever she transfers must be subtracted from her value (the sum of their value must remain the same). For example, if she has $10$ and Bob has $5$, after transferring $2$, she should have $8$ and Bob should have $7$
Victor is an independent observer and must be able to verify that the sum of the values does not change as a result of the transfer. But he should do it without learning any of the numbers involved

The scheme below is inspired by EC El Gamal. If anyone can see holes in it, would really appreciate feedback.

Setup

Alice and Bob hold pairs of EC keys generated using an Elliptic Curve with generator $G$ (an example of such curve could be secp256k1)
Their private keys are $x_a, x_b$, and $X_a, X_b$ are corresponding public keys
Alice has committed to her number by making $A = a*G + X_a$ public
Bob has committed to his number by making $B = b*G + X_b$ public

Transfer

Alice wants to transfer value $c$ to Bob such that $a' = a - c$ and $b' = b + c$. To do this, she does the following:

Calculates commitment to the new number $A' = (a - c)*G + X_a$
Calculates commitment to the transferred number $C_1 = c*G$
Calculates shared secret with Bob and uses it to build a shared key $s = H(x_a * X_b$), where $H$ is a hashing function
Encrypts $c$ with the shared key $C_2 = E(c, s)$, where $E$ is a symmetric encryption function
Makes the following info public $(A', C_1, C_2)$

Bob receives the info and does the following:

Calculates shared secret with Alice and uses it to build a shared key $s = H(x_b * X_a$)
Uses the shared key to decrypt the value of $c = D(C_2, s)$, where $D$ is a symmetric decryption function
Verifies that $C_1 = c * G$
Calculates commitment to the new number $B' = (b + c) * G + X_b$
Makes $B'$ public

Verification

An independent observer (Victor) can verify that the total value in the system didn't change by doing the following:

Verify that $A = A' + C_1$
Verify that $B' = B + C_1$

The scheme above should be secure because all numbers are padded. The numbers are 256-bit integers with:

64 most significant bits containing the actual number
The remaining 192 bits set randomly

So, effectively, instead of transferring something like $2$, Alice would be transferring something like $2.00034094035343043$

As is, there is nothing to prevent Alice from spending more than she holds by letting her $a$ underflow modulo the order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$ of $g$.

Update: and as pointed by VincBreaker in that answer, as is there is nothing to prevent Bob from computing Alice's commitment of transfer of $\bar c$ from Alice to Bob: the only use of Alice's private key is to compute $s$ that she shares with Bob, and with that $s$ Bob can do anything Alice can. A fix is considered in said answer.

Whether the above properties are a functional issue or not depends on the application, but these are something to watch for electronic money.

As proposed, the padding scheme for 64-bit value/amount $\bar x$ (with restriction to $0\le\bar x\le2^{64}-2$) is $x=P(\bar x,r)=\bar x\,2^{192}+r$ for $k=192$-bit uniform $r$, and $\bar x=Q(x)=\displaystyle\left\lfloor\frac x{2^{192}}\right\rfloor$ used to extract value/amount $\bar x$ from $x$, with $Q(P(\bar x))=\bar x$. It follows that if $a=b+c$ then either $\bar a=\bar b+\bar c$ or $\bar a+1=\bar b+\bar c$ hold, with next to equal odds. Whether this is a functional issue or not depends on the application (but see last section for a workaround).

Another security issue is that for $k$-bit random padding $r$ there is at best $k/2$-bit security against someone trying to confirm a guess, for example of a transaction amount $\bar c$ from $C_1=c*G=\bar c\,2^{192}*G+r*G$, by solving for $k$-bit $r$ the equation $r*G=C_1-\bar c\,2^{192}*G$ using e.g. the Baby-Step/Giant-Step algorithm. Same for values held $\bar a$ and $\bar b$.

Thus I'd say that 256-bit ECC is too little, especially if we want exact balance as follows.

If the uncertainty of one unit is an issue, we can improve on that with a sacrifice of some bits of $r$. That could be $k=176$-bit uniform $r$ with $P(\bar x,r)=\bar x\,2^{192}+r-2^{175}$ and $Q(x)=\displaystyle\left\lfloor\frac{x+2^{191}}{2^{192}}\right\rfloor$. In this way most transactions are exact, including the first $2^{16}$ with certainty, and in practice likely the first $2^{22}$.


Computations in extended finite field p^2 I would like to construct a distortion map from a point $\in \mathbb{F}_p$ to $\mathbb{F}_{p^2}$.
If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and a distortion map $\phi(x,y) \rightarrow (\beta x,y)$ that gives a point of the form $\{a+bi : a,b \in \mathbb{F_p}\}$ in $\mathbb{F}_{p^2}$.  Do my computations are the right ones ?

Here is the results of pari/gp :

? p = 821
? q = (p+1)/6
? E = ellinit([0,1]*Mod(1,p));
? until(ellorder(E,P) == q, P = random(E));
? P
%5 = [Mod(277, 821), Mod(137, 821)]

? u = ffgen(p^2, u);
? until(z != 1, z = random(u)^((p^2-1)/3));
? E2 = ellinit([0,1],u);
? elladd(E,P,P)
%9 = [Mod(415, 821), Mod(20, 821)]

elladd(E2,P,P)
%10 = [415, 20]

elladd(E2,P,[z*P[1],P[2]])
%11 = [544*u + 544, 684]

[z*P[1],P[2]]
%12 = [277*u, Mod(137, 821)]

Is the $u$ in pari/gp the $i$ in $a+bi$ ? I consider it as such in my computations.
Here is what I did using the elliptic curve addition algorithm :
For the simple addition P+P over $\mathbb{F}_{821}$, I have the same answer :

$\lambda = \frac{3.277^2}{2.137} = \frac{307}{274} = 307.3 \pmod{821} = 100$
$x_3 = 100^2 - 277 - 277 = 415$
$y_3 = 100.(277-415)-137 = 20$

So I get the same point (415,20) for the case in $\mathbb{F}_{821}$
Then after, with $z = i$, I take $\phi(P) = (277i, 137)$:

$\lambda = \frac{137 - 137}{277i - 277} = 0$
$x_3 = 0 - 277i - 277 = 544 + 544i$
$y_3 = 0.(277 - ((544 + 544i))-137 = 684$

And I get the point $(544 + 544i, 684) \in \mathbb{F}_{821^2}$ which is the right answer following the result of pari/gp.
Do I have any errors in my computations ?

Generally, an element of $\mathbf F_{p^2}$ can be represented as $a+bu$ with $a,b \in \mathbf F_p$ and $u$ a root of an irreducible polynomial of degree $2$ over $\mathbf F_p$. If this polyomial is $X^2+1$, then we have $u^2 = -1$, and in that case it is customary to denote it by $i$ (in an analogy with complex numbers). There is nothing that mandates the use of the polynomial $X^2+1$, however. In your case, PARI/GP uses the polynomial returned by ffinit(821^2), which is the polynomial $X^2+X+1$. Thus the relation to use in your computations is $u^2 = -(u+1)$, and not $u^2 = -1$.

Now, can you force PARI/GP to use the polynomial $X^2+1$? Yes, but remember that the polynomial must be irreducible, and $X^2+1$ is irreducible over $\mathbf F_p$ if and only if $p \equiv 3 \pmod 4$ (prove this!). So it will not work modulo $821$, but would work for example modulo $823$. You do it by providing the polynomial, instead of just the order, to ffgen: u = ffgen(Mod(1,823)*u^2 + Mod(1,823), 'u).

Also, although in this case the primitive $3$rd root of unity $z$ equals $u$, note that it is not true in general.


Asymmetric password encryption - Viable? Which algorithm? We have an application that requires cleartext passwords for user authentication because of the authentication mechanism in use (RADIUS/CHAP), which unfortunately we cannot change. Since we don't want to store cleartext passwords, an idea is to use asymmetric encryption to secure them as good as possible.
After creating/chaning a password, it will be encrypted with the public key and replicated through more or less unsecured channels to the authentication systems. When a user tries to authenticate, the encrypted password will be decrypted with the private key (which has to be available on the authentication servers, obviously).

So we would have a database with lots of encrypted passwords, but all encrypted with the same key. After some research I see that this not the way asymmetric encryption is commonly used. Usually the payload is encrypted with a block cipher and the symmetric key is encrypted with an asymmetric key. But since passwords are quite short I wonder if this additional encryption layer can safely be avoided or if this would be simplification would be a serious risk.

Related to this: What algorithm would you recommend? I kind of narrowed it down to RSA and Elgamal, mostly because these two seem to be most widely used and are available through well-known libraries (OpenSSL, gcrypt). RSA seems to require longer keys to provide the same security, so Elgamal seem to be the better option there's no other argument against it.

Comments?

This seems OK assuming you can trust the authentication servers to leak neither the private key nor the deciphered passwords; and, if you use RSA, assuming you use a standard encryption padding with randomization, e.g. one of the two RSAES schemes in PKCS#1.

Elgamal indeed can give you shorter cryptograms, which might be desirable in the context (an Elgamal cryptogram consists of two group elements; thus when the group is a 256-bit elliptic curve, you get security arguably better than 3048-bit RSA for 17% of the size of each asymmetric cryptogram).

But if ciphertext size is an issue, you can use hybrid encryption which gives you minimal ciphertext expansion, and can reduce the cost of deciphering one more password. That's by enciphering all passwords using a symmetric scheme (e.g. AES GCM, which also gives integrity) using the same random key, itself enciphered with an asymmetric scheme. As an additional (marginal) benefit, each server can have its own private key with minimal ciphertext expansion.
Each server needs to store only a single RSA cryptogram (or whatever asymmetric cryptosystem is used), which holds the symmetric key allowing to decipher any password.

None of this will survive compromise of a server, unless everything sensitive (including RADIUS/CHAP) is in a separate trusted environment, such as an HSM or Smart Card.


Can block ciphers encrypt messages larger than the key length? I am trying to learn some basic cryptography and I am reading some conflicting statements about block cipher.

My current understanding is that we start with an XOR to obfuscate our data. We can then generate a one-time pad to encrypt our message. The only limitation is that the message length must be less than the length of our single-use pad (making one-time padding impractical for large files).

So we introduce block ciphers which encrypt blocks of plaintext at a time. We generate a key which is essentially a mapping of input to output. An example of a block cipher is AES.

I read that AES would blow up if we tried to encrypt a jpeg file - or any message that is larger than our key size (thus introducing stream cipher). I've also read that block cipher is best used on any known-length message (i.e. any file). The latter makes more sense since we're breaking down messages of any length down into blocks anyway.

Which is true? Am I misunderstanding something?

A block cipher like AES itself cannot be used to encrypt large files. One needs to use some mode of operation to chain a sequence of blocks. The length of this whole "chain", which essentially is the product of the block size and number of blocks, is the length that you can encrypt files with. The key size of the block cipher basically tells you what security level you can get from a "chain" of block ciphers (or a single block cipher of course).


Should I include the ciphertext length in an AAD when using Chacha20+Poly1205 AEAD? I want to construct a time-limited authorization token using ChaCha20 and Poly1305 as defined by RFC7539. I chose the following simple layout:

version || nonce || ciphertext || Poly1305 tag
1B         12B      *B            16B

where the concatenation of version and nonce is used as the Poly1305's AAD.

However, this scheme does not explicitly specify the length of the ciphertext to follow, so an attacker may want to try to truncate or expand the ciphertext section of the token. If I add the ctlength value between version and nonce, will it improve security?

It is not necessary; ChaCha20+Poly1305 already includes the length of the ciphertext into the data which is MACed (and hence stirs it into the tag), hence you don't need to.  If someone appends or truncates ciphertext data, they'd change the data the MAC is computed over, and so the tag would not verify.

We can see the pseudocode (in section 2.8.1 of the RFC) which includes the ciphertext length in this line:

    mac_data |= num_to_4_le_bytes(ciphertext.length)
    tag = poly1305_mac(mac_data, otk)

Now, it won't hurt things if you decide to include the length into the AAD; however that's something that the designers have already thought of, and so you don't need to.


Which values to store in rainbow table generation? According to the Wikipedia and Philippe Oechslin's Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf), both starting points and endpoints are keys. Here is an example from Wikipedia:

As you can see, key kiebgt is the endpoint of this chain.

However, according to this site, it is hash values, rather than keys, that are stored in a rainbow table. That is to say, in the example above, hash value 920ECF10 should be shored as an endpoint.

So which one is the correct approach? The second one seems better to me, because we can skip one calculation(the first step) of reduction function R when looking up.

You can do either and the method works. Depending on which value is stored you check for existence in the table at different points in the computation. If the chains are long enough, the addition of a half step does not matter much for time, especially as the reduction function is typically very fast.

However, when you are trying to break a key with a size smaller than the hash size, it makes sense to store the former. Contrarily, if you are looking for passwords which do not have a lot of entropy and may even have different lengths, it can be more efficient to store the hash or a part of it instead.

(Note that the image you quoted is not for a rainbow table, but a simpler hash chain with the same reduction function at each step.)


Attacks on Biased OTP I know that a perfectly random unbiased and not reused OTP cipher is perfect. An OTP under cryptanalysis has a very strong bias (up to 30 % of symbols are represented by 5 out of 255 possible symbols) but no repetition could be found. This OTP encryption is theoretically vulnerable. May I know the possible sequence of steps to exploite the vulnerability?

Assuming that there are no other flaws in the scheme, e.g. that the pads are not reused, the bias alone may or may not be practically exploitable.  Whether or not it is mostly depends on how much you know (or can guess) about the plaintext.

For example, let's say you have a fairly short list of candidate plaintexts that the message might encode.  Given each possible plaintext and the known ciphertext, you can now determine what the pad that yields that ciphertext from that plaintext would have to be, and then calculate the probability that the known biased pad generation process would produce that pad.  This will then tell you which of the plaintexts is most likely to be the correct one (or, more precisely, let you update your prior estimates of the likelihood of each plaintext according to Bayes' theorem).

More generally, given sufficient bias in the pad and sufficient redundancy in the plaintext, you may be able to simply guess which characters of the ciphertext are likely to be encrypted with the most common pad values, and then fill in the missing characters.  For example, the ciphertext below encodes a common English pangram, encrypted with a standard mod 26 one-time pad, biased so that a bit over 50% of all the pad characters are A (effectively leaving about half of the plaintext characters unchanged).

EHUICVDPTWNFOXCUAGSOYERTHRLAZEJOG

Can you guess what the plaintext is?


Safe elliptic curve point addition using projective coordinates: How do I tell if the points are the same? I am trying to implement elliptic curve point addition in hardware for NIST p256 and p384 curves. I have noticed the following issue with the suggested NIST routines:

Consider routine 2.2.7 of http://www.nsa.gov/ia/_files/nist-routines.pdf: Point addition $R = S + T$ is not valid for the case $S = T$ (this would be a point doubling).

Is it correct to state that before performing point addition, you must first check if the two points are the same point and if they are the same point then perform a point doubling instead? If so how do you test if the points are the same?
I am using Jacobian coordinates for my intermediate computations so a given point may have a large number of congruent representations: $(x,y) \mapsto (x/Z^2,y/Z^3,Z)$, e.g. $(16,64,1) \equiv (4,4,2) \equiv (p+16, p+64,1)\equiv\dots$.

How does one determine if two points are the same if they have a large number of possible representations?

A naive method could be that before performing point addition to convert back to affine coordinates and reduce all coordinates to the range $0 \leq x < p$ so then both points have a unique representation but this defeats the purpose of using projective coordinates which is to avoid modular inverse during intermediate computation. In this case it would be better to do all computation in affine coordinates. There must be an easier way to test if $S \equiv T$ without doing this but I have not found many references to this problem. How is this handled in the real world?

In addition to using Jacobian coordinates, all of my intermediate results are not bounded by $0 \leq n < p$ but are instead bounded by $0 \leq n < M*p$ where  $1 \leq M < 2^r$ which is because of my modular multiplication algorithm which has not posed an issue except if trying to determine if the two points are congruent. This increases the search space in affine coordinates to $M$ possible congruent points.

Does there exist a safe addition algorithm for generalized curves?

Inb4 use Edwards curves: I am required to support NIST p256 and p384 curves so I can't pick arbitrary curves.

The routine you link to is already performing that check (lines 15-17): it returns $(0,0,0)$ when $S$ and $T$ are equal, and the caller is expected to handle this by calling the doubling routine.

The equality verification is performed by checking whether
$$X_1Z_2^2 - X_2Z_1^2 = 0$$
$$Y_1Z_2^3 - Y_2Z_1^3 = 0$$

It is easy to see that, since $x = X/Z^2$ and $y = Y/Z^3$, the above equations only hold when the points are equal. Indeed, if neither point is at infinity,
$$
X_1/Z_2^2 - X_2/Z_1^2 = \frac{X_1Z_1^2-X_2Z_2^2}{(Z_1Z_2)^2},
$$
$$
Y_1/Z_2^3 - Y_2/Z_1^3 = \frac{Y_1Z_1^3-Y_2Z_2^3}{(Z_1Z_2)^3}.
$$

We can safely ignore the denominator, since the result is $0$ if and only if the numerator is $0$.

While this implementation is correct, I would not call it safe; timing or power usage information could be used to learn a secret key. This is a good overview of what can happen, and the available options to counter it.


BIP 39: If I mix my 24 seed phrase with another 24 words, will the checksum property allow an attacker to retrieve the original seed phrase? Assume that I have a 24-word passphrase that I want to store securely but online by mixing it with another 24 words in a manner only I know. Does the checksum property somehow help an attacker to significantly speed up the process of guessing the right 24-word phrase in a reasonable time?
I would guess no because the attacker still needs to try an absurd number of combinations being somewhere in the vicinity of
$$
\binom{48}{24} \cdot 24! \approx 2 \cdot 10^{37}.
$$
Edit: For clarifaction, I add a minimal example which led me to the above question. Let us consider the following simple passphrase system:

Choose 3 distinct words from all words which can be set together by 3 letters (abc, god, ced, ....)
The fourth word must fulfil that it contains the first letters of the three first words (that is meant to be a very simplified checksum condition)

Let us say I have the passphrase (ago, bro, sis, abs) and mix it with another passphrase (gro, lab, for, glf) to
(ago, glf, for, sis, abs, gro, lab, bro)
Now it is way faster to scan this sequence and check for which quadruple rule 2. applies to obtain the two possible valid pass phrases than just trying all
$$
\binom{8}{4}\cdot 4!
= 1680
$$
combinations.

The proposed method requires 24 additional random BIP-39 words. The additional words together with the real 24-word passphrase are permutated in a word manner. The result has $2\cdot 10^{37}$ combinations that have $\approx 2^{124}$ bits of security. 8-word passphrase are already had more security than this $\approx 2^{139}$[1]
If a random permutation is used to scramble the words there is another problem with the bit size of the permutation that one has to store. If we consider that each of the 48 words can be represented with 8 bits then one needs $48\cdot 6 = 288$ bits to store. This is already larger than the bits size of the AES-256 that we hard to memorize it so we use BIP-39 or DiceWire to keep our keys secure depending on the length of the key 128 or 256.

I want to find a way to memorize a 24 word passphrase with the least effort possible and without using any encryption. So my suggestion was to just store 48 words in which the passphrase is hidden in a way I can remember. For example, I could just permute the words such that all the even positions recover my passphrase. For an attacker who doesn't know my system this would look like a random permutation. Can this attacker derive from these 48 words my passphrase?

Your least effort possible way to memorize is not unique to you. Actually, this means that you are using less entropy for your permutation. The attackers, by knowing or with a clever thought, will first try this least effort permutations as done in the least effort passwords like 1234.
I will not consider your example even possible position or others, the above paragraph should be enough ( how do you recover the order of the even permutations).
Your idea

Has less entropy than the 24-word passphrase 256 vs 124
An attacker can recover your weak permutations if you are the target and they know your system and you!
Humans are bad at random number generation [2] and you are shifting a secure system to your randomness that already shows the weakness.

If you already consider storing them consider using password managers so that you only need to store one really good BIP-39 or Dicewire and the rest of the passwords can be generated uniform randomly
.


Would this program be useful in cryptography? I know nothing of encrypting. I'm not even sure how to tag this.
I wrote a program that can calculate this pretty quickly on my macbook pro 2.3GHz IntelCore i7. The two exponents are Mersenne primes, and no I did not use floats.

It calculated ((2^756839)-1) * ((2^1257787)-1) = a number 606,463 digits long. The exponentiation, multiplication, and all took about a minute? Would it be good for encrypting? Maybe not those numbers specifically, but in general because it wouldn't require me to use a supercomputer. And yes, that is 606,463 digits long. So prime*prime=N, where N, aside from 1 and itself, is only divisible by the two primes. Don't know if it'd be useful at all, but I did it for fun, for something else. I'm going to try working on the reverse(factoring N).

I can several possible questions in the original post, hopefully I'll manage to answer at least one of them here.

I have calculated a large $N$, with $\log_{10}(N)>600,000$. Is this suitable for RSA?
We have that $\log_{10}(N)>6*10^5>2^{19}$, meaning $\log_2(N)>2^{19}$. Currently, implementations with $\log_2(N)\approx 2^{11}$ are coming into practice, making your choice of $N$ much much larger than those in use today. There's a nice little crypto.SE question here stating that there is no need for $N$ orders of magnitude greater than $2^{2048}$, with good references.

Is my multiplication algorithm good for taking the product of Mersenne Primes? I'm sorry to say the answer is almost certainly no. Multiplying large numbers is something that has been studied in depth over the years, and the odds are your program does not provide a breakthrough. In the particular case you've given (Mersenne primes), there is an efficient way to solve it anyway, so I suspect your implementation isn't as efficient as it could be:

Working in binary notation (as your computer will be), $(2^{756839}-1)$ is the number given by 756839 consecutive 1's. Since $$(2^{756839}-1) * (2^{1257787}-1) = (2^{756839}-1)*2^{1257787} - 2^{756839} + 1$$
the answer will (in binary) have 756838 ones, followed by a single zero,followed by ~50100 ones, followed by 756839 zeros and then finally a 1.
(nb: my counts may be out by $\pm1$, but the idea holds)

Part of this answer is drawn from my comments on the original post.

Is my algorithm good for taking the product of two large integers? I do not know the headline speeds for integer multiplication in general, but I'm pretty sure you should be able to do this a lot more quickly than you have, especially since your multiplication doesn't make use of the binary representation of its operands. You can easily test this by downloading reference code for Big Integer multiplication and timing yours against that. If you have a licence, Magma or Mathematica are both good candidates for a first test.
UPDATE: In the comments below, Reid provides benchmarking figures for Mathematica, demonstrating that your times are well off these, which should themselves be considered lower bounds.


Would creating a custom human language be stronger protection than encrypting a known human language? There are some languages that people haven't been able to read (Cretan Hieroglyphics for example).

Does that mean that you can better protect data by making your own language than by encrypting an existing one?

Or are all human languages really just different mappings of symbols to the same or similar ideas meaning that decryption and translation are the same thing?

$$\texttt{NO}$$

In short;

$$\text{We are living in a world where that is ruled by Kerckhoffs's principles}$$

The above may not be totally clear as indicated by Maarten in the comments. The We is the Modern Cryptographers, the World is used for the Cryptography,... In other words, and better;

$$\text{Modern Cryptography keeps to Kerckhoff's principles}$$

Decoding lost languages is not related to cryptography, though some techniques may be related like frequency analyzing. That is people tend to give names to some common objects like the sun, earth, man, women, child, etc.

  Does that mean that you can better protect data by making your own language than by encrypting an existing one?

Go on build one, then;

On day one, one will sell the decoding. Then you need to change your language and then you have to teach it, everybody. In Kerckhoffs's principle, the system relies on the secrecy of the key, not the system. If the key is sold or compromised, we can change the key, not the system. Of course, we assuming that the encryption system is designed to stay against cryptography attacks like AES that stands for almost 20 years and expected to stand more.
The more you talk the more information you will give to decode. You can get the notion from the researcher who goes into amazon forest to communicate with people who had no contact with other humans in centuries.
Actually, you build a large permutation cipher, that is breakable.

  Or are all human languages really just different mappings of symbols to the same or similar ideas meaning that decryption and translation are the same things?

That is not exactly. For example; some languages don't have a name for the color pink or other. Some missing other words for describing things/actions etc where it exists in some languages. Culture, living area affects the language. This is out of the Cryptography context.

  Would creating a custom human language be stronger protection than encrypting a known human language?

NO

Let finish with the Kerckhoffs's principles

The system must be practically, if not mathematically, indecipherable;
It should not require secrecy, and it should not be a problem if it falls into enemy hands;
It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
It must be applicable to telegraph communications;
It must be portable, and should not require several persons to handle or operate;
Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.


An unusual use-case for HMAC as compression function in web browsers It's an unfortunate fact that, right now (2019), browsers don't expose standardized streaming hashing interfaces in SubtleCrypto. The only way to hash a file, is to load it into an ArrayBuffer in its entirety, which for large files, this could be prohibitvely costly memory-wise.

To get around it, I'm thinking of building a custom hash function using HMAC as its compression function, in a usual Merkal-Damgaard construct.

$
\text{compress}(IV, M) = \text{HMAC-SHA256}_{IV}(M)\\
IV_i = \text{compress}(IV_{i-1},M_i) \\
IV_0 = \text{00h}^\text{hashlen} \\
H(M_1|M_2|...|M_n) = IV_n
$

The specific questions I have are:

Q1: Do I still need to include file length in the final block? I'm guessing no because the HMAC compression function already length-pad my message during processing.

Q2: What are the characteristics of such construct with regard to length-extension attack? I'm using SHA256 because it's standardized in Web Crypto, and it's length-extendable, so I wouldn't be bothering to defend against it in my HMAC-Hash construct.

The collision resistance of this hash will be the collision resistance of $\operatorname{HMAC-SHA256}_{IV}(M)$. Beware of the fact that pre-hashing of the key is a thing with HMAC, so $$\operatorname{HMAC-SHA256}_{\text{ReallyLongIV}}(M)=\operatorname{HMAC-SHA256}_{\operatorname{SHA256}(\text{ReallyLongIV})}(M)$$

  Do I still need to include file length in the final block?

To get the benefits of the Merkle-Damgard proof? Yes, because abstractly your HMAC invocations are just compression function calls.
However if you're willing to assume that it's impossible / really hard to find $(IV',m')$ such that $\operatorname{HMAC-SHA256}_{IV'}(m')=IV_0$ then you don't need to pad with the message length. You see this when you follow the standard Merkle-Damgard proof. That is go backwards through the message and if at any point the inputs differ but the outputs match you got a collision in the underlying compression function. There will be a point where one message may be shorter than the other, assumning both end with the same suffix - because otherwise there would be a collision - both end up at $IV_0$ at some point and as one message is longer one of them must expose a preimage to $IV_0$.

  What are the characteristics of such construct with regard to length-extension attack?

It's a standard Merkle-Damgard, so it has the same length-extension weakness. To fix this you could e.g. use HAIFA and use $C(S,M,P)=\operatorname{HMAC-SHA256}_S(P\mathbin\|M)$ as HAIFA's compression function for some fixed-length integer $P$.


Why can ssh-keygen export a public key in PEM PKCS8 format? In the documentation of ssh-keygen (man ssh-keygen) it says for the option -m that an export to the format “PKCS8” (PEM PKCS8 public key) is possible.

That works, and I can read the files using openssl. But the thing that really confuses me: isn't PKCS#8 a format for private keys?

Or is PKCS#8 a format for the keypair, and the private key is omitted? Those formats are really confusing.

Here is an example key exported with ssh-keygen -m PKCS8 -e:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAuRKdrvmS/1FdSvzljmq8
jNEAPMLLxuTT+yCAw5gZ5VaXQ6BR1LudV2N6YOFYp7yUoOye3CobHI9GhAXrNaHr
S3XoMk7/49g/uNNjJUTPzQ1xXZRbTnRgOkAbstYZDWY53S8X8fqk6ET0h3q2VwTu
vkNkzZpiswkSFi7/SqLF0P+DEewyDTeywaGTUO4ls+8nTtl+T63LRSBGd8qUdOzg
nfhr/YosKg3ePFyw1uC2UCK65KG47kmext+rLGFXT1o8oZ/Mlw5e+0aVSEoa6+MG
vXmhdV0IURnw/DJlalisxppFDHjyg6amBqC08w7r1nooqZvnjCXiXR+LEPlfj6hm
1wIDAQAB
-----END PUBLIC KEY-----

What you have here is indeed a structure called SubjectPublicKeyInfo. It's usually part of an X.509 certificate, but it is often also used separate from a certificate. It's, for instance, the default encoding for RSA public keys in Java and - if I'm not mistaken - OpenSSL.

You can view the complete structure here and compare it with the SubjectPublicKeyInfo structure defined here. Of course, you'll only see it up to the BIT STRING. The BIT STRING itself contains the structure defined as RSAPublicKey here. That the BIT STRING contains the RSAPublicKey structure is identified by the 1.2.840.113549.1.1.1 (RSAEncryption) object identifer (OID).

It's certainly not PKCS#8. That's indeed for private keys.

Note that what you are currently showing is the PEM encoding of said SubjectPublicKeyInfo. The PEM structure, sometimes also called "ASCII armor", makes it possible to send binary data over text interfaces, e.g. mail. It consists of the header, the footer and the base 64 encoding of the binary contents.


anonymous signature implementation and usage? This is one of the question asked in my class. Implement a anonymous digital signature. So it means hiding signers information. i could not find any article in anonymous digital signing. Also another confusion made me think about blind signature. blind signature used to hide senders information before sign by a third party. This scheme is not going to hide sender identity. For my knowledge group signature can be used hide the identity of sender. My question is

what is anonymous digital signature
How it different from blind signature
How can we use this to hide identity of sender

The first google-entry brought up this paper.
To answer your questions:

An anonymous signature is a signature that is unforgeable in the classic sense. But without the message no informations about the signer can be extracted from the signature even if brute-force of all public keys is possible.
If I'm understanding things correctly, a blind signature hides the message from the signer but the signer is still known. So the signer is not anonymous whereas with anonymous signing the signer is anonymous as long as the message is unknown, but the signer knows what he's signing. (I hope that makes sense)
The paper will give you insight in how to actually implement anonymous signature.

You may also wish to read this paper and maybe even some references to get further ideas. In the mentioned paper there's an approach the anonymize the signer by holding back parts of the signature.


justification for method to factorize n knowing RSA private exponent d I know that knowing the private exponent $d$ corresponding to the private key $k_{pub}\langle n,e\rangle$ it is possible to efficiently factorize n.

The procedure starts stating that:

$ed -1 = s(p-1)(q-1)$

and then saying that:

Randomly picking $x\in\mathbb{Z}_n^*$ we know that $x^{ed-1}\equiv 1\pmod n$ and computing $y=\sqrt{x^{ed-1}}=x^{\frac{ed-1}2}$

We have the identity:

$y^2-1$

And so:

If $y\neq\pm1\pmod n$, a factor of $n$ is obtained as: $gcd(y-1,n)$
If $y=-1\pmod n$, we repeat this procedure from the beginning and pick
another value for $x$
If $y=+1\pmod n$, we iterate the whole procedure starting from the square root of $y^2$

Could someone give me a justification for this? Especially for:

"If $y\neq\pm1\pmod n$, a factor of $n$ is obtained as: $gcd(y-1,n)$"

We have $y^2-1 \equiv 0 \pmod n$, meaning that $y^2-1 = (y+1)(y-1)$ is a multiple of $n$. $y \not \equiv \pm 1 \pmod n$ means that neither of $y+1$ and $y-1$ is a multiple of $n$. Now, clearly $\gcd(y-1,n)$ is a divisor of $n$; we want to show that it is not $1$ or $n$.

It cannot be $1$, because that would imply that $n$ divides $y+1$, which we assume is not the case.
Likewise it cannot be $n$, because that would imply that $n$ divides $y-1$.

The reason we take $y$ such that $y^2 - 1 \equiv 0 \pmod n$, by the way, is so that we have a good chance of finding a non-trivial factor. Indeed, if we just pick any random $y$, it is overwhelmingly likely that $\gcd(y-1,n) = 1$, which does not help us.


Ensuring no unintended leaking before authentication Assume my authentication system consists of querying an endpoint to get sign in parameters cost and salt, auth_hash.

After receiving these parameters, I will use cost and salt to derive a 768 bit key using PBKDF2:

key = pbkdf2(user_password, salt, cost, 768).hex

I then split the key three ways:

server_password = key.first_third
encryption_key = key.second_third
auth_key = key.third_third

I will then use auth_key to authenticate the parameters sent from the server and make sure the computed authentication hash matches the incoming auth_hash:

local_auth_hash = HMAC(cost.to_string + salt, auth_key)
abort if local_auth_hash != auth_hash

Now, during normal app flow, I will encrypt user data with encryption_key and authenticate it with auth_key.

My question is, is it safe to use auth_key in both of these contexts (sign in and data encryption)? The reason I would suspect that it might not be ok is that the server can return any cost and salt, and have me authenticate it with my auth_key, and potentially try to glean information this way.

Here are my comments in no particular order:

Don't create your own crypto.
We don't analyze designs on this website because it is hard work and you shouldn't create your own anyway.
It seems that for this protocol to work the server will have to store the user password in plaintext. That seems like a bad idea.
Using this scheme will allow an attacker to brute force the user password using only the information that has been transmitted since he can validate

auth_key = PBKDF2(password_guess, salt, cost, 768))

HMAC(cost.to_string + salt, auth_key) == auth_hash. That also seems like a bad idea.


Use $5^6\pmod 7 =1,$ to re-express negative powers of $5$ with exponents in $\{0,1,\cdots,5\}.$ This works since $5$ is a generator of the multiplicative group of $GF(7).$


Can we proxy-re-encrypt using homomorphic encryption schemes? Homomorphic encryption schemes are PKE schemes with an additional special method Evaluate.

The Evaluate method takes input any function (as boolean circuit) and encrypted inputs of the function and evaluates the circuit. The results of such function are still encrypted under the public key $PK$.

Now, if the user needs to re-encrypt the data with a new public key $PK^1$, the user should decrypt the data with older private key $SK$ first, and then encrypt again with new $PK^1$.

Or how can I efficiently proxy-re-encrypt using FHE schemes without decrypting the data?

Note that if the user runs the re-encrypt circuit as input to the Evaluate method with $PK^1$ as parameter, the result would still  be encryption of (encryption of original data with new $PK_1$) with the older $PK$.

YES. It is pointed out by Gentry (in his thesis) when he consider bootstrapping and re-encryption.

Let us denote the old key pair by $(PK, SK)$ and the new key pair by $(PK^1, SK^1)$.

What the user wants is to re-encrypt an old ciphertext $C = \mathsf{Enc}(PK, M)$ into a new ciphertext $C^1$ which is decrypted into $M = \mathsf{Dec}(SK^1,C^1)$.

To do so without direct decryption, we virtually decrypt $C$ in the draft chamber guarded by $PK^1$, that is, we evaluate a decryption circuit with $PK^1$.
Correctly speaking, we do the following:

Generate $\widetilde{SK}_i = \mathsf{Enc}(PK^1,SK_i)$, where $SK_i$ denotes the i-th bit of $SK$.
Compute $\widetilde{C}_i = \mathsf{Enc}(PK^1,C_i)$, where $C_i$ denotes the i-th bit of $C$.
Evaluate the decryption circuit. That is, $C^1 = \mathsf{Eval}(PK^1, \mathsf{Dec}, (\widetilde{SK}_1,\dots,\widetilde{SK}_n,\widetilde{C}_1,\dots,\widetilde{C}_m))$.

From the correctness of evaluation, we have
$$
\begin{align}
\mathsf{Dec}(SK^1,C^1)
 &= \mathsf{Dec}(\mathsf{Dec}(SK^1,\widetilde{SK}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{SK}_n),\mathsf{Dec}(SK^1,\widetilde{C}_1),\dots,\mathsf{Dec}(SK^1,\widetilde{C}_m))\\
 &= \mathsf{Dec}(SK_1,\dots,SK_n,C_1,\dots,C_m) \\
 &= \mathsf{Dec}(SK,C)\\
 &= M
\end{align}
$$
as we want.

This is just re-encryption Gentry suggested in his thesis.


Why do we use prime numbers apart from hard factorization? Why are prime numbers important in cryptographic constructs? I am not interested in RSA examples where factorization is the hard problem itself, that makes sense. However wherever I go I encounter prime numbers, especially prime order groups and more specifically safe primes from Discrete Log to ECurves etc. Is it only due to Pohlig-Hellman??

Logic says that any type of modular operation is a kind of trap door function that hides the original information regardless of being modPrime.

Any finite setting with addition that distributes over multiplication where neither operation loses information—except multiplying by zero—necessarily has a prime characteristic, which is the number of times you can add 1 to itself before you get back 0.  Further, the size of any finite field is some power of its characteristic, so the size of any finite field is always a prime power (proof).

Finite fields are useful for polynomial evaluation authenticators like Poly1305 and GHASH—their security as a message authentication code follows from the fact that a polynomial of degree $d$ over a finite field has at most $d$ distinct roots.  You could use a ring instead of a field, but then you would need a larger ring to attain the same security because multiplication even by a nonzero value may lose information.

The multiplicative group of certain finite fields—specifically prime fields $\mathbb Z/p\mathbb Z$ when $p$ is large, subject to certain other criteria—seems to be hard to compute discrete logs in.  If we used a ring instead like $\mathbb Z/p_1^{e_1} p_2^{e_2} \dotsm p_k^{e_k}\mathbb Z$ for $\gcd\{p_1,p_2,\dotsc,p_k\}=1$, then we could compute discrete logs independently in the $\mathbb Z/p_i\mathbb Z$ and then lift the solutions to the whole ring using a combination of the Chinese remainder theorem and a magic trick called Hensel lifting in an algorithm chronicled by Eric Bach.  So the DLOG security of $(\mathbb Z/m\mathbb Z)^\times$ depends on the size of the largest factor of the modulus $m$, and there's no reason to use a modulus with more than one factor.  (In principle we could also use finite extension fields like $\operatorname{GF}(2^t)$, but the DLOG security story is pretty well demolished there these days.)

Finite fields also are needed to construct elliptic curves, which provide groups with much better DLOG security than the multiplicative groups of finite fields directly.  (‘Elliptic curves’ over composite moduli lead to arithmetic errors eventually (attempts at division by noninvertible elements), an observation which turned out to inspire a state-of-the-art method of factoring, ECM!)  Either way you get a group $G$ of size $n$, and as you observed, when $n$ is composite, the cost of Pohlig–Hellman—and also of Lim–Lee active small-subgroup attacks on Diffie–Hellman protocols—is determined by the size of the largest prime factor of $n$.

Generally, in any setting where you have a finite group $G$, the group $G$ decomposes into subgroups of $d$ elements apiece where $d$ divides $n$.  And any setting of invertible transformations on a finite set leads to a finite group under composition, so there will necessarily be primes involved in the algebraic structure of the group.

All that said, not all cryptography involves large primes.  For example, the polynomial evaluation hash GHASH—used in AES-GCM for message authentication—is defined over $\operatorname{GF}(2^{128})$, but the group structure of $\operatorname{GF}(2^{128})^\times$ is not relevant to its security so the only prime that's ‘really’ involved (whatever that might mean in math!) is 2.  Code-based cryptosystems like McEliece public-key encryption and CFS public-key signature don't involve any group structures and are usually defined over binary Goppa codes, so, again, the prime 2 is involved, but other primes, maybe not so much.


distribution for a subset of md5 I need to uniquely assign a 32 bit integer to a collection of human readable strings (i.e. they will not be generated with hash collision in mind).  I don't expect more than a few thousand strings.  I would like to evaluate the possibility of using the first 32 bits of the md5 sum for this.  What is the distribution of these bits?

I guess it is wanted to assign a 32-bit integer to each of human readable strings in some collection (for the problem as worded, the answer is 00000000000000000000000000101010).

Assuming that the human readable strings are chosen independently of the definition of MD5, then the first 32-bit of the MD5 hash of each string is about uniformly distributed. That would be a classical result for any hash that is a PRF (for any distinguisher able to recognize the first 32 bits from a random function can trivially be turned into a distinguisher for the full function). MD5 was designed with the goal to be a PRF, and remains good enough. Sorry I do not have a reference.

Odds that there is at least one collision with $n$ strings is
$$p=1-(2^{32})!/(2^{32}-n)!/2^{32\cdot n}\approx1-e^{-n\cdot(n-1)/2^{33}}\approx n\cdot(n-1)/2^{33}$$
The approximation on the right is quite good for $n$ up to about $2^{14}$, arguably including " a few thousand strings ". For $n=10,000$, $p\approx1.2\%$.

However, one knowing your plan to do this and in a position to generate the human readable strings can make the number of collisions high (including having all the strings giving 00000000000000000000000000101010). That MD5's collision resistance is now badly broken is not relevant: the problem is that a 32-bit value is too small. To solve this issue (and return to the probability of collision previously stated even for evil choice of the strings), use a MAC with a secret key, e.g. a truncated HMAC.

Note: the MAC solution also allows to solve the problem of finding a hash with no collision for a particular collection, known as a perfect hash, in a simple way: try distinct keys at random until finding one for which there is no collision: that's easy to check with with $2^{32}$ bits (512 MiB) of RAM. It is tried on average $1/(1-p)$ keys and less than $n/(1-p)$ MAC computations. When $n$ grows past about $2^{17}$ that becomes increasingly impractical, and dynamic perfect hashing comes to the rescue.


Baek and Zheng’s Threshold Cryptosystem - limit on threshold? I have just completed an implementation of Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group by Baek and Zheng and am hitting a problem with high values of the threshold. Please forgive any mistakes below, I have minimal relevant math and notation knowledge and am learning as I go.

I am using a Haskell wrapper around PBC and so far I have been successful with the implementation on small value of $t <= 8$ and $n <= 100$. Unfortunately though anything with a larger $t$ means shares recombination fails. Taking the idea from a python implementation I found and given the dealer mechanism from the paper:

I've tried to reconstruct $x_0$ which fails for $length(a)>8$. Works great for $length(a)<=8$

Even a simple, non PBC version of $x_0$ reconstruction fails using simple values of $a$ e.g. $[10,20,30,40...150]$. Given the list of $x_0..x_n$ from the application of the polynomial on $a_0..a_{t-1}$ I used the Lagrange interpolation

$$\phi_i(xcoord)=\prod_{j\neq i}\frac{xcoord-xcoord_j}{xcoord_i-xcoord_j}$$

and summed the values of $\phi_i * x_i$ to get $x_0$. The shares I've selected are a subset of size $t$ of the list of numbers from the application of the polynomial above. The polynomial validates i.e. $a_0 == x_0$.

I've also tried the method specified in this explanation of Shamir's Secret Sharing but both seem to have the $t>8$ reconstruction problem (in fact the latter had a sign problem, for odd values of t that I could not resolve).

Does anyone have any thoughts on how to investigate further or even resolve? Could the use of the Barycentric form help fix this as per this answer?

The problem (thanks for the prompt Ido) was the use of PBC's element_mul_si instead of element_mul. This caused the polynomial calculation to loose precision(by rolling over I think) on larger values of t.

I now use element_mul during polynomial calculation in this commit and it works perfectly. Python Charm does not use element_mul_si hence the issue does not show up in the HoneyBadger implementation of TCG.


Hash ElGamal CCA approach With this Elgamal variant defined below, we have covered in lecture but I do not still understand how a CCA could work against it. Is the use of the homomorphic nature of the encryption something you could use?

$c=\langle g^r, \mathcal{H}(y^r)\oplus m \rangle$

What could be a CCA against this type?

I refer to you to a nice explanation of the basic attack on the "native" ElGamal scheme: How does chosen ciphertext attack on Elgamal work?

The difference between the native and this hashed scheme you outlined above is that the hashed elgamal version allows to encrypt a m-bit string message for any m since you use XOR, as long as the hashing function you use can output m bits. In the native ElGamal scheme, you have to map m into a group element, which may or may not be OK depending on which group you use. See Boneh's paper: section 4.1.
For example, it is not straightforward when using Ed25519 with the special encoding, but solutions exists such as the elligator mappings.


Checking a file for integrity and authentication A checksum is a small-sized datum derived from a block of digital data for the purpose of detecting errors which may have been introduced during its transmission or storage. It is usually applied to an installation file after it is received from the download server. By themselves, checksums are often used to verify data integrity but are not relied upon to verify data authenticity.
  [wikipedia]

How would you verify data authenticity then? Would transferring a file through the https protocol and then comparing it's hash confirm that it's genuine, or is there more to it than that?
And how would you hash a big 40+gb zip file, would you have to hash the entire contents of the file and, each file within the zip file?

I couldn't find any good resources on how to hash verify big files.

This relate to the difference between authenticity and integrity.

Authenticity:
you are sure of the identities involved:
Where does the data come from?

Integrity:
you are sure that the content has not been modified:
Was there an error during the transmission?

The second is usually provide through a Checksum (such as any hash function) e.g. $$SHA-3(\ M\ )$$
while Authenticity requires a MAC (Message Authentication Code), often in a form of a HMAC or KMAC e.g.  $$SHA-3(\ K\ ||\  M\ )$$
or a signature e.g. $$ Sign_{K_{priv}}(\ SHA-3(\ M\ )\ ) $$
Remark:$$\textbf{Authenticity} \implies \textbf{Integrity}$$

As for your second question:
You have to hash the whole file, hashing sub contents will increase the workload but will provide you integrity over small part and allow you to detect which part has been corrupted.
Note:
To hash big files you might want to have a look this article: Is SHA-3 slow ?
Further readings:

What are the differences between a digital signature, a MAC and a hash?
What is the advantage of digital signatures over message authentication codes?
How is digital signature different from a message authentication code (MAC)?


Proof of probability of weak keys in block cipher My textbook has the following theorem:

  Given a block cipher with a key length of K bits and blocksize of n bits as well as t plaintext-ciphertext pairs, the expected number of false keys which encrypt all plaintexts to the corresponding cipher text is $$2^{k - tn}$$

This makes sense if you consider DES gives us roughly $2^{-8}$ for a single plaintext-ciphertext pair as explained here. However the author doesn't give a proof to this theorem, I want to know if it's possible to prove it and how can I prove it? I thought about using induction but I'm having some problems about which assumptions I can make

However the author doesn't give a proof to this theorem, I want to know if it's possible to prove it and how can I prove it?

The author likely doesn't bother with the proof because it is so straight-forward; we also need to note that the figure $2^{k-tn}$ is not exact, but merely an approximation (albeit a very close one for realistic key and block sizes); once we skip the approximation, the proof becomes slightly less trivial.

First, the assumption we make: that the cipher acts like an ideal cipher, in particular, if we give an incorrect key to the cipher, that it generates random ciphertext blocks (and ones that are independent of the ones generated with the correct key).

Then, if we consider giving the known $t$ plaintexts to the cipher with an incorrect key, it will generate $t$ random ciphertexts, each of which is $n$ bits.  Given that these are random, the probability that all $n$ of them are precisely the same bits as the expected ciphertext bits is $2^{-nt}$ (as there are a total of $nt$ bits, all of which need to be precisely the correct value.

Now, this isn't quite accurate.  The block cipher, even given an incorrect key, is still a permutation, and assuming that all the plaintext blocks are distinct, all the generated ciphertext blocks will be distinct.  This means that, if $t>1$, that certain outputs (such as the all-0 output) will be impossible (because the cipher will never encrypt two different plaintexts into the same all-0 ciphertext block); the precise probability for an incorrect key is $(2^n-t)! / 2^n! = \frac{1}{2^n \cdot (2^n-1) \cdot (2^n-2) \cdot … \cdot (2^n-t+1)}$.  If $2^{n/2} \ggg t$, that is, we're considerably under the "birthday bound", this is quite close to $2^{-nt}$

Now, this is the expected value for one incorrect key, and the total expected value is the sum of the expected values for all the various disjoint possibilities.  There are a total of $2^k$ incorrect keys, and so the total expected value is $2^k \cdot 2^{-nt} = 2^{k - nt}$

Now, this also isn't quite accurate, there are $2^k-1$ incorrect keys (as we assumed that there was a correct key); obviously, for the key sizes we use, $2^k$ is quite a good approximation; we've also seen that $(2^k-1)(2^n-t)! / 2^n!$ is the precise (if generally less useful) expectation.


Optimal compression ratio in compression function So we'll have a transform that maps any of $A=2^a$ possible inputs to $B=2^b$ possible outputs. $a$ is generally fixed as the number of bits in the input, and $b$ is determined by the transform used. We'll name the difference $d=a-b$.

There's 3 main groups:

$d$ is large and the output is much shorter than the input - we see this in SHA1, SHA2 and a lot of other hashes like it, where they use it to absorb blocks.
$d=0$, so it's bijective. As far as I know SHA3 is the only hash that does this, and it has a large hidden internal state. Side question, for cases where there isn't some extra internal state, it being bijective implies it's reversible, which is quite bad for hashes right?
$d<1$ is small and the output is the same length as the input - a compression function, the interesting one and the one I'm concerned with. Around what value of $d$ should I aim for? Some considerations are obvious, like keep $d$ very small if the transform is iterated such as in a password hash, but otherwise I'm at a loss. Of course we can't just choose $d$ since it's based on the transform, but we can design the transform and pick constants to get $d$ around the desired value. So what order of magnitude should $d$ be? Maybe $d\approx a^{-\frac{1}{2}}$?

Main purpose of this is for hashing. I was going to try making my own hash.

You said ‘hash’, but you didn't say what properties you wanted.  For example, the ChaCha core $C\colon \{0,1\}^{256} \times \{0,1\}^{128} \to \{0,1\}^{512}$ is called a hash function and used in CTR mode to make a one-time pad $C(k, 0) \mathbin\| C(k, 1) \mathbin\| \cdots$ to encrypt a message under key $k$.  Poly1305 is called a universal hash function family and is used to make a one-time authenticator for a message under a single-use secret key, but is useless for encrypting messages.
Are you talking about building a variable-size collision-/preimage-/second-preimage-resistant unkeyed function $H\colon \{0,1\}^* \to \{0,1\}^n$ out of a fixed-size function $f\colon \{0,1\}^a \to \{0,1\}^b$?  That's one of the outmoded definitions of ‘hash function’ in cryptography—outmoded because there are other properties like (enhanced) target collision resistance, prefix-PRF, etc., that turn out to be at least as important in protocol design, and are sometimes summarized as indifferentiability from a random oracle.  And if that is what you're looking for, it's hard to imagine how $d$ could turn out to be anything other than a nonnegative integer.
But assuming that is what you're looking for, here are some comments on common values of $a$, $b$, and $d$:
The design principle of SHA-256 is to iterate a block cipher $E_k$ in Davies–Meyer form:

Break the padded message into 512-bit chunks $m_0, m_1, \dots, m_{\ell - 1}$.
Let $h_{-1} = \mathrm{IV}$ be the standard 256-bit initialization vector.
Compute $h_i = E_{m_i}(h_{i - 1}) \oplus h_{i - 1}$.
Reveal $h_{\ell - 1}$ as the hash.

Here a = 768 and b = 256, so d = 512.
The design principle of BLAKE2 is similar, except it uses a tweakable block cipher $E_{k,t}(m)$ instead of an ordinary block cipher, in HAIFA form, which fixes some potential pathologies of naive Davies–Meyer or Merkle–Damgård form, so that it goes beyond collision and second-preimage-resistance to simulate a random oracle in other dimensions.
The design principle of SHA3-256 is to iterate a fixed permutation $\pi$ in sponge form:

Break the padded message into 1088-bit chunks $m_0, m_1, \dots, m_{\ell - 1}$.
Let $h_{-1} = 0^{1600}$.
Compute $h_i = \pi(h_{i - 1} \oplus (m_i \mathbin\| 0^{512}))$.
Reveal the first 256 bits of $\pi(h_{\ell - 1})$ as the hash.

Here a = 2688 and b = 1600, so d = 1088.
Which is better—HAIFA or sponge?  It depends on whom you ask!  There's no evidence to suspect any weakness in BLAKE2 or SHA-3.  Maybe it's easier to make something faster out of HAIFA—certainly BLAKE2 is much faster than SHA-3.  Maybe it's easier to prove security reductions of compositions to primitives when the primitive is a single fixed permutation instead of a PRF made out of a PRP.
Note that in all of these compositions one of the basic components is a permutation—$E_k$, $E_{k,t}$, or $\pi$—but the fact that the component is reversible doesn't mean there's any security problem in the composition.  Knowing the first 256 bits of $\pi(s)$ for a random permutation $\pi\colon \{0,1\}^{1600} \to \{0,1\}^{1600}$ doesn't help you to guess a 256-bit secret $s$: you'd have to fill in 1344 bits you don't know, which is unimaginably harder than just guessing $s$ in the first place!


Cryptanalysis of an certain algorithm Is an attacker of an cryptographic algorithm allowed to change order of sub-keys but not changing their number in attack? Would it be called an attack on broken algorithm of cipher?

The attack you describe (at least insofar as I understand it) is essentially a type of related key cryptanalysis, which is a valid but very strong attack model that is not always accepted by cryptographers as showing serious weaknesses in a cipher.  In terms of the plausibility of such an attack, the general idea is that if the expanded key (consisting of all the round keys) is stored or transmitted insecurely then it might be possible for an attacker to alter them in some particular way, even if she cannot simply read them directly.  The alterations to the rounds keys would induce the cipher to behave differently in a way that enables the attacker to deduce bits of the key.

This scenario might seem to stretch credulity a little too much, which is why not all cryptographers are concerned about related key attacks.  However, weaknesses in a cipher under related key attacks can often inspire breaks under the more conventional one-key model (e.g. Biham's 'key schedule' related-key cryptanalysis of LOKI inspired slide attacks, and differential related-key cryptanalysis techniques aided the development of biclique cryptanalysis).  We also may be interested in the strength of a cipher when it is being used as the core of a hash function, where the attacker can directly control the 'key' input.

You do have to be a little careful about with the type of "key alteration" you propose (i.e. transposition of round keys).  So long as the attacker is restricted to just transposing round keys that should be fine.  But if the attacker is given more fine-grained control, to the point where she can transpose individual bits of the round key, then that is much too strong of a capability to grant her, because not even an Ideal Cipher can resist an attacker with that ability.  Related key attacks are only really "interesting" (in the sense of revealing a structural weakness in a particular cipher) if an Ideal Cipher can in principle be secure against them.


AES-CBC Padding: Why always attach 16x 0x10 pad? Why do we have to always attach a 16x 0x10 pad even though the last block is already at block-length?

You are talking about the PKCS#7 padding. There is a simple reason;  assume that when the last block is full and you don't apply the padding before encryption and then send the message.

When decrypting, the receiver needs to see a padding pattern to remove the padding. What if the last byte is 01 of the message? is it padding or the message itself? Similarly with low probability same if the last bytes are 0202, and so on.

Instead of this, padding with 10 for an additional extra plaintext block solves the problem.

There are no reasons to perform this particular kind of padding if the plaintext size is known in advance. It may also not be required if the size of the plaintext can be determined by other means. For instance, ASCII encoded text will generally not contain a byte set to zero, so zero-byte padding may be used if the text is not a multiple of the block size. PKCS#7 padding can however always be removed deterministically, independently of the contents of the message.

Many modes, especially streaming modes such as the popular CTR (counter) mode and derivatives - such as the authenticated GCM mode - do not require padding at all;  they operate on plaintext bytes rather than plaintext blocks.


Decrypting without using the private key Let $g$ be a generator of a multiplicative group $G$ of order $q$, $x$ be a private key, and $h=g^x$ be a public key of an exponential ElGamal cryptosystem.

Given a ciphertext $c$ produced as the ElGamal encryption of a given plaintext $m$, that is $Enc(m,h,r)=(g^r, g^m h^r)=(R,S)=c$, it is obvious that this ciphertext can be decrypted by using the private key $x$.
So $Dec(c,x)=\log_g \frac{S}{R^x}=m.$

However, it seems also quite clear to me that another way of decrypting it without being in possession of the private key is by knowing the random value $r$, so $\log_g \frac{S}{h^r}=m$.

Let's assume we have a protocol in which Alice first publishes some encrypted message, and after a while, she wants to reveal it by just revealing what the random value $r$ was. This may remind a Pedersen commitment scheme, with the difference that when opening the encryption, I would like Alice to reveal only $r$, and not both $r$ and $m$.

Does this make any sense? How certain can Bob be that the value $r$ that Alice just revealed, is the one she actually used to generate $c$, and she didn't make it up?

If $(G,q)$ are public authentic parameters and Alice publishes $(h,R,S)$, then if Alice later publishes $r$, Bob needs to check if $g^r=R$, which fixes $r$. Consequently, when computing $\log_g S/h^r$ also fixes $h$ and the exponent of $S$ is fixed. Changing $m$ to $m'$ would require to solve $m+rx\equiv m'+r'x \pmod{q}$ for $r'$. However, since $r$ is fixed in $R$, this does not work out without changing $R$ to $R'\neq R$ and same argument for $x$ which would change $h$ to $h'\neq h$ (but this can be detected).

But why should Alice not give $(r,m)$ to Bob and Bob runs $Enc(m,h,r)$ again and checking whether the computed result matches $(R,S)$ previously published by Alice? This would also be more efficient as you avoid computing $\log_g S/h^r$.


Diffie-Hellman problem: is DH still secure if $g^{a^2}$ is known? Let, $g^{a}$, $g^{b}$ are known elements, where $g\in G$ and $a, b\in Z_q$. According to Computational Diffie-Hellman (CDH) assumption, it is hard to compute $g^{ab}$.

If $g^{a^2}$ is also known then is it still fall into Computational Diffie-Hellman assumption? In other words, if $g$, $g^{a}$, $g^{b}$, $g^{a^2}$ and $q$ are known, is it still hard to compute $g^{ab}$?

No, the assumption "given $g, g^a, g^b, g^{a^2}$, it is infeasible to compute $g^{ab}$" is not known to reduce to the CDH assumption. In fact, we can even prove a separation in the generic group model (meaning, it is impossible to build such a reduction by using the group operations in a black box way). Intuitively, this is because we do not know how to generate an instance of the first assumption given a CDH instance: it requires computing $g^{a^2}$ from $g^a$, which is already equivalent to breaking the CDH assumption. However, this assumption remains a plausible one: a scheme whose security would reduce to this assumption would be considered secure in the crypto community. In fact, many assumptions of this type which are variants of the CDH assumption are common in the crypto community.


Quadratic residuosity problem reduction to integer factorization How can one show how to reduce the quadratic residuosity problem to an integer factorization?

Factoring $\longrightarrow$ square roots.
Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of $a$ modulo $p$; for $p \equiv 1 \pmod 4$, you can use Cipolla or Tonelli–Shanks.

Computing square roots modulo a composite of known prime factorization is easy: compute square roots modulo each factor separately and combine with the Chinese remainder theorem.
Square roots $\longrightarrow$ factoring.
It is well-known that an oracle $S$ for finding square roots of random elements of $\mathbb Z/n\mathbb Z$ can be used to make an efficient algorithm to factor $n$: pick $x$ at random, and if $y := S(x^2) \not\equiv \pm x \pmod n$, then $\operatorname{gcd}(x \pm y, n)$ is a nontrivial factor of $n$ since $y^2 \equiv x^2 \pmod n$ so $n \mid x^2 - y^2 = (x + y) (x - y)$, and by hypothesis neither $x + y$ nor $x - y$ is congruent to zero modulo $n$.
Factoring $\longrightarrow$ quadratic residuosity.
Deciding quadratic residuosity for a prime modulus $p$ is easy: just compute the Legendre symbol $(a|p) \equiv a^{(p - 1)/2} \pmod p$ and see whether it is 0 or 1.

Deciding quadratic residuosity for a composite modulus of known prime factorization $n = pq$ is easy: $a$ is a quadratic residue modulo $n$ iff it is a quadratic residue modulo $p$ and a quadratic residue modulo $q$, which can be computed by the respective Legendre symbols.
Quadratic residuosity $\stackrel?\longrightarrow$ factoring.
We don't know!

If you could find a way to factor $n$ using a decision oracle $D$ for deciding whether random elements of $\mathbb Z/n\mathbb Z$ are quadratic residues, you could publish it in a top-tier conference, because the state of the art to my knowledge is that such a reduction is known only in the generic ring model.


Why should the factors $p,q$ of $n$ be half the bit length of $n$ in RSA? Why do we want the factors $p,q$ of $n$ to be of size half the bit length of $n$ in RSA?

I know $p,q$ need to be large so that it is harder to factor $n$ and if one of $p,q$ is small, then it is more likely to find a factorization by brute force. But why half the bits of $n$ (i.e., $p,q$ must be in range $[2^{(n-1)/2} \dots 2^{n/2}]$)? Is it just that for $p,q$ to be the largest possible they both need to be of size half the bit length of $n$?

They don't need to be restricted to that range. It's just a safe and convenient choice with no downsides.

Having a small p or q enables easier factorization using the elliptic curve method. To avoid ECM being faster than GNFS you need the primes to be larger than about 30% of the modulus (depends on the key size).
Having a large p or q reduces performance, because the Chinese remainder theorem based speedup becomes less efficient.
Having a nice power-of-two size for both factors is convenient for the implementer, especially in hardware
If you restrict them to the range $[2^{(n-1)/2} ... 2^{n/2}]$, you get the nice property that you can generate p and q independently and get modulus of exactly the desired size.
It only marginally reduces the number of available primes, which has no security impact.

Personally I'd go even one step further and restrict to $[\frac{3}{4} \cdot 2^{n/2} ... 2^{n/2}]$ because it simplifies key generation (just set the two most significant bits to 1)


Minimum number of independent trials needed to detect a bias Suppose, I suspect that the probability of occurrence of a particular bit as $0$ is $.558$. Since, it is not $.5$, so this is possibly a bias. Now, my question is:

  What is the minimum number of independent trials I need to confirm my result?

I mean, observing this scenario for, say 100 times, must not be convincing. There should be a theoretical result regarding this. It would be very helpful if someone links such papers while answering.

What I am looking for is: Suppose I suspect a possible bias of $0.5 \pm x$, $x \in (0, .5]$. Then, at least, say $2^{1/x}$ trials are need to confirm my suspicion.

Related: https://stats.stackexchange.com/questions/417981/calculate-the-number-of-trials-needed-to-achieve-certain-number-of-successes-at

I searched the web, and finally (I think) I got:

In page 47, 48 of this thesis, it is mentioned that -

  To detect a bias of $p(1+q)$ (where $p$ is the probability for an Uniform Random event), we need roughly $\dfrac{1}{pq^2}$ samples.


SHA-3 maximal number of zeros (Padding) What is the maximum number of zeros, which are appended at the input- padding in messages? How large must the message be for this?

Let's start from the top and work down, using FIPS 202 as reference. Note that the KECCAK paper uses a somewhat different notation (!).
$$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M | 01, 224)$$
$$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M | 01, 256)$$
$$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M | 01, 384)$$
$$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024] (M | 01, 512)$$
this is explained as:

In each case, the capacity is double the digest length, i.e., $c = 2 \cdot d$, and the resulting input $N$ to $\operatorname{KECCAK}[c]$ is the message with the suffix appended, i.e, $N = M | 01$.

Now it is also given that

$\operatorname{KECCAK}[c] = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], \operatorname{pad10*1}, 1600 – c]$.

where $\operatorname{SPONGE}$ is defined as $\operatorname{SPONGE}[f, pad, r]$. This means that $r = 1600 - c$ which can be rewritten as $r = 1600 - 2d$.
This is the information that we need for chapter 4: SPONGE CONSTRUCTION

The padding rule, pad, is a function that produces padding, i.e., a string with an appropriate
length to append to another string. In general, given a positive integer $x$ and a non-negative
integer $m$, the output $\operatorname{pad}(x, m)$ is a string with the property that $m + \operatorname{len}(\operatorname{pad}(x, m))$ is a positive
multiple of $x$. Within the sponge construction, $x = r$ and $m = \operatorname{len}(N)$, so that the padded input
string can be partitioned into a sequence of $r$-bit strings. Algorithm 9 in Sec. 5.1 specifies the
padding rule for the KECCAK functions and, hence, the SHA-3 functions.

Here $N$ is the input string of Keccak / SHA3 and $m$ is therefore the length of the input string (in bits).
So great, we now can finally look at the definition of $\operatorname{pad10*1}$:

Within the sponge construction, $x = r$ and $m = \operatorname{len}(N)$

Let $j = (– m – 2) \bmod x$.
Return $P = 1 | 0^j | 1$.

Now negative modular calculations can be a bit confusing, but it is clear that no matter what, the maximum value of $j$ and thus the number of zero's is $x - 1$ or $r - 1$ as $x = r$. This is because $m$, the input length, can have any non-negative value. As this is for the sponge, this is also true for $\operatorname{KECCAK}[c]$ and therefore SHA3.
Now $m = \operatorname{len}(N)$ but $N = M|01$. In other words, the input $m$ is the message length - say $l$ - plus two bits. So that means that $j = (– m – 2) \bmod r = (– (l + 2) – 2) \bmod r = (–l - 2) – 2) \bmod r = -l - 4 \bmod r$. This maximum will be reached for $l = N \cdot r - 3$. This is kind of expected; if you have a minimal overhead of 4 bits for the padding then a message three bits shorter than the $r$ will require the maximum padding as the padding will overflow into the next block.

SHA3-224 means $r = 1600 - 448 = 1152$, so for $N \cdot 1152 - 3$ the maximum number of zero's is reached, which will be $r - 1 = 1151$ zero's.
Let's check this for $N = 1$: $\operatorname{len}(\{0,1\}^{1149}|01|1|0^{1151}|1) = 1149 + 1151 + 4 = 2304 = 2 \cdot 1152$. So that indeed leads to two times the rate $r$.

The usual input of hash algorithms isn't in bits, but in 8-bit bytes. In that case the input would simply be $N \cdot r$ for a maximum number of zero's that's of course $8 - 4 =4$ bits smaller. The number of zero bytes is of course $r / 8 - 2$ bytes.
Lets validate this again using SHA3-224. The first block of $r$ bytes would just be the message and the last block of $r$ bytes would consist of $06 | 00^{142} | 80$ in hexadecimals. This seems strange but that's because NIST uses little endian and flipped bit order (low order bits leftmost in the padding, but rightmost in the bytes, i.e. bit $b_7$ is on the right).


When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)? SIS (Short Integer Solution) Problem : Given $m$ uniformly random vectors $a \in Z_q^n$, grouped as the columns of a matrix $A \in Z_q^{n.m}$, find a nonzero integer vector $z \in Z^m$ with $||z|| \leq \beta \lt q$, such that $Az = 0 \mod q$.

Concerning the hardness of the problem, there is a theorem that states that : for any $m = poly(n)$, $\beta \gt 0$, solving $SIS$ is at least as hard as solving other approximation problems like $GapSVP_\gamma$ (Decisional approximate Short Vector Problem) and $SIVP_\gamma$ (Short Independant Vector Problem) on arbitrary n-dimensional lattices, for some $\gamma = \beta.poly(n)$.

My question is : what are the maximum values of $\beta$ and $m$ relatively to $n$ for which the problem stays hard to solve? For example in the $GPV$ signatures they consider $m = 2n\log q$, and $\beta = 6n\log q$. But can we consider too $m = 4n\log q$? $8n\log q \dots $? $n^{100} \log q$? $\dots$ Same thing goes for $\beta$. What's the limit for these parameters for which the problem starts becoming easy?

The problem becomes easy (as in `solvable in polynomial time') if $$\beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k}$$ for some constant $C$. This follows from:

volume $q^{n}$ for the $q$-ary kernel lattice
a Hermite approximation factor of $C^k$ for lattice reduction algorithms (LLL/BKZ) over a lattice of dimension $k$
noting that one can `ignore columns' to work with a lattice of dimension $k \leq m$

Some more details in Section 3 of

https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf

(where $C=\gamma_2$ because we just consider what is provable with LLL, but all other smaller fixed constants $C>1$ are also reachable in polynomial time)


Maintaining validity of ZKP throughout re-randomization of homomorphic ciphertext without linkability to previous ciphertext Question:
How is it possible to adapt a ZKP for a homomorphic ciphertext to still be valid after said ciphertext has been re-randomized?

Context:
In a lot of e-voting systems homomorphic encryption is used to tally the individual votes preserving the privacy of the individual voters as only the total tally is revealed. Each voter must provide valid ZKP's proving that their vote is correctly formed and one of the possible values.

A way to achieve privacy is to re-randomize the ciphertext as well as the corresponding ZKP. This seems to be possible using Groth-Sahai proofs though I do not understand how as the ZKP somehow has to be bound to the ciphertext.

First (if it's not the case) you have to read carefully the original Groth-Sahai paper : https://eprint.iacr.org/2007/155.pdf

We can focus on a concrete example to understand why it's possible: in the "SXDH" setting for example (page 24);
Let suppose we have a commit $\vec{c_1}$ for a vector of elements of $G_1$ and
a commit $\vec{c_2}$ for a vector of elements of $G_2$. And a proof $(\vec \pi, \vec \theta) $

You can change randomize the commitment $c_2$ (by adding $R'\vec{u}$ to $\vec{c}$ for example), but if you do this the proof will be no more valid.

Then you have to add also the corresponding randomness to the proof, here it means you have to add to $\vec\pi$ $R'\Gamma c_2$.

More generally you have to randomize the commitment and the proof in the same time (Notice that in the groth sahai model commits are not considered as cipher but as part of the proof).