An encryption algorithm does not need a keyspace.  By definition, however, it has one.

It sound to me like your confusion is mainly terminological.  In cryptography, the "keyspace" of an encryption system is defined simply as the set of all possible (distinct) keys that the algorithm can accept.

For example, let's say that we're back in the days of the ancient Romans, and encrypting a message with a simple shift cipher.  Obviously, to encrypt and decrypt the message, we need to know the correct key: the number of letters by which the alphabet is shifted.

Clearly, "1" is a valid key for this cipher, since we can indeed shift the alphabet by one letter.  So is "2", and "3", and so on.  Equally clearly, "1.5" is not a valid key, since it makes no sense to shift the alphabet by one and a half letters.  Thus, while the keys 1, 2 and 3 are all part of the keyspace, 1.5 is not.  Neither is $\pi$ or $\sqrt{-1}$ or "banana".

(A somewhat more subtle question is whether the keyspace for a shift cipher should include "0" or "-1" or "999".  Certainly, an alphabet shift of zero letters is possible; it just doesn't obscure the message in any way, and is thus completely insecure even by ancient Roman standards.  Similarly, we could shift the alphabet by 999 letters — but, since neither the modern nor the ancient Roman alphabet actually has that many letters, it will just wrap around and be equivalent to some smaller shift amount.  Generally, for cryptanalytic purposes, we'd want to ignore such obviously equivalent keys, and just say that the keyspace of the shift cipher has as many (distinct) keys as the alphabet has letters; or one fewer, if the zero key is not allowed.)

Why do we care about the keyspace, or its size, then?  Well, for one thing, a simple way for someone to attack a cipher is to try to decrypt a captured message with every possible key, and see which of the results makes sense.  The bigger the keyspace, the more resistant the cipher is to this naïve attack.  (Furthermore, in modern crypto, we actually try to design our algorithms so that, hopefully, this naïve attack is the best possible one, or at least close to the best.  Thus, unless someone breaks the cipher by finding a more efficient attack, the size of the keyspace is a direct measure of the strength of the algorithm.)

Also, when we do pick our encryption key, we obviously need to pick one that belongs in the keyspace; otherwise, by definition, it will not work.  Indeed, the safest choice is generally to pick the key uniformly at random from the entire keyspace.  If we don't (and the attacker knows or can guess how we picked our key; which we generally cannot prove isn't the case), then they can speed up their attack by trying the keys we're more likely to have picked first.  Thus, it's not enough to just know the size of the keyspace; we also need to know what the keyspace is, or at least enough about it to let us pick random keys from it.


Authentication mechanism for low memory, low computing power device

SRP doesn't require very much memory, has a low transmission cost (4 packets), and its CPU usage isn't very high (less than 1 second on a low-end 32-bit CPU, but higher on something like an 8-bit CPU).

http://en.wikipedia.org/wiki/Secure_Remote_Password_protocol


Recasting randomly generated numbers to other widths

Well, it rather depends on what you mean by "uniformly distributed".  If you mean that, over all possible lists, each byte position was from a uniform distribution, that doesn't actually tell you that.

Here's the problem: all "uniformly distributed" in this case means is that, in a sufficiently large sample, each value occurs approximately equally often (in the uint_8 case, about 1/256 of the time).

However, it says nothing about correlations, that is, which values tend to immediately follow other values.  It is easy to design a 'random string' that is perfectly uniform, however the adjacent bytes are strongly biased; this means that, when you combine adjacent bytes, each uint_16 will not be equally represented.  For example, consider a string where, after a byte value $X$, the next position is also the value $X$ with probability 1/2+1/512, and a value $Y \neq X$ with probability 1/512.  This sequence is equidistributed; however if you combine uint_8 values, the resulting sequence is strongly biased.

However, if by "uniformly distributed", you mean that the $N$-byte sequence as a whole was selected uniformly from all possible $256^N$ possible sequences, then yes, uniformness is preserved by combining adjacent elements.

Now, getting down to practice: if the list was generated by a cryptographically secure random number generator (CSRNG), then we can assume that combining adjacent elements is harmless.  That's because we assume that the output of a CSRNG cannot be efficiently distinguished from random by any method; if the attacker could distinguish it by combining adjacent bytes, that would mean that we really didn't have a CSRNG in the first place.

On the other hand, if the list was generated by a statistical random number generator (that is, a generator that was designed to generate output that "looks" random, that is, passes some standard statistical tests), then it's a tad trickier.  Real life generators can have problems when you combine outputs at the "wrong" size; however it is unlikely that one used in practice would have a problem with combining only 2 or 4 elements.  So, in this case, you're probably safe (although you might want to check with the generator to be sure)


What math makes it safe to offer a stolen-password check service?

If we think of this as secure multi party computation then we want to calculate a function on two inputs the DB and the password. We want to know if the password exists. We don't want the db holder to learn anything about the password and the password holder to learn anything about the db beyond the answer to the question does the password exist. This is definitely solveable with generic secure multi party computation solutions. You had an extra requirement of the db holder not getting the answer to the question which I suspect may not be possible(it might be).
See: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation


What is "msg = group.random(GT)" in Charm encryption schemes?

In real world applications Attribute-based Encryption (ABE) is used in conjunction with a symmetric cipher, because you can only encrypt group elements with ABE. In this case it is the multiplicative group $G_T$.

The number of bits is limited when you try to represent text messages (bit strings) with a group element, because the size of the group is derived from a prime. In Charm it is most likely 512 bit prime. You cannot represent messages that are bigger than any group element, if you would have a mapping function to map bit strings to group elements and back again.

Generally something else is done. It is called hybrid encryption in the context of ABE. The text message is encrypted using AES or other symmetric ciphers and the random key that was used is derived from the random $G_T$ element.

Generate a random $G_T$ element with el = group.random(GT).
Generate bytes from el e.g. like this extractor(el) or even hashlib.sha256(str(el)).digest() which can be directly used as the AES key.
You would encrypt your text message with a symmetric cipher like AES-256 using the previously generated key.

Charm provides something for steps 2 and 3: SymmetricCryptoAbstraction.

The schemes that are implemented in Charm don't go this far to implement hybrid version of the scheme, because it would be the same for every one of them. It is unnecessary for the validation of the functionality of the scheme. This is why the message is just a random group element as a placeholder for a real world message.


Efficiency of chaining AES "groups" of blocks

Well, if you have hardware which you can give it a long ciphertext block, and say "decrypt this block in one shot", well, one could argue that reusing the last ciphertext block as the next IV might give some minimal amount of gain; you would concatinate all the ciphertexts in order, and ask for the hardware to decrypt the entire thing -- the result will be the plaintexts all concatinated.  On the other hand, even if you used independent IVs, you could concatinate the blocks as series of [IV, ciphertext blocks] vectors, and so you could still use your fancy hardware to decrypt it all in one shot.

However, arguing about minor efficiency gains misses a larger point -- it is known that generating IVs this way (or in any way where the next IV can be predicted by someone in the middle) can cause cryptographical weakness; that is, someone who can insert their own text can game the system to decrypt low entropy (that is, mostly guessable) texts.  In case you think this is an entirely theoretical attack, well, this is precisely how the Beast attack worked in SSL.

Now, I don't know where an attacker can plausibly inject chosen plaintext into the encryption stream; however it strikes me as likely enough to reject this rather minimal performance gain.


Are there any security flaws in using an involutive S-box?

As pointed out by Aleph and poncho, it is difficult to provide an educated answer without seeing the whole cipher.

One one hand, involutive S-boxes can be used to attack a scheme: e.g., this key-recovery attack against MANTIS observes that since the SBox is involutive, its DDT is symmetric, and uses it against the scheme. This paper by Biryukov shows that involutional components can be used as a leverage to ease distinguishing attacks.

On the other hand, there are block ciphers like ICEBERG which heavily rely on involutional components and are still secure: in ICEBERG, the SBox is involutional, but also the multiplication matrix and even the whole cipher itself (up to the key schedule).

Also keep in mind that the rationale usually given for putting involutional components in block ciphers is that they allow compact hardware implementations (you can reuse the same components for encryption and decryption). So if hardware implementation is not your goal, I would advise against using involutions as they can introduce subtle weaknesses.* As there already exist many great block ciphers, I would also strongly advise against designing your own.*

*unless there is a strong incentive to do so (or if you are doing it for research/recreational purposes)


Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system?

$x$ is not encrypted in Alice’s response. The point is that, even though Eve knows the puzzle number $x$, she has no way to tell which of the puzzles Bob sent is the one with this number, unless she solves all of them (or at any rate half of them, on average).


Byte location of plaintext vs ciphertext when using a block cipher or stream cipher

But why?

It is because the cipher is designed with the avalanche effect property. Namely, changing a single bit in the plaintext (or key) should result in a significant change in the ciphertext. So really, it happens because ciphers are designed with that property.

  What is happening behind the scenes?

Really it is the entire cipher. If you look at a cipher generically as substitutions and permutations, it is the substitutions which really cause the effect, but even then, the permutations contribute to it when multiple rounds are used.


No, there is not.

Your question is not well-posed.  You have not specified whether you want worst-case complexity or average-case complexity, and over what class of SAT instances.  The answer will depend heavily upon those details.

If you want to know what is the world record for an algorithm for 3SAT, measured by its worst-case complexity over all possible 3SAT instances, that's a question to ask on https://cs.stackexchange.com/ or https://cstheory.stackexchange.com/ .  See, e.g., Best Upper Bounds on SAT and Measuring the difficulty of SAT instances.  But don't expect these theoretical results to necessarily have any relationship to the performance of SAT solvers in practice.


Is there an efficient 2 out of 3 secret sharing scheme based on XOR?

Here is a simple (2, 3) secret sharing scheme that used only xor's, and each share is the same size as the secret (assuming that the secret is an even number of bits long)

First, we divide the secret $s$ into two equal sized halves, $s_1, s_2$.

And, we pick two random values of the same size, $r_1, r_2$

Then, the Alice shares are $a_1 = s_1 \oplus r_1$, $a_2 = s_2 \oplus r_2$

The Bob shares are $b_1 = s_1 \oplus r_2$, $b_2 = s_2 \oplus r_1 \oplus r_2$

And the Carol shares are $c_1 = s_1 \oplus r_1 \oplus r_2$, $c_2 = s_2 \oplus r_1$.

It is straight-forward to show that any two parties can recover the secrets $s_1, s_2$

With the Alice and Bob shares, we have $s_1 = a_1 \oplus a_2 \oplus b_2$, $s_2 = a_1 \oplus b_1 \oplus b_2$

With the Alice and Carol shares, we have $s_1 = a_2 \oplus c_1 \oplus c_2$, $s_2 = a_1 \oplus a_2 \oplus c_1$

With the Bob and Carl shares, we have $s_1 = b_1 \oplus b_2 \oplus c_2$, $s_2 = b_1 \oplus c_1 \oplus c_2$

And, with a single share, neither Alice nor Bob nor Carol gain any information about the value of the secret (assuming $r_1, r_2$ was picked randomly).

And, if the total length of the secret is n bits (and so each half of the secret is $\lceil n/2 \rceil$ bits long), the total length of each share is $2 \lceil n/2 \rceil$ bits, which is $n$ bits if $n$ is even.


How is the precomputed table for 25519 Elliptic curve generated?

CodesInChaos created an exact gist in C# for this:
https://gist.github.com/CodesInChaos/ef914909941ce7caf514

It worked for me, took around 8 seconds on a 48MHz 32bit device, but either way, works.
My C port can be found here
https://gist.github.com/irfansehic/9c0b204845370f372bdfccfb66ec5942


Exchanging encrypted messages, and decrypting without a public key?

You're describing a form of three-pass protocol, which is a communication mechanism where neither party needs to know each other's secret key. Wikipedia describes a helpful metaphor using a box that can be locked by two padlocks:

First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice. When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob. When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice.

I assume you're using multiplication and division simply as example functions, but as others have mentioned these aren't suitable operations for this task because they're too easy to reverse. However there do exist actual encryption and decryption functions which do work this way - the necessary property is for the operations to be commutative, so that the encrypting and decrypting do not need to be done in a certain order.

In order for the encryption function and decryption function to be suitable for the Three-Pass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).
...
A [further] necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(r,m).

This second condition eliminates multiplication and division, since we could look at the three transmitted messages s*m, r*s*m, and r*m and easily compute m from them.


Ed25519 is a signature or just elliptic curve

Your short answer is this: ed25519 is both a signature scheme and a use case for Edwards-form Curve25519. EDDSA generalises this signature scheme to any curve in edwards form (for example Ed448-Goldilocks, Curve41417).

Curve25519 first arrived in 2005-2006 (https://cr.yp.to/ecdh/curve25519-20060209.pdf), a few years before the Edwards Normal form papers on Elliptic Curves. Montgomery curves, the form of curve used for Curve25519, was originally used to speed up elliptic curve factorization (https://cr.yp.to/bib/1987/montgomery.pdf). The original proposal for Curve25519 was for use as a diffie hellman (key exchange) protocol. This is still its use and is now often called X25519.

Later, Edwards came up with his own form of elliptic curve (http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf). DJB, Tanja et al researched these forms and realised they too were fast, especially for signatures and we got Ed25519 (https://ed25519.cr.yp.to/ed25519-20110926.pdf) using the Edwards form of Curve25519. This was later generalised to EDDSA (https://ed25519.cr.yp.to/eddsa-20150704.pdf) so that other curves could be used with the scheme.

So, so far we have the following nomenclature:

Curve25519, Curve41417, Ed448-Goldilocks: generally the name of the curve itself, however it was originally presented (bear in mind they're often presented alongside use cases to justify them, like "it's fast").
X25519, X448, X41417 - DH key exchange schemes using the above curve.
EDDSA, Ed25519, Ed448 - the first being the generic Edwards variant of DSA, plus other fixes, the others being specific instances matched to their curve names.

Confusingly, Open Whisper Systems came up with XEdDSA (https://whispersystems.org/docs/specifications/xeddsa/). To quote them:

  XEdDSA enables use of a single key pair format for both elliptic curve Diffie-Hellman and signatures.

Hence, I suppose "X EdDSA" is taken to mean "exchange and EdDSA" of the given curve. In this instance, the key exchange part still happens using the montgomery form of the curve, but the signature part (eddsa) uses the same curve in edwards form.

As pointed out by Kostas Chalkias in the comments, the X may in fact be a reference to the use of the x-coordinate in curve25519. X25519 is performed on the kummer line, which is a fancy mathematical way to say that it suffices to know the x-coordinate to compute the scalar multiplication necessary for X25519 key exchange.


Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

Let the key, message, and ciphertext spaces all be $\mathbb{Z}$, which is in bijection with $\mathbb N$. I'm going to pick a specific bijection by making the non-negative integers map to evens and the negative integers map to odds, and let $\mu$ be the asymptotic density measure applied to $\mathbb{Z}$ using this bijection. We can then construct a one-time pad by setting $c = m + k$. For any (possibly finitely-additive) probability measure $\mu_M$ chosen by the adversary on $m$, and any set $Y \in F$, $(\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\}) = \mu(Y)$. That is, the resulting measure on the ciphertext is uniform, no matter what measure $m$ comes from. I am stating it this way so as to avoid the division inherent in the $P(m \in X | c \in Y)$ expression in your question.
Details: First, we need to show that $\mu$ is translation invariant on $\mathbb Z$. $\mu(A)$ could equivalently be defined as $\lim_{n \to \infty} \frac{A \cap [-n, n]}{2n + 1}$. To see that translation invariance holds, notice that $|[-n, n] \cap A|$ and $|[-n, n] \cap (A - x)|$ only differ by at most $2 x$, since $[-n, n]$ and $[-n + x, n + x]$ overlap everywhere except for $x$ points at either end. This becomes irrelevant in the limit as $n \to \infty$.
Next, we need to evaluate the product measure. Unfortunately product measures do not seem to be very well defined for finitely additive measures. I will pick one product measure, but in general it is not unique.
\begin{align*}
(\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\})
&= \int_{\mathbb Z} \mu(\{k \in \mathbb Z \mid m + k \in Y\}) d\mu_M(m) \\
&= \int_{\mathbb Z} \mu(Y - m) d\mu_M(m) \\
&= \int_{\mathbb Z} \mu(Y) d\mu_M(m) \\
&= \mu(Y) \\
\end{align*}
Here we have used that $\mu$ is translation invariant on $\mathbb Z$ and that $\mu_M$ is a probability measure, so the integral (i.e., expected value) of a constant is that constant.
However, none of this is physically realizable, at least with a digital computer. Any way of generating a random key is going to give a distribution that has countable additivity, since it can always be broken down into discrete choices, with each outcome having paths leading to it with only have a finite number of choices. I don't think it is physically possible in general, but I have less justification for that.


In the case of a GCM-based ciphersuite, there is no MAC key. If the tool insists on a size, give it 0.

See RFC5246 section 6.2.3.3 (which discusses AEAD ciphers, of which GCM is one example); it explicitly states that, in this case, no MAC key is used.

In addition, the IV sizes are 4 bytes; these 4 bytes are combined with the 8 bytes from the TLS record to form the 12 byte GCM nonce; see RFC5288 second 3.

And, of course, the encryption keys for GCM128 is 16 bytes, yielding a total of:

  1- Client_Write_Mac_Key - 0 bytes

  2- Server_Write_Mac_Key - 0 bytes

  3- Client_Write_key - 16 bytes

  4- Server_Write_key - 16 bytes

  5- Client_Write_IV - 4 bytes

  6- Server_Write_IV - 4 bytes


How can a Encrypt-And-MAC scheme be insecure if the encryption is CCA secure?

Note that the security notion targeted by MACs is not IND-CCA, but EUF-CMA (Existentially Unforgability against Chosen Message Attacks).
You can read the formal definition on page 156 here: https://cseweb.ucsd.edu/~mihir/papers/gb.pdf.

Suppose we have a MAC scheme $M =(\mathcal{K}, \mathsf{MAC}, \mathsf{VF})$ which is EUF-CMA secure. Let's create another MAC scheme $M' = (\mathcal{K}, \mathsf{MAC}', \mathsf{VF}')$ which is still EUF-CMA secure, but which provides absolutely no privacy of the message. It is defined as follows:

$$\mathsf{MAC}'_K(m) := m || \mathsf{MAC}_K(m)\\
\mathsf{VF}'_K(m, t) = \mathsf{VF}'_K(m, m' || t') := \text{return 1 iff } m = m' \text{ and }  \mathsf{VF}_K(m, t') = 1.$$

I leave it to you to prove that $M'$ is EUF-CMA secure. However, what can you say about the security of your combined scheme with $M'$ as the MAC function?

If you are interested in learning more about the E&A mode and the security of generic composition in general (i.e., EtA vs AtE vs E&A), then the standard reference is:
"Authenticated Encryption: Relations among notions
and analysis of the generic composition paradigm
" - containing full proofs and counter-examples.
For more on AtE and E&A in particular, look at "The order of encryption and authentication for protecting communications (Or: how secure is SSL?)".


why inverse in diffie-hellman protocol will not give same value?

In DH if you want to compute $g^a$ from $K$ you have to know $b$ (which the legitimate receiver of $g^a$ clearly knowns, so this does not really make sence). This party can compute the inverse of $b$, namely $b^{-1}$, and then compute $g^a=K^{b^{-1}}$. Note that this is not the same as $(K^b)^{-1}=(g^{ab})^{-1}$ (as I will discuss below). But that is not related to the security of DH.

The security behind DH is the computational DH problem, i.e., an eavesdropper learning $g^a$ and $g^b$ cannot compute the shared secret $K=g^{ab}$. But clearly the two parties doing the exchange can, as they hold $b$ and $a$ respectively. So for instance the party holding $a$ and received $g^b$ can compute $(g^a)^b$. Both parties holding $K$ can then use this shared secret to derive some symmetric key for encryption of any messages they want to communicate.

Note that in ElGamal (which may be seen as a non-interactive DH using the public key as static DH key of the receiver) you have $(c_1,c_2)=(g^k,mg^{xk})$ as a ciphertext and $h=g^x$ as the public key and $x$ as the secret key. This means that you encrypt a message using the DH key. Then you decrypt as $m=c_2\cdot (c_1^x)^{-1}$. Note that $(c_1^x)^{-1}=(g^{xk})^{-1}$ which is the inverse of $g^{xk}$ and will cancel out in the decryption as $g^{xk} \cdot (g^{xk})^{-1}=1$.

Note that nobody would use ElGamal to directly encrypt messages, but one will use hybrid encryption, i.e., use ElGamal to encrypt a random symmetric key and use the symmetric key to encrypt the messages.

Why is it a different thing to compute either $(g^{ab})^{b^{-1}}$ or $((g^{ab})^b)^{-1}$? Well, I think your problem is that you should write the parenthesis as I have done it above, since these are two different things.

Now, $K^{b^{-1}}=(g^{ab})^{b^{-1}}=g^{abb^{-1}}$, i.e., here you exponentiate $K=g^{ab}$ with the element $b^{-1}$ (the invese of $b$) and since $bb^{-1}=1$ you obtain $g^{a}$. In the second case you have $(K^b)^{-1}=((g^{ab})^b)^{-1}=(g^{abb})^{-1}$, i.e., you exponentiate $K=g^{ab}$ with $b$ and then compute the inverse of the resulting element, which does not give you $g^a$ as a result, but $(g^{abb})^{-1}$ which is not equal to $g^a$.

For a concrete setting, if you work in the group ${\mathbb Z}_p^*$ with $p$ being prime and use a generator $g$ of  ${\mathbb Z}_p^*$, then arithmetic is done modulo $p$. So inverses of elements, e.g. $(g^{ab})^{-1}$, are computed in ${\mathbb Z}_p^*$. But, be careful, operations on elements in the exponent of $g$ ($g$ generates the group of order $p-1$), e.g., computing $b^{-1}$ (if you want to compute $(g^{ab})^{b^{-1}}$) are done modulo $p-1$. This clearly requires that $b$ is co-prime to $p-1$, i.e., $\gcd(b,p-1)=1$, that the multiplicative inverse $b^{-1}$ of $b$ exists.


Some sites even suggest using a salt that is the length of the digest of the hash function, created by a CSPRNG, but 16 bytes is generally the minimum salt length used (128 bits).


Is there a developer's resource that ties encryption methods and strengths to the appropriate usage scenarios?

Start with NIST Computer Security Division:

FIPS (Federal Information Processing Standards) specifies multiple use scenarios in their Publications and Special Publications, many of which include the type of scenarios on your short list, as well as related scenarios. These are primarily for federal use, but if your use case matches that of the government their publications will apply.

Additionally, there are numerous books, including one called "Cryptography for Developers", which goes more into the application development side of implementing cryptographic systems. Niels Ferguson and Bruce Schneier of the Twofish team have written several books on practical design and implementation of cryptosystems that focus more on the cryptography side of things.

For more of of an open discussion try the sci.crypt newsgroup, where you can specify a specific scenario in detail and engage in debate; there are also other moderated locations to do this as well.

Hard as I try not to do the "list/recommendation" answer, thats kind of how it turned out, there really is not a better way to answer that broad of a question, individual questions on specific scenarios that are not answerable by the wiki/google method will provide more specific answers.


If you're using a real encryption scheme then no it cannot weaken or strengthen the system because the encryption scheme's security is supposed to be independent the actual data being encrypted. The plaintext could be random bytes or all zeroes for all it cares, it will be just as secure.

All this modification achieves is lower your encryption scheme's capacity (number of plaintext bytes you can transfer in a given number of ciphertext bytes) and performance (number of plaintext bytes encrypted by second) as well as complicating the algorithm even further for no reason.

This is, of course, if the adversary only has access to the bytes over the wire. Your implementation of this modification may well leak sensitive information through a side channel (don't know how, but it's possible since you need to add code to implement this, and this code may have bugs and security vulnerabilities, as with any code.

Basically, it doesn't really do anything useful and has only cons, so don't do it.


RSA decryption with small exponent - no "public keys"

Actually, someone who gets two plaintext/ciphertext pairs (after padding; randomized padding foils this attack), and guesses the small exponent can recover the modulus, allowing him to decrypt other ciphertexts.

The relation between plaintext, ciphertext and modulus is:

$$C^e \equiv P \pmod N$$

or

$$C^e - P = kN$$

for some integer $k$.  Hence, if we have two such plaintext/ciphertext pairs $P_1, C_1, P_2, C_2$, the attacker could compute

$$\gcd( C_1^e - P_1, C_2^e - P_2 )$$

and that is likely to be a small multiple of $N$; the actual value of $N$ (which has no small factors) is easy to derive from that.

On the other hand, if everything is kept secret and shared between the two parties, is there any reason you don't go with (say) AES and a shared secret key?


Testing PRNG quality from ECC public keys?

No, not in general without a model for how the PRNG might be bad.  If the PRNG is bad, then there is a test to distinguish it from (say) uniform random bit string outputs; you must then adapt that test to work not on bit string outputs, but on the resulting curve points.  How you do this depends entirely on how the PRNG is bad.


Traditional DES scheme in Unix crypt function

As for the salt, it is a two-character string chosen from the set of printable characters leading to an effective 12-bit entropy.

The fact that every eigth bit of the password is dropped is due to the DES itself: from the 64-bit key, only 56 bits are actually used, thereby dropping 8 of the bits of the key. So, you just input the 64-bit password as the encryption algorithm secret key.

As for the all zeros block, it refers to the plaintext input to the encryption algorithm, which in the DES is a 64-bit value.

Thus you load the password as the key, an all zeros block as the plaintext into the encryption algorithm.

Now the only thing is the encryption algorithm is a tweaked version of the DES: the salt is indeed introduced during the expansion function $E$ of the DES as described in section 4 of this paper. Instead of the standard $E$, a tweaked version $E'$ is implemented.

All of this is well described in this paper.


How to test implementation of primality tests like Miller–Rabin?

Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time).

However, that simple-minded test might miss something.  The Miller-Rabin test can report $n$ is "composite" because of one of two reasons:

Because $g^{n-1} \ne 1 \bmod n$; that is, the Fermat test fails
Because $g^{(n-1)/2^\ell} \bmod n$ is a nontrivial squareroot of 1

If you just throw random composites $n$ at it, then it'll run into the first reason almost all the time.  Hence, it makes sense to deliberately try a value $n$ that fails for the second reason.

One set of values $n$ are known as Carmichael numbers; these are composites with $g^{n-1} = 1 \bmod n$ for all integers $g$ relatively prime to $n$; if we test a Carmichael number with no small factors, the Fermat test will almost always succeed, and so if the test fails, it'll be be the second reason.

One way of finding such Carmichael numbers is to search for prime triplets $6p+1, 12p+1, 18p+1$; if all three are prime, then $(6p+1)(12p+1)(18p+1)$ is a Carmichael number.


Security of AES counter mode vs. CBC mode

The requirement for the AES-CTR input blocks is, that they should be unique during the lifetime of a key. In most of the cases a random 96bit nonce is used with a 32bit counter that starts from 0. If the same input block for AES-CTR occurs twice, AES-CTR is not CPA secure any more. In this case, this can be due to a counter-overflow after $2^{32}$ blocks or due to colliding randomly chosen 96bit nonces (birthday paradox: 50% chance after $\sqrt{2^{96}}$ messages. Consider the following case:

Two distinct 1-Block messages $P$ and $P'$ are sent under the same key $K$ (that might be negotiated beforehand) and with the same nonce $N$. The attacker knows that the related cipher texts $C$ and $C'$ where calculated by XORing them with the keystream (which is based on the nonce and the counter):

$C = P \oplus E_K(N,0)$

$C' = P' \oplus E_K(N,0)$

Then the attacker can simply xor the cipher texts

$C\oplus C' =  P \oplus E_K(N,0) \oplus P' \oplus E_K(N,0) = P \oplus P'$

and he obtains the ''distance'' between the two plain texts. Due to redundancies in the English language, he might be able to determine $P$ and $P'$.

This problem is also known as the "two-time-pad". Once the same keystream is XORed with the plaintext, we get into trouble. Therefore, it is important, that the input for the AES encryption is unique during the lifetime of a key. It does not have to be unpredictable, just unique.


One of the candidate answers you should consider is "for no good reason."  As Provos and Mazières put it in the bcrypt USENIX paper (section 6.1.2):

  Some steps in the algorithm make it doubtful that the scheme was designed from a cryptographic point of view—for instance, the binary representation of the password length at some point determines which data is hashed, for every zero bit the first byte of the password and for every set bit the first byte of a previous hash computation.

That's remarking on a different step of the algorithm than you are, but I suspect it generalizes to the step you highlight as well.  Any halfway decent hash function is going to diffuse its state, and MD5 is no exception, so shuffling the bits of the MD5 output is just suspect.

PHK wrote a history of md5crypt that might be of some use to help us understand his mindset at the time, although it doesn't very much go into nuts and bolts, so it doesn't particularly illuminate the step in question.


Is there a difference between asking for a signature and asking for a decryption in challenge-response authentication?

As long as properly implemented using secure algorithms, there is no real security difference. In both cases the protocol is secure as long as the underlying signature or encryption algorithm is.

However, one difference is the random number used:

In scheme A the numbers must be unique. If the server ever reuses a number, then an adversary could replay a previous signature they have observed.
In scheme B the numbers have to be unpredictable, or an adversary can authenticate just by guessing correctly, but as long as the encryption algorithm is semantically secure, repeats are not a problem.

You need larger random numbers in the first scheme than the second, due to the uniqueness requirement.

As mentioned in the other answers, this is not secure against man in the middle attacks. It could be run in a channel that prevents those. For example, in a typical TLS situation the client would have authenticated the server already, man-in-the-middle attacks would be ruled out, and the server could use either of these to authenticate the client.


A one way Function provably reversible at N applications with the same seed?

F(s,A) can be

a prefix-free encoding of the number of elements in the finite field encoded by s

|| $\:$ the polynomial R (as described at this link) from that finite field $\;$ ||

the output of the degree-at-most-(N-1) polynomial encoded by s over that finite field at the point A

.
Let SP be the set of polynomials of degree at most N-1 over the finite field. $\:$ N input-output pairs would allow one to efficiently find the encoded element of SP by Lagrange interpolation. $\:$ Observe that for any given field, for all A, evaluate-at-A is a linear map from SP to the field. $\:$ Since Lagrange interpolation will always give a compatible polynomial (and not just find one when there is one), that linear map is surjective. $\:$ Thus, for all integers x in {0,1,2,3,...,N-2,N-1}, for any
given N-x input-output pairs and any given z other inputs, the outputs at those x inputs for such a polynomial chosen uniformly from the subset of SP that produces the given N-x input-output pairs are independent and uniformly distributed. $\:$ Observe that any guess at s can only be correct if it gets those outputs correct.

Therefore, for all integers x in {0,1,2,3,...,N-2,N-1}, the probability of guessing s correctly is

at most [[the sampling error for SP] plus [one over [[the number of elements in the field] to the x]]].

This wiki article describes how to do arithmetic over finite fields given an irreducible polynomial over

their characteristic field. $\:$ This paper gives the "simplest" such polynomials for degree at most 10000

over the field with 2 elements, and these two papers give algorithms which can let you confirm that

those polynomials are in fact irreducible (confirming that they're the simplest would be harder).

More generally, over small prime fields, this paper gives a deterministic algorithm

for constructing irreducible polynomials and this paper gives constructions that

are presumably more efficient for degrees divisible by a not-too-small power of 2.


It's hard to be sure without seeing a bit more context, but the paragraph you quoted looks like it's part of a definition of IND-CPA security (ciphertext indistinguishability under a chosen-plaintext attack) for public-key ciphers.
Here's the corresponding definition from the Wikipedia article I linked to above:

"For a probabilistic asymmetric key encryption algorithm, indistinguishability under chosen plaintext attack (IND-CPA) is defined by the following game between an adversary and a challenger. For schemes based on computational security, the adversary is modeled by a probabilistic polynomial time Turing machine, meaning that it must complete the game and output a guess within a polynomial number of time steps. In this definition $E(PK, M)$ represents the encryption of a message $M$ under the key $PK$:

The challenger generates a key pair $PK, SK$ based on some security parameter $k$ (e.g., a key size in bits), and publishes $PK$ to the adversary. The challenger retains $SK$.
The adversary may perform a polynomially bounded number of encryptions or other operations.
Eventually, the adversary submits two distinct chosen plaintexts $M_0, M_1$ to the challenger.
The challenger selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge ciphertext $C = E(PK, M_b)$ back to the adversary.
The adversary is free to perform any number of additional computations or encryptions. Finally, it outputs a guess for the value of $b$.

A cryptosystem is indistinguishable under chosen plaintext attack if every probabilistic polynomial time adversary has only a negligible "advantage" over random guessing. An adversary is said to have a negligible "advantage" if it wins the above game with probability $\tfrac12 + \epsilon(k)$, where $\epsilon(k)$ is a negligible function in the security parameter $k$, that is for every (nonzero) polynomial function $\mathrm{poly}()$ there exists $k_0$ such that $|\epsilon(k)| < \left|\tfrac{1}{\mathrm{poly}(k)}\right|$ for all $k > k_0$."

Unlike the definition you quoted, the Wikipedia version doesn't explicitly represent the adversary as two polynomial-time algorithms $A1$ and $A2$, but it does note that the total computational time used by the adversary must be polynomial, which amounts to the same thing.
What the Wikipedia version does note explicitly, however, is that the adversary is supposed to choose (at least) two potentially vulnerable plaintexts, of which the challenger then encrypts one and sends it back to the adversary, who then tries to guess which of the plaintexts it corresponds to.  The Wikipedia article also notes that the reason this isn't trivial is because the same plaintext can encrypt to many different ciphertexts:

"Although the adversary knows $M_0, M_1$ and $PK$, the probabilistic nature of $E$ means that the encryption of $M_b$ will be only one of many valid ciphertexts, and therefore encrypting $M_0, M_1$ and comparing the resulting ciphertexts with the challenge ciphertext does not afford any non-negligible advantage to the adversary."


What is the smallest plaintext/ciphertext size for an algorithm like?

"Known plaintext" means that the attacker has knowledge of some data and its encrypted counterpart, but he did not choose either (it is "chosen plaintext" when the attacker chooses the plaintext and obtains the corresponding ciphertext, and "chosen ciphertext" when he chooses the ciphertext and obtains the corresponding plaintext). What is "plaintext" depends on what the attacker is trying to attack.

AES is a block cipher: it operates on fixed-size values (the "blocks", 128 bits for AES). When encrypting arbitrary messages, a mode of operation is used; the mode decides how the input data is to be split and mangled and reassembled; the block cipher being only the central part of the process. However, whatever the mode is, at some point some block-sized values will go through the block cipher, because the block cipher cannot use anything else.

So, when discussing attacks on a block cipher (as opposed to: attacks on a symmetric encryption scheme which uses a block cipher and a mode of operation and possibly many other things), we concentrate on the number of (distinct) block values for which the attacker needs to know the plaintext and the corresponding ciphertext. For instance, linear cryptanalysis, when applied on DES, requires $2^{43}$ known plaintexts, i.e. 64-bit plaintext blocks and corresponding ciphertext (DES uses 64-bit blocks). With common modes of operation such as CBC, a block cipher with $n$-bit blocks will be invoked once every $n$ bits of input data, so this requirement translates to $2^{46}$ bytes worth of data (somewhat over 70 terabytes).

Huge amounts of known plaintext are of course impractical. Cryptographers still consider an attack to be "genuine" as long as it requires less than $2^n$ known plaintext and $2^{k}$  effort: if, for $n$-bit blocks, you have $2^{n}$ plaintext/ciphertext pairs, then you have the complete codebook and you do not need the key anymore; and with a $k$-bit key, trying out all possible keys has cost $2^{k}$ invocations of the block cipher. An attack is "real" (in an academic sense) if it does better than that, even by a small margin.


Showing the pairwise XORed random variables are independent

If two binary RVs are uniform, they are independent if and only if the probability that they are equal is the same as the probability that they are unequal (so knowing one does not help in guessing the other).
$$
P[X_1 \oplus X_2=X_2\oplus X_3]=P[X_1=X_3] =P[X_1\oplus X_3=0]
$$
which is clearly $1/2$ since $X_1,X_3$ are unbiased and independent.


Relation between Threshold Cryptosystem and Secure Multiparty Computation ?

Yes and no.

A threshold cryptosystem means the decryption key can be split into $n$ shares such that only $t\leq n$ are required to recover it. That property in isolation is not useful for multiparty computation.

However when you combine a threshold cryptosystem with one that is at least partially homomorphic (meaning you can do some operation, like addition or multiplication, under encryption), then the two properties combined can make a useful basis for multiparty computation.

The model is that each party encrypts their inputs, you use the homomorphic property to do some computation on the ciphertexts while they are still encrypted, and the threshold property enforces that only the final value is decrypted assuming less than $t$ dishonest key share holders. Without the threshold (or at least a distributed $n$-out-of-$n$ key), the keyholder could simply decrypt the inputs and learn everyone's value.

The most famous paper on this is "Multiparty Computation from Threshold
Homomorphic Encryption." This approach is used in lots of papers. A different approach in the same model is "Mix and Match: Secure Function Evaluation via Ciphertexts." It is less used (I think maybe a bit overlooked) but you can do interesting things with it.


I would suggest looking into sharemind. Their setup is a little different from VIFF, there are 3 computation servers and everyone shares their inputs with the computation servers. As long as the computation servers don't collude, privacy is guaranteed. They have also optimized many things. So it may work better for you.

That said, there are some optimizations you could do to VIFF to make things faster. I believe VIFF does comparison by splitting the shared secrets into shares of bits of the secrets. In otherwords, if you were sharing 8-bit integers, then instead you would have 8 sharings of the individual bits of each input. Splitting the shares is a costly operation, but once you have shares of the bits, comparison isn't too bad. So, you could just have the parties share the bits in the first place.


Does encrypting different versions of the same file or folder with the same key make it easier for hackers to attempt the decoding?

For modern ciphers when well-implemented, no: encrypting different versions of the same plaintext(s) with the same key does not make the cipher attackable.

That's because adversaries having access to nearly the same data encrypted multiple times is part of what's assumed in the baseline attack model for all modern ciphers: Choosen Plaintext Attack. The cipher is nearly never the weak link in the security chain. That's true including for AES-CTR.

Problems do occur when the random generator used for the Initialization Vector fails, or is omitted; indeed CTR mode is sensitive to that.

To a lesser degree, some side-channel attacks could be facilitated by multiple slightly different plaintexts.


When using HMAC, does key encoding matter?

The theoretical problem with using text encoded keys, is that it doesn't necessarily conform with how the keys are assumed to be formatted in security proofs such as this one. If you are using HMAC with an underlying hash function that is still believed to meet the requirements of a cryptographically secure hash function, such as the SHA-2 family of hashes, this shouldn't be a problem. The collision resistance assumption of those hashes should be enough to make your alternative scheme no less secure than conventional HMAC.

However, technically, using keys with special formatting might be a problem e.g. if you are using HMAC-h with a broken underlying hash function h, such as SHA-1 or MD5. Both of these two algorithms are based on simple operations such as bit-wise logical operators, addition modulo $2^{32}$ and shifts and rotates. Considering that both hexadecimal encoding and base64 encoding results in octet strings with the high bit of each octet consistently zero, it wouldn't be completely unrealistic that HMAC-h with $K_{hex}$ or $K_{base64}$ might get broken before (or after) HMAC-h with $K$ selected uniformly from $\{0,1\}^k$.


How to measure the complexity of the discrete logarithm problem?

To clarify: I think you ask why we only consider the bitlength of the size of the group and not the actual size of the group for complexity estimates, at least that's what I try to answer.

  Why don't we chose the size of the group as the argument?

We do.
It entirely depends on the conventions you want to use. If $q$ is the size of the group and $n\approx\log_2(q)$ (don't forget that $2^n\approx q$) the bitlength, then you can either write the effort needed for brute-force as $\mathcal O(2^n)$ or $\mathcal O(q)$, with the first being slightly less precise (but not to a point where it matters) and the second being the more accurate one. However the first one nicely shows how the effort needed grows exponentially while the second one may leave you with the impression it's linear at which point people may find it harder to understand "how that's hard, after all it grows only linearly".

  Is there a criterion to know what argument to chose?

Basically whatever you want. If you want to be clear and know your audience understands what you're meaning anyways, use $q$ otherwise use $2^n$ to make it easier to understand.


Is it safe to exchange cryptographic salt and initialization vector in messages?

The answer is yes. There is no problem with sending the IV in the clear. So, this is fine. Likewise, the salt is not there to add entropy so this is also fine.

Having said that, I understand from the code that the application is not using a uniformly distributed (and so high entropy) key. This is a problem and very bad, since it is easy to carry out a brute-force search over the password space. In practice, this is extremely effective.

The salt helps a little bit since it makes it impossible to prepare a time/space tradeoff attack (often called a Rainbow table attack, since this is one instance of the attack). However, it still will not be secure unless a very high entropy key is used.

Another thing which is very strange (and a bit out of scope so I'll refer to it anyway) is that the server is regenerating the key for every block. This is really inefficient (both the key derivation costs and the key schedule for AES is run every time).


How to encrypt data and know it will be secure for at least a few decades?

Is this a good idea?

Not really.

It is rare to find attacks against vetted designs that allow a complete break with a tiny amount of cipher-text.

Assuming you plan to have a unique key (which isn't used anywhere else) for just this few kilobytes of plaintext, it's very unlikely any cryptographic attack could be mounted against any modern cipher that would recover the plain-text.

Honestly, your message is likely to be absolutely fine encrypted with AES.

It's very unlikely someone's missed a key-recovery attack on AES that can be conducted with a few kilobytes of cipher-text.

  Does the nesting increase the security, or does it somehow introduce a new vulnerability?

It is possible to do this badly and introduce a new vulnerability, yes.

  If this is a good idea, which algorithms would be best to use?

Just use AES in GCM mode.

  Would it be better to use asymmetrical algorithms instead of symmetrical ones?

No.

  How many iterations is enough?

One iteration of AES in GCM mode is enough.


How do Latin squares relate to quantum cryptography?

There is a conjecture that a full set of mutually orthogonal Latin squares' existence is linked to the existence of MUBs. I am unsure if there is support for this beyond experimental evidence.

Mutually Unbiased Bases (MUBs) introduced by Schwinger are used in quantum measurements and also quantum cryptography. MUBs are $d+1$ Orthonormal bases of $\mathbb{C}^d$ where the inner product of any pair of vectors between two distinct bases is $1/\sqrt{d}$ in magnitude.

For example, constructing
 a complete set of mutually unbiased bases in the $\mathbb{C}^d$ with $d$ composite and not a prime power has not been achieved yet, not even for $d=6.$

See the PhD thesis of Joanne Hall here


Can Add and Multiply On Cipher Text achieve all operations?

If addition and multiplication are preserved, then we can evaluate arithmetic circuits over the encrypted data.

It seems that your confusion about the class of problems that we can compute stems from the fact that you are envisioning boolean circuits in which we perform operations on the bitwise representations of the input. This is not an FHE question per se, but rather a question regarding the difference between the computational models of boolean circuits vs. arithmetic circuits. To understand the problems that can be computed with this model of computation, take a look at this paper. A relevant portion:

  The definition above shows an evident difference between arithmetic circuits and Boolean circuits.While Boolean circuits can perform operations on the "bit representation" of the input field elements,that are not necessarily the arithmetic operations, arithmetic circuits cannot. Nevertheless, most algorithms for algebraic problems fit naturally into the framework of arithmetic circuits.

In regards to why they defined FHE this way, it follows the definition of  Ring Homomorphism. By definition, a ring homomorphism is a function between two rings that respects addition and multiplication.

In practice, recent research on FHE studies lattices since ideal lattices yield both additive and multiplicative homomophisms.


What's the difference between rsa_pss_pss_* and rsa_pss_rsae_* schemes?

Summary: they aren't different signature schemes. Both specify the use of RSA-PSS. The difference is in how to parse the certificate to find the public key.

RSA-PSS (also spelled RSASSA-PSS and other variants) is a family of short-message signature schemes defined in PKCS#1 (RFC 8017). A short-message signature scheme can only sign a message with a small length limit; normally the payload is a hash of a message that can be arbitrarily long (in pratical terms). RSA-PSS is a family of schemes because it is parametrized by a mask generation function (and a salt length but I won't discuss that here; you can view it as a parameter of each signature rather than a parameter of the signature scheme). The only mask generation function anyone uses is called MGF1, but it is parametrized in turn by a hash function. Thus RSA-PSS-MGF1-SHA-256 is one example of a short-message signature scheme. RSA-PSS-MGF1-SHA-256-SHA-256 and RSA-PSS-MGF1-SHA-256-SHA-512 are two examples of message signature schemes that use the hash-and-sign construction, with RSA-PSS-MGF1-SHA-256 to sign the hash.

rsa_pss_pss_sha256 and rsa_pss_rsae_sha256 both indicate the RSA-PSS-SHA-256 signature scheme, in the same way that rsa_pkcs1_sha256 indicates the RSA-PKCS#1v1.5-SHA-256 signature scheme which uses the RSA-PKCS#1v1.5 short-message signature scheme. The reason there is a pair of values for each PSS-based scheme is that signature algorithm extension in TLS 1.3 encodes a little bit more than a signature scheme.

That extra bit of information is how to find and validate the public key. For the most part, given a TLS version and a ciphersuite, there is only one way to do this: in a ciphersuite that uses certificates (i.e. the “normal” ciphersuites, as opposed to ciphersuites without authentication or using pre-shared keys or raw public keys), you parse the certificate chain, check that the chain of signatures is valid, and check that the root of the chain is acceptable. There is no other method in use in the TLS protocol.

But wait, how do you parse certificates? The TLS protocol only specifies one certificate format, which is X.509. So there's still no need for any extra information. I won't go into detail about X.509, suffice to say that there is a standard way to find the public key and the signature, and both annotated by some information that says what type of key
or signature it is. The key or signature type is conveyed by an OID.

Obviously, since there are two standard signature schemes that use RSA keys (RSA-PKCS#1v1.5 and RSA-PSS), they each have their own OID. Less obviously, there are also multiple key types for RSA keys. There's an OID called rsaEncryption which allows the key to be used for any of the standard encryption or (despite the name) signature schemes. And there's an OID called id-RSASSA-PSS which indicates that the key may only be used for PSS signatures. This is explained in RFC 4055. In addition to restricting the use of the key to the RSA-PSS signature scheme family, using id-RSASSA-PSS to identify the RSA key rather than rsaEncryption allows the certificate to indicate which scheme parameters to use (MGF1, its hash, and other rarely-used parameters). The reason to have a distinct key OID is that if you use the rsaEncryption then there is no way to specify that the key must be used for PSS only, and if someone finds something signed with PKCS#1v1.5 then it must be a forgery that takes advantage of a weakness in PKCS#1v1.5. (There is no known weakness of PKCS#1v1.5 when correctly implemented, but one may be discovered one day, and PKCS#1v1.5 verification is difficult to implement correctly.)

So what does this have to do with TLS? Some TLS implementations use an X.509 parser that only recognizes rsaEncryption. So they don't include the rsa_pss_pss_sha256 value when they send the signature algorithm extension, they only include rsa_pss_rsae_sha256 (if they support it), where the rsae part stands for “encoded with rsaEncryption in the certificate”. Others may consider rsaEncryption to be legacy, and they don't include rsa_pss_rsae_sha256, only rsa_pss_pss_sha256 (if they support it), where the second pss stands for “encoded with id-RSASSA-PSS in the certificate”.


Diffie-Hellman: Should the subgroup have prime order?

For DH, whether the subgroup is of order $p$ and $2p$ isn't that big of a deal; if it's $2p$, that means that the attacker can deduce one bit of the exponent; that's minimal.  As for computing the discrete log, it's effectively equivalent; given an Oracle that can compute the DLog of an element of one order, you can (with one query) compute the DLog of an element of the other.

On the other hand, you're using SRP, and that changes things.  For SRP, you MUST use a primitive element, that is, one with order $2p$.  If you pick a proper subgroup; that is, a group for which random values in $Z_q$ have a nontrivial probability of not being in the group, the attacker can effectively eliminate many of the possiblities for the secret value from a single exchange; this is a violation of the SRP security policies.

If you want to generate SRP parameters, read the SRP specs; it tells you how to do it - it's important that you follow those (and actually, you're close; it mandates a safe prime;).


As the name suggests, CTR mode works by encrypting a counter (that gets incremented with each 16-byte block) to generate a stream of random bits. That bit stream is then XOR'ed with the plaintext to create the ciphertext. The IV provides the initial value for the counter.

CTR mode is secure as long as the probability of a counter value repeating is negligible. Therefore the scheme you describe is secure under two conditions:

No message is longer $2^{32}$ sixteen-byte blocks long. Since this works out to be 64GB, this assumption is probably safe. (I'm assuming the 32 IV bits that are the same each time are the bits that get incremented with each block.)
The number of messages encrypted under a single key is small.

How small is small? Well, the birthday paradox says that if you encrypt $2^m$ messages, the probability that the random, 64-bit portion of the IV will repeat is at most $2^{2m}/2^{64}$. So if you encrypted $2^{16} = 65536$ messages, the probability of having a repeated counter is less than one in $2^{32}$; i.e., less than one in roughly four billion. In most cases, this is an acceptable risk (although some may consider it high by cryptographic standards).


Zero-knowledge proof for subset sum problem?

I would suggest rewriting your subset-sum problem as a lattice problem, either Approximate Close Vector Problem (Approx-CVP) either a Bounded Distance Decoding Problem (BDD), depending whether your subset-sum has low density or high density. Then, there should be plenty of litterature for efficient zero-knowledge proofs for lattice problem (like this one, but I'd guess there are more recent work with better efficiency).

To translate the subset-sum instance $t = \sum^n_{i=1} x_i b_i \bmod M$ into a lattice problem, consider the $n$-dimensional lattice $L = \{ \vec v \in \mathbb Z^n | \sum v_i b_i = 0 \bmod M\}$. Choose any $\vec y \in \mathbb Z^n$ (not small) such that $t = \sum^n_{i=1} y_i b_i \bmod M$. Then, solving your subset-sum is equivalent to to writing $\vec y = \vec v + \vec x$ where $\vec v \in L$ and $\vec x$ is small. Depending on how short of an $\vec x$ you expect, this is either an Approx-CVP problem or a BDD problem.


Deterministic Rand function for Winternitz One Time Signatures

Why not use a stream cipher? The requirement for the generating function is not that it is a PRF but a PRG (which in many constructions is build out of a PRF). If you use the key stream of a stream cipher as output then this is a PRG.


The GQ identification scheme is essentially a zero-knowledge proof of a value $x$ such that $x^\mu \equiv J \pmod N$ where $N$ is an RSA modulus and $(\mu,N)$ are system parameters and $J$ is known to the verifier and $x$ only known to the prover.

Now your question is not directly concerned with the aforementioned proof where a user shows the possession of a credential, but with how credentials are issued to users by the authority.

Before going into the questions regarding the GQ identification scheme, I briefly recall existential forgeability of textbook RSA signatures.

Recall the RSA setting where we have an RSA modulus $N=pq$ being the product of two primes $p$ and $q$ and the public exponent
 $e$ being an invertible element of the multiplicative group $\mathbb{Z}_N^*$ (with order $\phi(N)$) and the private key $d$ it's multiplicative inverse,
 i.e., $d \equiv e^{-1} \pmod{\phi(N)}$. Now we may abuse the notation and write $d:=1/e$ (what is done in the GQ paper).

So, in texbook RSA signatures the computation of a signature for a message $m\in \mathbb{Z}_N$ amounts to computing
 $\sigma \equiv m^d \pmod{N}$ and verification amounts to checking $m\equiv \sigma^e \pmod{ N}$.

Observe, that by simply choosing $\sigma$ and computing the message $m$ as $m:= \sigma^e {\mod N}$ gives an existentially
 forged message signature pair $(m,\sigma)$ for the textbook RSA signature.

Observe, however, that the adversary cannot
 control the message $m$, since the adversary cannot predict what $\sigma^e$ will yield (consequently, it is a good idea to apply a cryptographic hash function $H$ to messages before signing, since then such an existential forgery would yield $H(m)$ and one would need to find $m$ which is firstly hard given a secure hash function and moreover will very likely not yield a meaningful message $m$ anyways. This is called the hash then sign paradigm).

Shadowed Identity

Now, exactly this is the purpose of a shadowed identity in GQ, i.e., we require the credential including identity $I$ to have some structure and thus the identity is shadowed to $J$.
 Consequently, it is not efficiently possible to choose a random element $A$, compute it's $\mu$'th power ($\mu$ is the public key $e$ from above) and obtain a valid shadowed identity $J$.
 Note, that one could choose $A$ randomly and compute $J\equiv A^\mu \pmod N$, but requiring $J$ to have
 some defined redundancy (being an shadowed identity),
 such a forgery will not lead to a valid identity $J$ under the redundancy scheme with very high probability.

Note that this prevents an adversary from computing a credential on its own without interacting with the authority (knowing the value $1/\mu$). The authority, however, can form the shadowed identity $J$ and then compute $A\equiv J^{1/\mu} \pmod N$. Observe that this is essentially a textbook RSA signature of the authority for message $J$.

Nevertheless, it is not exactly stated in the paper how this shadow should be chosen.

Extracting $\mu$'th roots

Note that $\mu$ plays to role of $e$ (the public exponent) in the RSA setting and note that computing the inverse $1/\mu$ from $(\mu,N)$
 (which is equivalent to the private exponent $d$ in the RSA setting) requires to know the factorization of $N$. Observe that
 $1/\mu$ is computed as the multiplicative inverse of $\mu$ modulo $\phi(N)$ using the extended euclidian algorithm.

In the GQ identification scheme as described in their paper, the factorization of $N$ is only known to some authority and thus the identification tokens $A$ can only be computed by this party. Consequently, having this redundancy scheme (shadowed identities) and limiting the knowledge of the private key $1/\mu$ and the factorization of $N$ to some authority, $\mu$ and $N$ can be system parameters for many users.

The value $\mu$ can be chosen to be any value that is co-prime to $\phi(N)$ and for instance fixed to the prime $2^{16}+1$ as it is common in the RSA setting.

Last part of the question

You write

  Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$
  or $r.(B^d\ mod\ n)$?

It means $(r\cdot B^d)\ mod\ n$ and this is equivalent to $(r\cdot (B^d mod\ n))\ mod\ n$.

Final remark

Finally, I would like to suggest to read about the GQ identification scheme in another source such as chapter 10 of the freely available Handbook of Applied Cryptography, since the description is much easier accessible than in the original paper.


Is Pohlig-Hellman Cipher the only option?

If you define $E_a(M) = M \oplus  a$ then the key $ab$ can also be defined as $a \oplus b$ as follows:

$E_b(E_a(M)) = (M \oplus a) \oplus b$

$E_{ab}(M) = M \oplus (a \oplus b)$

However using the same key and/or message more than once in XOR will leak the other one. So I think it's potentially not what you're looking for.

As far as I know, SRA is also a variant, where you get regular RSA where both parties use the same modulus (and prime numbers) and create their own encryption, decryption exponents; and keep it secret. This way you achieve the same commutativity as in PH.


What is the best and fastest algorithm to generate a hash collision?

The currently best algorithm to finding collisions of generic hash functions is the parallel pollard-rho algorithm due to van Oorschot and Wiener (1994, PDF). A nice summary with an updated communications cost model can be found in Bernstein's "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?" (2009, PDF). For an in-depth discussion, please refer to these two papers.

I shall now sketch the parallel pollard-rho algorithm. Let $b$ be the the length of the hash function $H$'s output in bits, let $c$ be a positive constant and let $\pi:\{0,1\}^b\to\{0,1\}^{b+c}$ be an injective padding function (in practice appending $c$ zero bits works). Furthermore let $M$ be the number of parallel processing units you have. Define the sequence $x_{n+1}:=\pi(H(x_n))$ with $x_0$ being arbitrary (but different for each processor).

Compute $x_i$ until the first $b/2-\lceil\lg M\rceil$ bits of $x_i$ are $0$ and call this a "distinguished point". We expect to have found a distinguished point after $2^{b/2}/M$ after time $2^{b/2}/M$ on all $M$ processors. Note that we have considered $2^{b/2}$ inputs for $H$ at this point across all processors.

Now we only need to look through our list of $M$ distinguished points and find two which are equal, this can be done using e.g. distributed sorting algorithms in time aboutt $O(\sqrt M)$. As the starting values for the sequences were different, but the end values are the same, there must must be a collision in them.

Let's call the matching distinguished points $y_j$ and $z_k$, now compute $|j-k|$, i.e. the difference in the sequence lengths. Go back to their respective starting values and apply the iteration $|j-k|$ times on the starting value which had the larger index for the distinguished point. Now iterate the sequences in parallel until you find the collision.

All in all this algorithm will take about $O(2^{b/2}/M)$ time and a negligible amount of memory per processor.

  Should I constantly produce two random strings and compare them until
  I find a collision?

No, this will likely take time $2^b$, because you only consider two strings at a time and not all strings you have evaluated so far.


Decrypting a substitution cipher, but with symbols instead of letters

Frequency analysis is the way to go. If your plaintext is in English then the letter "e" would (probably) be the most common letter in the text. A good technique would also be to look for repeated symbols. In the English language (and probably all other languages as well) there are many words with double letters (i.e. "kill", "hello", "symmetry"), so you can narrow it down what the word with the repeated symbol would be.


Measuring entropy for a ciphertext only attack

Well, from your previous questions, I'm assuming that your writing a utility to brute-force decrypt a password protected file (encrypted with a certain encryption utility), and you're looking for a way to determine whether your trial decryption is plausible.

Normally, when an attacker attempts to decrypt something, he has some idea about what it is (why else is he investing the effort), and even if that guess doesn't give him an entire plaintext block, he partial information about what it is (be it an IP packet or a Word document) will help him recognize it.

Thomas states that the usual assumption is that you do have a full plaintext block; that may be the assumption you make when you're designing a cipher (actually, you assume the attacker has a lot more than that), but that's not always true for all attackers (for example, yourself).

Your suggestion (run a Chi-Squared test on the byte frequencies to see if it is consistent with the bytes being generated randomly (with the idea that decrypting the data with the wrong key will end up with random looking plaintext) isn't a bad idea; whether it is the right idea depends a great deal on whether it will actually pick up the plaintext (without the sensitivity needing to be so high that you are deluged with false hits).  This is a real concern; I suspect that (say) ZIP files have fairly even byte distributions; the Chi-Squared test would be hard pressed to identify those).

Hence, my suggestion would be to rely on a series of tests, each designed to pick up a particular file format (as well as a general purpose test that has a shot at recognizing file formats you didn't anticipate).

Some ideas for these tests might be:

Checking if the MSbits of the bytes are mostly the same.  This will catch anything in a text format (and yes, a Chi-Squared test would also catch it, but you'd need to decrypt a lot more data to run that test)
Check to see if the start of the is consistent with a specific file format (for example, check the magic number that appears in a ZIP file header or a JPEG file header).

Your Chi-Squared based test is a decent general purpose test, which has a good shot at picking up most file formats that aren't heavily compresssed.  If I were doing this, I'd pick a simpler but related characteristic (such as "is there a byte value that occurs more than N times"); I have no good feel as to which would work better in practice.


Terminology for parties in authentication protocols

Yes, it seems so: User and Principal/Party

In Protocols For Authentication And Key Establishment, published this year and written by
Colin Boyd, Anish Mathuria, and Douglas Stebila, it says this in Section 1.2.2:

  In the following,
  we use the term user to mean an entity who will use the session key for subsequent
  communication. We also use the term principal or party to mean an entity who will
  engage in the protocol. For example, in a protocol which uses a key server (often
  called an authentication server) there are users who will obtain the session key while
  the server is a principal but not a user.

These terms occur throughout the the international standard ISO/IEC documentation. Just one example is ISO/IEC 11770-2 Server-Based Protocols, in the section about key establishment mechanisms.


so long as the adversary does not obtain any plaintext/ciphertext pairs, Alice and Bob can share multiple messages with the same key

Even if Alice and Bob do not explicitly disclose plaintext/ciphertext pairs, if they care for confidentiality, they must not use this cipher, except maybe for essentially random plaintext and when leaking the Hamming weight of plaintext is no issue (e.g in re-encryption).

Problem is, the more ciphertext, the easier it is to reconstruct all or part of the permutation given some model of plaintext redundancy. For example, if the plaintext is known to be ASCII restricted to uppercase and space, then groups of 7 bits where one is rarely 1 and the others 6 are always 0 when that occurs must belong to the same character, and the rare 1 is the bit set in a space, coded 00100000 in binary (while letters are 010xxxxx). The bit among the remaining 6 that is 1 in all letters is identified by this characteristic. Then frequency analysis reveals the mapping of the remaining 5 bits, and the corresponding letters. Then all that remains from the cipher is a fixed substitution of symbols.

Even with a single block of $n$ bits, if we know that the plaintext is restricted to a small set (e.g. names as written on the class roll), the Hamming weight might allow decryption, and will likely narrow the possible names.


For such small numbers, brute force search will do: by definition $a^{-1}\bmod p$ is the integer $x$ in $[0,p)$ with $a\,x\bmod p=1$. The desired $x$ can be found by trial and error. This requires less than $p$ additions, tests, and subtractions, noting we can move from one candidate $x$ to the next using that $((a\,(x+1))\bmod p)\,=\,((((a\,x)\bmod p)+x)\bmod p)$.

One of the most recommendable and fastest classical algorithms is the (half) extended Euclidean algorithm. In crypto, we sometime prefer that variant avoiding negatives. There also are binary variants. Essentially, these find unknown $x$ solving the Bézout identity $a\,x+p\,y=1$ for given $a$ and $p$, and some immaterial unknown $y$.

Yet another method uses $x\gets a^{p-2}\bmod p$. It's applicable when $p$ is prime and integer $a$ is not a multiple of $p$. It follows from Fermat's little theorem. This uses less than $2\log_2(p)$ modular multiplications, using binary modular expoentiation. The method is extensible to any group of known order.


I think that you may be referring to hash functions with (not secret) keys as presented in any theoretically rigorous text on cryptography. In practice, hash functions do NOT have keys. However, if you try to define collision resistance without keyed hash functions, then it is impossible to achieve. This is because there always exists an adversary who finds a collision (this is an adversary who has a collision hardwired in its code). You may not be able to FIND such an adversary, but they certainly exist. We therefore define hash functions to have keys which are chosen after the adversary is fixed. (See textbooks for more discussion; it's an annoying technicality, but very not trivial.)

There a few ways to bridge this theory and practice. One is to say that the IV in practical hash functions is the key. I like this one, but most people don't (so I'm in the minority). Another is this paper by Rogaway http://web.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf. Anyway, the introduction to that paper will also help explain the problem.


I think Caesar cipher meets your requiremnts, check it out here Caesar Cipher


The following two assumptions are mutually incompatible:

  you're trying to do SHA3-224

and

  with a 32-bit machine you'd presumably be using KECCAK-f[800]

because chapter 6.1 of the SHA-3 Standard FIPS PUB 202 (the link can be found here) defines

  $\text{SHA3-224}(M) = \text{Keccak}[448](M \mathbin\Vert 01, 224)$,

but chapter 2.4 of this Standard defines that

  $\text{Keccak}[c]$ is the Keccak instance with $\text{Keccak-}f[1600]$ as the underlying permutation and capacity $c$.

Regarding the question about the rotation offsets for $\text{Keccak-}f[800]$ — see chapter 3.2.2 of the SHA-3 Standard FIPS PUB 202 and note that $w=32$. For example, I have seen both the algorithm and the precomputed offsets here:

github.com/XKCP/XKCP/.../KeccakP-800-reference.c.


The ECDSA algorithm can't be used for encryption. It's not that there's no accepted way to do it, it's that it's simply not possible to do so. Likewise, RSA signing can't be used to encrypt (there's a mandatory hash in signing that you don't want in encryption). However, RSA signatures work similarly to RSA encryption; they aren't interchangeable, but fundamentally RSA signing, verification, encryption, and decryption all revolve around running the RSA operation on some data $m$ with one of the exponents $e$ (i.e. computing $m^e\pmod{n}$). You could, by making some not-huge changes to RSA signing, get an encryption scheme.

In contrast, ECDSA looks fairly different from any encryption algorithm. Verification looks nothing like signing, and the private key and public key are different things (one's a point, one's a number), so with the public key you can't do anything that looks like signing. A change to let you encrypt wouldn't be called ECDSA, as it wouldn't particularly resemble it.

(There are ECC signing and encryption schemes both called ElGamal; ECDSA is based on ElGamal signing. However, they just share a name because that's the guy who invented both of them; they don't look particularly similar, aside from both relying on discrete logarithm. RSA encryption and signing might also have had different names if they weren't invented by the same people.)

So ECDSA simply can't be used for encryption -- it looks fundamentally different from encryption schemes. What the person on that site did was create an encryption scheme unrelated to ECDSA (but rather similar to ElGamal encryption) that happens to use the same key format. ECDSA keys, ECDH keys, ECIES keys without shared secrets, ElGamal encryption keys, ElGamal signing keys, and the keys of most other ECC systems I'm aware of look rather similar: there's a set of curve parameters (which are generally the same for everyone), and then the private key is an integer $k$ and the public key is $k$ times the generator point found in the curve parameters. This is the standard keypair for something relying on discrete logarithms; with DH and DSA, the keypair is also basically that (just replace $k\times G$ with $g^k$). In that sense, there are all sorts of ways to use ECDSA-style keys for encryption; ECIES is probably your best bet.

That said, ECDSA keys should not be directly reused as encryption keys. Using the same key for two schemes generally a bad idea (they aren't designed for that, and may interact insecurely), and there are often differences in key management between encryption and signing. However, the general structure is already used in plenty of encryption systems.


What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

2) Has anyone claimed to make any progress with this challenge?

Ah that question I can answer now...

I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA).

I noticed around the end of 2015 that if I used GMP I could find the answer on my Core i7-6700 CPU in about three years and a half. So I basically let my computer open 24/7 so that it'd solve the "puzzle".

The secret message and the two primes shall be announced on the 15th of May during a ceremony where the "time capsule" shall be opened.

Link to the CSAIL's article about it:

Programmers solve MIT’s 20-year-old cryptographic puzzle


In your formula, $n$ appears to relate to the key space, not the message space.

The message space does not intervene in the definition of IND-CPA, and that's a good thing because practical message spaces consist in messages which "make sense" in a given context. There are situations where the attacker already guesses quite a lot of the attacked message, and the message space size (as in "number of distinct values that the message may meaningfully assume") can shrink down to 2 (e.g. if the attacker tries to guess a yes/no answer). So whatever security definition you use must be able to cope with very small message spaces.

The formula you quote is the translation of the following thought experiment:

A key pair is generated, with a given "size parameter" $n$ (e.g. we do RSA, with a 1024-bit key). The public key is made public, i.e. the adversary can see it.
The adversary produces two messages $m_0$ and $m_1$ of his choosing, from the set of message values that the encryption scheme can process (e.g. with RSA, a 1024-bit key, and PKCS#1 v1.5 padding, $m_0$ and $m_1$ must be sequences of bytes no longer than 117 bytes).
We choose at random one of the two messages, encrypt it, and give it back to the adversary.
The adversary must now guess which of the two messages we encrypted.

If we do this many times, we can compute the average success of the attacker. If the encryption system is "perfect", the adversary can do no better than a random binary choice. But we give him some CPU power (the $t$ parameter) and he can use that to try to guess the private key, so the attacker can always guess correctly a bit more often than incorrectly. The   $ε$ value is a measure of that "bit more".

Specifically, in the formula, the first probability says how often the adversary gets it wrong when he answers "1", and the second how often he gets it right. The difference between the two probabilities should be no more than $ε$. Note that if the adversary cannot guess right substantially more often than half the time, he cannot guess right substantially less often than half the time either (otherwise, he could just systematically reverse his answer; a compass which always points South is quite useful once you know it).

"CPA" means "Chosen-Plaintext Attack": in the thought experiment, the adversary can choose $m_0$ and $m_1$ as he wishes to, and can do it again for each attack instance.


Easily reversible hash functions as a method of data transmission

The hashing function you describe would be a magical compression method. Well, I'm sorry to burst this on you, but magic isn't real. Magical compression that can take arbitrary data and condense it to a very small size does not exist. In fact, it's easy to prove mathematically that there is no compression method that reduces the size of all data, by the cardinality argument you give.

Compression that reduces the size of common data certainly does exist. But it works by recognizing certain kinds of patterns. Cryptography doesn't help with recognizing patterns — if anything, cryptography is all about hiding patterns.

Compression that can take data among a finite set and condense it to a fixed size is called naming or indexing. Cryptography doesn't help with that either.


Using hashed password as shared secrets. Good or bad idea?

I'm not sure about your specific system; this only addresses "can a key derived from the password make a good shared secret?"

The most common password hashing functions are actually designed for exactly this purpose -- deriving a cryptographic key from a (weak) password. That's actually what PBKDF2 stands for: "password-based key derivation function #2" (scrypt and bcrypt don't have it in their name, but are also key derivation functions). It's also used in GPG, and for file and disk encryption, etc. Kerberos does so as a login mechanism - when you send the KDC your username, you get information that lets you authenticate as that user, encrypted with a key derived from the user's password.

Passwords tend to be low-entropy, far below that required of a cryptographic key. PBKDFs mitigate that by having a salt (to prevent dictionary attacks, for instance by having a list of the keys derived from the 10000 most common passwords) and by being as time-consuming as you please, which means that while an attacker doesn't have to try as many possibilities as with a random key, it takes them a long time to try each possible password.

So in general, password-derived keys make fine shared secrets. There are some catches (notably: if an attacker compromises them, they've compromised the shared secret; this is why Kerberos KDCs have to be so secure). But there's nothing generally wrong with the concept.


multiplicative inverse in galois field $2^8$

Set $g(x)=x^8+x^4+x^3+x+1$ , $p(x)= x^5+x^4+x^3$.

Applying Euclidean algorithm,

$g(x)=p(x)(x^3+x^2+1) + (x+1)$,

$p(x)=(x^4+x^2+x+1)(x+1)+1$.

Therefore, $1=p(x) + (x^4+x^2+x+1)(x+1)
            = p(x) + (x^4+x^2+x+1)[g(x) + p(x)(x^3+x^2+1)]
            = [(x^4+x^2+x+1)(x^3+x^2+1)+1]p(x) + (x^4+x^2+x+1)g(x)$

Setting $q(x) = (x^4+x^2+x+1)(x^3+x^2+1)+1$ (please expand yourself),
$p(x)q(x) = 1  \text{mod}  g(x)$.
So $q(x)$ is the inverse of $p(x)$.

Maybe there are some errors in my calculations because I didn't do double-check, but I'm sure of the process.

Sorry for bad editing. I'm a newbie to this site.

To check the answer, multiply the result polynomial to p(x) and divide by g(x).
The answer must be 1.


Does public-key + hashing create a security vulnerability?

The hashing does not compromise security in any way. Assuming you're calculating hash(ciphertext+salt), the hash provides no new information that an attacker with access to your ciphertexts doesn't already have.

A secure hash like SHA-3 is a one-way function, safe even on a salted plaintext, and the outputs of such are stored in authenticated encryption. You can actually strengthen your system by using a HMAC rather than just a hash and incorporating an authentication mechanism.

As for whether the whole system is secure, it depends on what you're storing.

Checking if the packet has been stored is likely to create an oracle for a side channel attack. If the attacker can send packets to encrypt and your response or its timing is in any way different for duplicates, they can verify if a certain file of interest or a certain password is being stored in your system.

Whether it's effective depends on the search space for the plaintext. If it's small, e.g. passwords, or files people don't want to be known to possess, that's a vulnerability. Deduplication is generally at odds with security, and creating secure deduplication is a current challenge.

N.B. I've addressed only security, not utility above. Keep in mind that you can only compare hashes with the same salt, so this scheme may have limited effectiveness for deduplication.


Zero knowledge proof for sign of message value

What you are looking for is called a range proof. There has been a vast body of research on the topic recently - so vast, in fact, that it can be quite hard to know what is the state of the art, and what solution is the most appropriate in a given situation. Therefore, to let you evaluate by yourself what might best suit your exact situation, I'll attempt at providing a quick survey of the existing methods and their constraints.

The most natural method is the naive method that you mentioned: commit to the bits $(m_i)_{i\leq \log q/2}$ of the plaintext $m$, prove that $\sum m_i 2^i = m$ and that $m_i(1-m_i)=0$ for every $i$ (id est, each $m_i$ is a bit). Unfortunately, this takes $O(\log q)$ group elements, hence it is very costly. An improvement to this naive method has been suggested in this article. The idea is the following: rather than decomposing $m$ in base 2, decompose it in base $B$. You now simply need to commit to the $\log_B(q/2)$ elements $m_i$ of the decomposition in base $B$. To prove efficiently (in constant time) that $m_i \in \{0, \cdots, B-1\}$, the idea is to let the verifier add signatures of the integers $0, \cdots, B-1$ to the public key, and to use known methods to let the prover show that he can produce a signature for the committed value. As he cannot forge a signature for any value outside $\{0, \cdots, B-1\}$, it is sufficient to complete the proof. This gives you a proof which communicates $O(\log q / \log \log q)$ group elements, but it has a downside: it requires to use an elliptic curve with an appropriate pairing operation, as such a pairing is required for the signature part. The constant in this $O()$ has been improved in this article.

Now, you might also be fine with a proof that does not hold for arbitrary provers, but only for computationally bounded provers - it won't make much difference in practice. This is called a zero-knowledge argument, and there are more efficient methods in this case. The one I will describe is not explicitely mentioned in an article, but is a natural consequence of a serie of works by Groth and Bayer (and can therefore be seen as folklore). The core idea is that one can commit to many numbers at once using a scheme called "generalized Pedersen commitment scheme": the public key contains $n+1$ random group elements, and to commit to $n$ values $(a_1, \cdots, a_n)$ with random coin $r$, compute $c = h^r\cdot \prod_i g_i^{a_i}$. This is perfectly hiding, and computationally binding under the discrete logarithm assumption.

To prove that $m$ is in $[0,q/2]$, decompose $m$ in base 2: $m = \sum_i m_i2^i$. Group these bits by packs of $\sqrt{\log q}$ consecutive bits (you'll have $O(\sqrt{\log q})$ such packs). Commit to each pack, with a single group element per pack, using the generalized Pedersen scheme. Now, perform a batch product proof to show that all the committed values are bits (ie, they satisfy $m_i^2-m_i = 0$). This kind of batch proofs are non-trivial, but have been studied in detail in e.g. this article. Essentially, they are all constructed by carefully and repeatedly applying the Schwartz-Zippel Lemma, which is used to say (informally) that if someone knowns a random linear combination of some values, he must know all the values. Applying this lemma allows to shrink the dimensions of the problem.

The prover must also prove that $m = \sum_i m_i 2^i$; the previously mentioned article also shows how such proofs can be constructed. The techniques developed essentially allow to perform an efficient (batched) proof for any statement over committed values that can be expressed with linear algebra, see this article. Overall, this gives you a range proofs with a communication of $O(\sqrt{\log q})$ group elements. It involves many rounds (I'd say 7 to 9), but can be made non-interactive if you are fine with using the Fiat-Shamir transform, which is secure in the random oracle model (hence only "heuristically secure").

If you want an even shorter proof, then you can consider again using an elliptic curve with a pairing, to use the improved version of the above method: this article does essentially what I described above, but gains additional efficiency by using a pairing, which allows (informally) to commit to commitments, hence to get one more level of "packing". It gives a protocol which communicates $O(\log^{1/3}q)$ group elements.

And finally... You can have a proof of constant size. But then, you must rely on a completely different method: first, commit to $m$ in a group of unknown order, and prove that you've committed the same value in two different groups, using for example this article. To have such a group, the usual method is to have an RSA modulus $N = pq$, product of two safe primes, and to take a generator of the group of squares, whose order $\phi(N)/2$ is unknown unless one can factor $N$. Note that this means that the constant will be large: factorization-based methods need very large groups (say, $|N| = 2048$). This is therefore suitable for range proofs on large intervals. The trick is the following: by a theorem from Lagrange, an integer is positive if and only if it can be decomposed as a sum of four squares. Therefore, one simply commits to the elements of this decomposition (which can be efficiently computed) and prove that the sum of their squares is $m$. The group of unknown order is required to ensure that we indeed work over the integers: the prover cannot perform modulo reductions if he does not know the modulus. This method was described in this article, and improved several time. To my knowledge, the most efficient constructions of constant size range proofs are given in this article, which is one of my recent works. In particular, we review the existing optimized range proofs and give new constructions, while weakening the necessary security assumptions.

To choose an appropriate scheme is now up to you, depending on the following:

Are you willing to use an elliptic curve with pairings?
Are you Ok with using the random oracle model to get less interactive arguments?
Would you be fine with using additional assumptions, and a group of unknown order, which might require an additional setup phase?
How many range proofs will you have to perform? Range proofs can be batched: using a combination of this article and my article allows to perform $M$ range proofs simultaneously, incurring only a $\sqrt{M}$ overhead. As you seem to have many such range proof to perform, it would probably be better to perform a global batched range proofs.
What is the exact size of the intervals you will have? (having $q$ of size 256 bit, if using elliptic curves, or, say, 1024 bits if using subgroups of prime order fields, can change the appropriate method)

I do not provide detailed explanations of the methods in my answer, it would be too long; you can either refer to the articles I've included, or ask for precisions on a particular method if one of them seems to suit your requirements.


RSA-blind signatures vs. DSA-blind signatures

Well, I think it is quite hard to give a really objective and complete answer to this question.

Personally, I think that why you may encounter RSA blind signatures quite often is due to it's simplicity. I am not quite sure
if you will see it often in practical implementation though, because there has been a patent (which as far as I remember expired quite recently). RSA blind signatures can be proven secure in the random oracle model under an interactive assumption (the one-more
RSA inversion assumption), see here. Some people may say that proving security under some interactive
 assumption is not really nice, but we do not have any better arguments for this scheme. A nice thing from a theoretical point of view, however,
 is that RSA blind signatures are round optimal, i.e., two move (one message to the signer and one back), and thus automatically concurrently secure, i.e., one
 does not need to care about attacks due to interleaving different signing sessions.

Schnorr type blind signatures (such as blind DSA signatures) are conceptually not that simple (although also not really complicated) and
always at least three move (and thus not round optimal). From a provable security point of view they can be proven secure in the random oracle model,
but as far as I know all reductions require the forking lemma and are thus not really tight. You have to decide on your own if you would rather live with interactive assumptions or loose reductions to the discrete log assumption.

If you are looking for practical blind signatures
in the discrete log setting, you may also look at BLS blind signatures, which are round optimal and
can be proven secure in the random oracle model under an interactive assumption (quite similar to that of the RSA blind signature scheme). However, they require gap Diffie Hellman groups, i.e., groups where the DDH is easy, and thus requires pairings.

From an implementation point of view I think it is hard to give a general answer as it really depends over which types of groups you
are going to instantiate blind signatures in the discrete log based setting.


How can I factorize a 350 bit (106 decimal digits) number in two prime factors?


Performing HMAC with random key before MAC comparison

The commit that added this double HMAC only says it improves "valid MAC detection", but it simultaneously adds the constant-time comparison, so likely the reason is indeed defense against timing attacks:

Improve valid MAC detection
Implement constant time string comparison as well as double HMAC
verification for encryption MACs.

Double HMAC is a known technique to avoid the side channel attack, and has been recommended as a more reliable (and "simpler") alternative to constant time comparisons. I am not aware of anyone recommending both, which is pointless (they prevent the same attack) and costs even more than double HMAC - its main downside compared to constant time comparisons. On the other hand, it should not hurt, so perhaps it is done out of an abundance of caution.