I'll assume the question asks: in the Diffie-Hellman key exchange protocol, how large does the secret random natural number that Alice and Bob each select needs to be.

It can be used a newly generated cryptographically secure random integer $x$ of 256 bits. This is conjectured safe for sound parameters (detailed below) and protocols used in practice. That's possibly good for a few decades, not accounting for mathematical breakthrough, nor hypothetical quantum computers usable for cryptanalysis.

PKCS#3 v1.4:1993 (official home) allows this, with an optional parameter $l$ length of private value in bits. When this option is used, $2^{l-1}\le x<2^l\;$ (with this option, PKCS#3 uses $x$ of fixed bit length, perhaps to reduce leakage by timing analysis). The modern Java CryptoAPI also has an $l$ parameter.

This practice is used in the Internet Key Exchange protocol of RFC 2409 with parameters of RFC 3526. It limits the cryptographic resistance to at most $O(2^{l/2})$, but, conjecturally, not significantly further down if the order of the generator used is a prime $q$ of at least about $l$ bits (or twice such a prime), which to my knowledge is met by all recommended DH parameters. See Paul C. van Oorschot and Michael J. Wiener, On Diffie-Hellman Key Agreement with Short Exponents, in proceedings of Eurocrypt 1996, which gives justification and a narrower criteria.

Choosing a larger bound for $x$ does not harm (demonstrably: by more than one bit of security), except for speed (execution time is roughly proportional to the bit length of $x$, all other things being equal). The absolute maximal security is obtained when $x$ is uniform on an interval of width equal to the order of the generator, but for some recommended DH parameters this comes at significant performance cost.

Note: This answer has been considerably expanded, following constructive criticism of an earlier version. I now stress that the above statement is relying on a stronger (thus mathematically less certain) assumption than a pure Diffie-Hellman assumption, and detail the conditions conjectured sufficient to ensure that a short exponent is secure.

The simplest form of Diffie-Hellman key exchange protocol works in the multiplicative group modulo some suitable public prime $p\;$ (the group $\mathbb Z_p^*\;$), using some suitable public member $g$ of that group. Alice (resp. Bob):

selects a random integer $x_a\;$ (resp. $x_b\;$) less than the bound $m$ discussed; the lower bound for $x$ can be $0\;$, $1\;$ (Handbook of Applied Cryptography Protocol 12.47), or $m/2\;$ (PKCS#3 with optional parameters $l$ and $m=2^l\;$);
computes and sends $y_a\;=\;g^{x_a}\bmod p\;$ (resp. $y_b\;=\;g^{x_b}\bmod p\;$);
receives $y_b\;$ (resp. $y_a\;$);
computes $z_a\;=\;{y_b}^{x_a}\bmod p\;$ (resp. $z_b\;=\;{y_a}^{x_b}\bmod p\;$).

Assuming that the messages have not been altered during the exchange, $z_a=z_b\;$. Both are $z\;=\;g^{x_a\cdot x_b}\bmod p\;$. For proper choice of $p$, $g$ and $m$ it is believed computationally infeasible to determine that common $z\;$ from knowledge of $y_a$, $y_b$, $p$ and $g\;$. That $z$ can then be used to establish a common symmetric secret key using a Key Derivation Function (beware that this protocol is vulnerable to a Man-in-the-Middle).

An $l/2$-bit security level requires choosing an upper bound $m$ at least $O(2^l)\;$. That's because regardless of parameters $p$ and $g$, there are generic attacks recovering $z$ in full with cost $O(2^{l/2})$ modular multiplications. One such attack finds $x_b$ from $y_b$, by precomputing $y_b\cdot g^u\bmod p$ for $u<2^{l/2}$, then searching $(g^{2^{l/2}})^v\bmod p$ for $v\le2^{l/2}$ among that; once a match is found, it comes $x_b\;=\;v\cdot2^{l/2}-u\;$; and $z$ is then computed as ${y_a}^{x_b}\bmod p\;$. There are better methods requiring much less memory, but we know no method requiring much less time and still generic (that is working for any $p$ and $g$, and more generally any group used for a generalized Diffie-Hellman key exchange protocol).

Common wisdom is that baring mathematical breakthrough or quantum computers usable for cryptanalysis, and with otherwise sound parameters, random-enough primes $p$ of 3072 bits can give about 128 bits of security. Beyond that, various practices exist for the choice of $p$, $g$, and $m\;$.

It can be used a safe prime $p\;$ (that is, such that $p=2q+1$ with $q$ a prime), and $g$ a generator of $\mathbb Z_p^*\;$ (a positive integer such that $g^q\bmod p\ne1\;$); and bound $m=p-1\;$. This works in the group $\mathbb Z_p^*\;$, which has even order $p-1\;$. Noticeably, a passive adversary can find whether the common $z$ is a quadratic residue modulo $p$ or not, which leaks ≈0.81 bit of entropy. This is a non-issue when $z$ is post-processed by a proper KDF.
As a variant it can be used $g$ of order $q\;$ (that is with $g^x\bmod p$ taking $q$ distinct values for unbounded $x\;$, which can is insured if $g^q\bmod p=1\;$ and $g\bmod p\ne1\;$), and bound $m=q\;$; or equivalently it can be used $g$ and $m$ as in [1.] above, but with restriction to even $x\;$. This is relying on a pure Diffie-Hellman assumption in the group of quadratic residues modulo $p\;$, which has prime order $q=(p-1)/2\;$. It is demonstrably as secure as [1.] is.
It can be used a prime $p$ such that $p=q\cdot r+1$ where $q$ is a prime of about $l$ bits; and $g$ of order $q\;$, which is equivalent to $g^r\bmod p\ne1\;$; and $m=q\;$. This is relying on a pure Diffie-Hellman assumption in a Schnorr Group of prime order $q$ of about $l$ bits. Common wisdom is that it offers about $l/2$ bits of security for small $l$; thus with a $p$ of 3072 bits, using $q$ of about 256 bits is believed not to harm security compared to $q$ of 3071 bits in [1.] or [2.] above. There's a speedup by a factor of nearly 12, which the applied cryptographer loves (even though Schnorr groups create complications for authenticated variants of the Diffie-Hellman key exchange protocol, where an active adversary could try to sneak in $y$ not member of the Schnorr group).
As a variant of any of the above three practices, and as suggested in the first part of the present answer, it can be chosen $m=2^l$ (and $m/2\le x<m$ in a PKCS#3 context).

When [4.] is combined with [1.] or [2.], we have the speedup of [3.] with $p$ still a safe prime. With $l$ large enough, there is no known reduction in security compared to [1.] or [2.]; but we do not know for sure how large $l$ should be. I see no argument to assert if at equivalent $l$, the security is more or less than the security of [3.] alone, which is commonly used.

When [4.] is combined with [3.], there demonstrably can't be a significant reduction in security compared to [3.] alone: no more than $\max(\log_2(q)-l,0)+1$ bits worth could be lost.

When using one or both of [3.] or [4.], the upper bound $m$ for $x$ is typically 160 to 512 bits, further with $m=q$ when not using [4.]. Otherwise (when using [1.] or [2.] without [4.]) the bound is typically per $p-1$ or $q$, thus 1023 to 4096 bits (though $p$ of 512 bits has been used, including as intentionally weakened cryptography).


Abstracting primitives and modes of operation

It is not a good idea to try and find abstractions at places where there is no fundamental reason for them to exist. That there is some "accidental" structure in the way encryption or hash methods are build up does not say anything about future encryption or hash functions.

Besides, you may need to apply specific protections against e.g. side channel attacks. It would be a shame if your carefully build software design would be in the way of creating a more secure library.

Note that if there is no fundamental reason for specific abstractions, there may not be any advantage in creating them. E.g. you would not see too many advantages regarding code duplication.

Many algorithms have specific naming conventions and reference implementations. You should not want to shoehorn those into your design.


I'm not sure if you want to model existing hash functions with a general model, or invent a new one.
The usual general definition of hash function is a function which takes a variable length input bit string and produces a fixed length output bit string: $h : \mathbb{Z}_2^* → \mathbb{Z}_2^n$ ($n$ being the output length).
All real-live hash functions I know have some input block size (often larger than the output size), and process the input in blocks of this size. One could model this as a "processing function"
$$p : S × B → S,$$
i.e. a function which maps a state and a block of input to a new state. Often part of this state is some kind of counter or other bookkeeping information, and another part is what is the cryptographically interesting one, where the pseudo-random shuffling goes on (and where you want to have your hamming criteria going on).
At the end, when we want to produce output, another transformation $o : S → O$ is used, which transforms the state to the output. In some hash functions this is a simple projection (throw away the bookkeeping part of the state and output the rest of it), in other cases it does more processing.
We also need some initial state $S_0$ (usually fixed in the specification of the hash function), and some input padding rule $pad$, to make the input a multiple of the block size.
The whole hash function can then be modeled as this:
$$h(M) = o(p(p(\dots p(p(S_0, M_0), M_1), \dots ), M_{k-1}, M_{k}))$$
with
$$M_0||M_1|| \dots ||M_k = pad(M)$$
and each $M_i$ having the hash input block size.
Due to the iterative nature of the construction, we can process the input as it comes, block by block, assuming $pad$ only changes the end of the message (or at least all changes for a block depend only on the current block (and maybe earlier ones) and not the future ones).
If a programming interface allows supplying the input in smaller chunks, these are stored in some cache until a full input block is filled, and then the processing function $p$ is evaluated. If a programming interface allows supplying the input in larger chunks, these are splitted into the input block size. It is easy to create such interfaces which allow arbitrary sized input chunks, for any input block size, so the programmer (user of the hash function) doesn't even have to know that size.
Of course, we could view a programming interface which allows single-bit input as a "hash function" $H : S \times \mathbb Z_2 \to S$ like in your question, but then in most cases the state would change only by adding this single bit to a cache (and updating some input cache counter) – your hamming distance criteria is not valid at all.
This is not a problem, as long as the internal processing function $p$ comes near it, or the output transformation $o$, which is run at the end. After all, the user of a hash function is only interested in the final output, not in the internal state changes.
So your hash function model is not that useful as you imagine.
About your other points:

For a (cryptographic) hash function to be generally useful, it is important that it produces the same output for the same input. Using a random initial state makes this impossible. So normally some "random-looking" (or simply zero) initial state is fixed in the definition of each hash function.
If you want a random output, you can use different primitives based on a hash function (like a keyed hash, or a hash-based stream cipher).

As the state is finite, if your processing function is defined everywhere, you eventually get into a loop. Usually this loop will not contain every possible state, but be a lot shorter. This is not a weakness, as it is still longer than anyone could possible evaluate in his lifetime, assuming sufficiently random behavior and a large enough state.
In practice often the total input size is limited by some huge number so you actually don't get your loop.


What is the benefit of applying the tweak a second time using XTS?

XTS works by encrypting each plaintext block with XEX, and specifies which tweak to use.
The benefit of applying the tweak to the blockcipher output is that it makes XEX secure against chosen-ciphertext attacks.

If T is the tweak and E is the underlying blockcipher, we could consider a variant of XEX without the second application of the tweak: $\mathsf{XEX}_\mathsf{weak}(T, X) = E(h(T) \oplus X)$ (where $h$ is the keyed function used to "hash" the tweak and $E$ is the blockcipher). Then decryption would be $\mathsf{XEX}_\mathsf{weak}^{-1}(T, Y) = E^{-1}(Y) \oplus h(T)$. But this would imply that for any T, Y, and Y', $\mathsf{XEX}_\mathsf{weak}^{-1}(T, Y') \oplus \mathsf{XEX}_\mathsf{weak}^{-1}(T, Y) = E^{-1}(Y) \oplus E^{-1}(Y)$ --- the $h(T)$ terms cancel out because of the way XOR works. This is a problem because the right-hand side doesn't depend on the tweak; tweakable ciphers should look like a family of unrelated random permutations, one permutation for each tweak, but the above equality is structural and predictable.

So if an attacker were to change the first two blocks of each sector to Y and Y', he could guarantee that the corresponding two plaintext blocks would always XOR to the same constant. It's hard to see how this would result in a practical attack (although I'm sure someone imaginative could find a contrived example). That being said, in crypto we generally try to avoid saying things like, "Oh, that'll never matter" and instead try to make algorithms that remain secure regardless of context. Plus, you can't be sure you've found all the attacks unless you prove that none exist. Applying the second tweak lets us prove that there are no efficient chosen-ciphertext or chosen-plaintext attacks against XEX.


Is this adaptation of one-time-pad still secure?

No, it's not secure; after three messages, the attacker can gain information about the second and third messages.

To review this in greater detail, lets look at your proposal, and what it actually exposes to the user:

To start with, you have a secret $x_0$ and $y_0$ (I'll subscript them to distinguish the values between the iterations).  To encrypt the first message $m_0$, you generate a fresh secret $x_1$, $y_1$, and transmit:

$$m_0 \oplus x_0, x_1 \oplus y_0, y_1 \oplus y_0$$

To send the second message $m_1$, you generate more secrets $x_2$, $y_2$, and transmit:

$$m_1 \oplus x_1, x_2 \oplus y_1, y_2 \oplus y_1$$

For the third message $m_2$, you generate even more secrets $x_3$, $y_3$, and transmit:

$$m_2 \oplus x_2, x_3 \oplus y_2, y_3 \oplus y_2$$

At this point, the attacker has seen $x_1 \oplus y_0, y_1 \oplus y_0, m_1 \oplus x_1, x_2 \oplus y_1, m_2 \oplus x_2$.  If xor's all those values together, he gets:

$$x_1 \oplus y_0 \oplus y_1 \oplus y_0 \oplus m_1 \oplus x_1 \oplus x_2 \oplus y_1\oplus m_2 \oplus x_2 = m_1 \oplus m_2$$

And thus he has recovered the difference between the two messages.  And, other than the fact that the attack cannot recover the first message (because the attacker doesn't get any information on $x_0$), this is not really any better than xoring in a constant string.


Rounding down in the exponent of group element

can we build the following algorithm:
$$\mathcal{A}(g,g^x,g^{x^k},p,q) = g^{y^k} \text{ where } y = \bigg \lfloor x \cdot \frac{p}{q}\bigg\rfloor \in \mathbb{Z}_p$$

It would appear that such an algorithm that works for any input would allow us to compute discrete logs (hence we hope the answer is "no" in general, however it might be possible for certain inputs (although I personally have my doubts).
One way to do this to evaluate the discrete log of $g^x$ would be to start with evaluating $\mathcal{A}(g, g^x, g^x, 2, q)$ (that is, with $k=1$); if $x < q/2$, this evaluates to $g^0$, if $x \ge q/2$, this evaluates to $g^1$, thus halving the range of where $x$ might be.
Then, we would follow it up with $\mathcal{A}(g, g^x, g^x, 4, q)$, which would allow us to further halve the possible range of $x$.  We could keep on going until we've recovered all of $x$, hence solving the DLog problem.


Security analysis for a extended ElGamal Signature against selective unforgeability

The hashed ElGamal signature scheme was shown to be secure by Pointcheval and Stern (see Section 3.3.); i.e., the signature scheme resists adaptive chosen message attacks assuming the discrete logarithm problem is hard. The proof of security is quite remarkable, as this was the first application of the forking lemma. Sometimes they refer to the hashed ElGamal signature scheme as the Pointcheval–Stern signature algorithm.
Note that the original ElGamal scheme (where the message is not hashed) is existentially forgeable, see Theorem 16. in the linked paper above.


Is it safe to include the public certificate in xml digital signatures?

The problem that you are having is how trust in the ownership of a public key can be created. That is a problem in all public key settings and independent of the format used (like XML signatures).

As you state correctly, the pure signature verification can only check, if some public key matches the private key used to sign a mesage. After that step, you need to check if you trust the ownership relation between the public key and the (claimed) signer.

There are quite a few trust models used in practice:

Certification Authorities An authority that you trust in advance (usually via a list installed in your operating system or software) signed a certificate containing the signers name and the public key
Trust on first use Whenever you communicate with a new entity for the first time, you trust the sender' public key and store that relationship
Web of trust Similar to 1. You trust a certificate, because someone else that you already trust does so.
Manual validation You have manually checked the ownership of a keypair by the sender previously via some out-of-band mechanism (like comparing the key's fingerprint on the phone)


Poly1305-AES is a message authentication code.  AES-GCM is an authenticated cipher.  So it isn't a meaningful comparison.

But we could compare Poly1305-AES with AES-GMAC, which is a message authentication code.  They're both Carter–Wegman–Shoup MACs built out of the block cipher AES and a universal hash family based on polynomial evaluation with differential probability bounded well below $2^{-100}$.

One essentially inconsequential difference is that Poly1305-AES uses part of its key directly for its universal hash while AES-GMAC passes its key through AES to derive a universal hash key.

The main difference between Poly1305-AES and AES-GMAC is the type of arithmetic used by the underlying universal hash family, Poly1305 or GHASH, respectively:

Poly1305 uses arithmetic in the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ which is easy to implement fast in software without timing side channels.
GHASH uses arithmetic in the binary field $\operatorname{GF}(2^{128})$ which is hard to implement fast in software without timing side channels: if you don't have hardware support—or if a bug somewhere deep inside your leaning tower of software in a modern software stack has caused it to fail to take advantage of hardware support—then either your software will be slow, or your software will leak secrets through timing side channels.

Poly1305 is optimized for fast safe software implementations, whereas GHASH is a security risk unless you can guarantee you're using hardware support.  Optimized implementations with hardware support are comparably fast, running at about 1 cpb.

Of course, the same criticism of GHASH applies to AES itself, which is why you should really use ChaCha20-Poly1305 instead of AES-GCM or anything built out of Poly1305-AES.


Fast crytographically secure Pseudo-Random number generator in software

What are the methods for generating pseudo-random numbers in software?
What are the other methods available for fast pseudo random number generation?

If you don't need to be able to repeat the stream of numbers, there is little reason not to use the methods provided by the operating system - namely, urandom on linux, and CryptGenRandom in Windows. The RDRAND CPU instruction is another option, though it is often times combined with other sources of random number generation, as not everyone trusts it completely (you can ignore this unless you are dead set on obtaining absolutely secure random numbers).
Otherwise, assuming a modern CPU with AES-NI support, nothing will likely be faster then utilizing AES in CTR mode. There is no need to hash the output, this is just eating cycles for no statistical or security benefit.

Why don't people use ISAAC for their implementations?

We can only conjecture at the motivations of others. Some reasons might include:

ISAAC is not a hugely well known algorithm in the same tier as AES or salsa20

If they are not aware it's existence, they will not use it

Their requirements may be satisfied with simpler/more commonly used algorithms
Secure random numbers are not always required; Often times, numbers that look random enough work just fine.
On the other hand, sometimes security is required, as well as conformance to a particular security standard. ISAAC is not a standardized (read: officially prescribed) algorithm for use as a PRNG by any official organizations i.e. NIST.

AES-CTR-DRBG is a standards compliant PRNG.

Is ISAAC not secure enough for cryptographic applications?

The jury appears to be out on this one. There was a reason to prompt the author to design ISAAC+, so while there is no known attack that breaks it outright, it does provide less assurance then a thoroughly reviewed design such as AES or salsa20.


The source is the paper by Goldwasser and Micali on probabilistic encryption. The definition is of primary importance even though it is rarely used to prove security of encryption. The reason for this is that indistinguishability is much easier to use. However, indistinguishability is not a good intuitive definition in the sense that it is not immediately clear that it means that nothing can be learned about a plaintext from the ciphertext (beyond the length and any existing a priori knowledge). Since this latter notion is what we want to formalize, and this is exactly what is formalized in the definition of semantic security, this is the definition of encryption. Of course, by its equivalence to indistinguishability we can happily use the simpler definition, with the knowledge that nothing is revealed beyond what is already known (and the length).


Assuming this is ECB mode encryption, the workload of a known-plaintext meet-in-the-middle attack will depend strongly on the plaintext here.

If the plaintext contains some non-identical 128 bit blocks that partly coincide on a DES-block, the adversary can reverse the final AES encryption with $2^{128}$ AES decryptions work factor. They can then execute a standard meet-in-the-middle attack on 3DES using parallel collision search (easy compared to the preceding step). See van Oorschot/Wiener for details on the techniques used.

If the plaintext consists only of non-identical 64-bit blocks, the adversary can use the same idea (look for collisions of 64-bit blocks in the ciphertext after AES decryption) to at least rule out some AES keys. They should be able to rule out the vast majority of AES keys when the size of all encrypted plaintexts significantly exceeds the birthday bound for a 64-bit block cipher.

If the plaintext is short and does not contain repetitions of DES blocks that are not also repetitions of AES blocks, there may be no better idea than to perform a meet in the middle attack between 3DES and AES using parallel collision search. This should be doable in time about $\approx 2^{212}/(\sqrt{w} m)$ on a machine with $2w$ AES blocks of memory and $m$ processors (see again the parallel collision search paper).


Attack on BB84 algorithm for quantum key exchange?

What you are describing is known as the Photon Number Splitting Attack (PNS), described for the first time (I think) by Brassard, Lütkenhaus, Mor ans Sanders in this 1999 paper. Several countermeasures have been invented since (single photon sources, robust protocols, decoy states), but detailing them would stray away from of your question.

If one sends 2 or more photons, the enemy can store this photon in a quantum memory, and make the polarization measurement after the basis choice have been revealed. The enemy then knows whether to measure in the rectilinear or diagonal basis, and has all the information shared by Alice and Bob.

In 2001, Scarani, Acín, Ribordy and Gisin proposed a protocol (SARG04 pdf, wiki) which is robust against PNS attacks while using the same physical modulation than BB84. This protocol works by exchanging classical information which is more ambiguous than the basis. However, as soon as $K\ge3$ and the losses are over 50%, this protocol is subject to an unambiguous discrimination attack.


Will an algorithm that constantly changes the order of 10 hash functions be protected from an ASIC?

Will it be impossible to create ASIC for such algorithm?

No, actually it is quite easy.
The way you'd design a single brute-force core then is that you take a hashing engine for each hash function used, an input generator, a hash validator and a smart interconnect.
Then when you want to brute-force an invocation of ordering 1, the input generator outputs the guess along with routing / ordering information for the interconnect which then sends it to the appropriate engines in the appropriate order. As you are only targeting one ordering at a time, you could possibly even make this a state register of the interconnect. Then, once the first engine has processed the first piece of data, the interconnect receives it back, checks its ordering register and sends it to the next engine, while accepting the next guess for that ordering from the input generator which is promptly sent to the first engine.

Will it be impossible to create ASIC for such algorithm?

As you have seen exemplified above, there is no algorithm which is really hard to brute-force for an ASIC. The best one could hope for is that the optimal ASIC configuration would be (close) that of a modern CPU, but even then, chances are that the algorithm will not use specific parts of the CPU, e.g. FP cores, which a dedicated ASIC can drop.


What are the pros and cons of Pedersen commitments vs hash-based commitments?

The hash-based commitment scheme you are sketching is in fact not secure under collision resistance and preimage resistance of the hash function. For hiding, you need to assume that the hash function you are using behaves like a random oracle (i.e., whenever queried on a new value it returns a uniformly random value from the output domain of the hash function, and for every repeated query it answers consistently).

The random oracle assumption is an idealizing assumption which is considered to be a rather strong assumption compared to the discrete log assumption.


When do I need to use hybrid cryptography?

The protocol message size is between 100 bytes to 500 bytes. Do I need
  to use asymmetric encryption or hybrid cryptography?

To support 500 byte messages, you need about your (direct) encryption scheme to work on about 5000 bits (e.g. for RSA, Paillier, ElGamal) to provide room for the padding to gain CCA2 security. At 5000 bits, these schemes become somewhat slow, so you should definitely make a measurement in either case between a hybrid and a direct solution (using e.g. RSA-5000 with OAEP and maybe the exponents 3, 17 and 65537).

  What about Curve25519?

If you could reversible encode your message onto an elliptic curve point (not easy), you could use ElGamal or Cramer-Shoup on Curve25519 to encrypt messages of up to 32 bytes. Of course 32 bytes is much less than you want to encrypt so direct encryption is out.

Normally with Curve25519 and the other schemes you will do hybrid encryption, either as ECIES or directly by encrypting a symmetric key (using a CCA2 secure or specialized scheme like RSA-KEM) and AE encrypting the message. As an additional bonus you can then potentially re-use this shared key for multiple messages if you can do the neccessary nonce / IV management, i.e. you can guarantee that you can come up with a unique nonce for each message.


Is the dealer a volunteer in Shamir secret sharing scheme?

If no then what is the purpose for him to involve in the scheme?

This sort of "why would someone perform this protocol" question is something that crypto does not address.
Perhaps the dealer is the author of his own will, and he is delivering shares of it to his inheritors (for them to recombine after his untimely death).  Perhaps he is the owner of a cryptocurrency purse, and is distributing shares of his private key to save as backups (so that, even if one of his backups is stolen or lost, he's still safe).  Perhaps he is an HSM, and is distributing shares to the key that unlocks the administrator account.
To the protocol, the "why" question doesn't really matter.


Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k'

I had emailed Dr Thomas Pornin the very same question and received his reply. With his permission I cross post his answer as followed

From: "Thomas Pornin" ...
Date: 2021/04/22 11:38

Q1:  Additional data k' is concatenated after bits2octets(H(m)) in HMAC
input in step d.
May we also need to concatenate k' after bits2octets(H(m)) in HMAC input
in step f?

There is no real "need" here. Section 3.6 lists (but does not formally
specify) possible variants of the mechanism described in RFC 6979; these
variants are, emphatically, NOT the "true" RFC 6979 mechanism (section
3.6 says as much) and, in particular, do not match the test vectors
contained in the RFC. However, they all make sense, cryptographically
speaking, and thus can be considered in some specific contexts.
The process described in RFC 6979 has been designed to reuse as most as
possible the definition of HMAC_DRBG from NIST SP800-90A, with the
avowed goal of being able to rely on existing security analysis of that
specific construction. Note that HMAC_DRBG is still, as defined by NIST,
a random generator that expects to work along with a seed generator. The
context of RFC 6979 is outside of the scope of HMAC_DRBG; thus, whatever
we do, we cannot really claim to be using HMAC_DRBG in a formal sense;
we can only claim that we use a construction for which existing
cryptographic analysis also applies to the case of deterministic DSA and
ECDSA signatures (see references from section 4).
Thus, in that context, there is no real notion of "correct" or
"incorrect" variant. If injecting some additional input (k') into the
first HMAC call (step 3.2.d), you may or may not also inject the same
additional input into the third HMAC call (step 3.2.f). Both variants
work and "make sense" (neither seems more secure or less secure than the
other). Neither variant matches the RFC 6979 test vectors; this does not
compromise interoperability (in all of this, interoperability is about
generating signatures that are acceptable to unaware verifiers), but it
is out of the scope of RFC 6979. It is a case of "yeah, sure, you can".
Section 3.6 merely points out that having additional input (k') injected
into HMAC_DRBG maps to construction elements in NIST SP800-90A which are
designated as "additional_input" in the process on page 48 of that
document (page 47 in the 2015 revision of SP800-90A, but RFC 6979 dates
from before 2015), so that variant is not something absurd or unheard
of.
--Thomas Pornin

So I'd guessed that the term "additional input" in RFC6979 doc 3.6 (page 14 the last line ~ page 15 the first line) is not the term "additional_input" (used in generating and reseeding) in NIST.SP.800-90Ar1 doc 10.1.2.5 (page 47) in exact sense.  Nor is it the term "additional entropy" (used in instantiation) in NIST.SP.800-90Ar1 doc. It just means "additional" (extra, more) data.  We may or may not use k' as "additional entropy" or "additional input" in HMAC_DRBG instantiation or generating.


Is this algorithm good enough for small radio messages?

The question, even complemented with three useful comments, leaves me worried about the security of the system envisioned, for several reasons (from most to least serious)

The UMAC illustration in C code considered as reference in the question is secure only for single use of its key. Actual UMAC requires a block cipher, which is not stated in the question, and its code is sizably larger. While that block cipher could be TEA, that must not be TEA with the same key as the one used for encryption (that would at least invalidate the security argument of UMAC, and perhaps open to attacks).
It is not stated what the receiving device does when the UMAC check fails. If it allows other checks, including with another nounce, a 3-byte MAC seems hardly good enough: a forgery requires an average $2^{23}$ attempts (twice that if the nounce is forced to change), and at 100 per second that's less than a day. If on the other hand the receiving device stops operating when the UMAC check fails, there's a reliability problem. Rate-limiting is hard to make right, especially to make it resistant to Denial Of Service and/or random power loss.
A naive byte-per-byte implementation of the UMAC check could be very vulnerable to timing attack (reducing the average number of attempts to only about $3\cdot2^7$).
A less naive implementation doing the UMAC final check in constant time could still be vulnerable, because UMAC requires multiplication, and that's far from always constant time on a "tiny microcontroller".

Since the payload is so small (14 bits), there's a much simpler solution without UMAC (thus reducing code and removing 3 bytes in the message) that solves much of the above (in particular increases the expected number of attempts for forgery to almost $2^{49}$ attempts).

The idea is that

The sender enciphers with TEA and the fixed shared key a 64-bit block concatenating:

the 32-bit Nonce/incremental number
18 bits at zero
the 14-bit payload

The message (13 bytes rather than 16 in the question) is:

1 byte header
4 bytes Nonce (incremental number)
8 bytes cryptogram (Nonce, zeroes, payload encrypted with TEA)

The receiver(s) deciphers the cryptogram, checks that the deciphered 64-bit result starts with the Nonce (extracted from the message) and 18 bits at zero, and considers the message invalid otherwise. If a check of the Nonce is performed (e.g. that it is incremental), that check occurs only for valid messages.

This is demonstrably insensitive to timing attack as long as:

The implementation of TEA is constant-time (see note)
The 32-bit Nonce

is checked first and in constant time, e.g. using a single 32-bit compare,
or is checked together with the 18 bits at zero and in constant time.

Nothing with data-dependent timing is performed with the 14-bit deciphered payload when the above integrity check fails.
The TEA cipher is unbroken (as its stands).

Update per comment: the 32 bits of Nonce do count towards integrity. Argument: an adversary trying to make a forgery can either:

Reuse a 64-bit TEA cryptogram previously used in a genuine message, and then can either

Uses the Nonce in that genuine message; the message will pass the cryptographic check, but will be identical to the original message, thus does not count as forgery (beside, the repetition of the Nonce may allow rejecting the message, since the Nonce is supposed to be incremental)
Use a different Nonce; the message will be rejected, thus does not count as forgery.

Use a 64-bit TEA cryptogram that never was used in a former genuine message; assuming security of the TEA block cipher (and given that there can be as most $2^{32}$ genuine messages with a 32-bit the Nonce), the adversary has essentially no information about the result of the decryption of that block by the verifier. Whatever the value of the Nonce submitted to the verifier, the verifier will perform that TEA decryption, then a comparison including the Nonce bits, and the adversary has no way to predict the correct Nonce other than by trying (that's where at least the Nonce must be checked in constant time). Hence each additional bit of Nonce doubles the number of queries to the verifier (hence the duration of the attack) for a given forgery probability.

Update: if the header needs to be authenticated, change the 64-bit block format to 8-bit header, 32-bit Nonce, 10 bits at zero, 14-bit message; keep checking every bits except the message after decryption; and check at least header+Nonce (anything the adversary can vary) first and in constant time.

Note: In practice, it is hard to accidentally make TEA not resistant to timing attack. That would require the following two lines of code to exhibit a timing dependency w.r.t. v0 v1 k0 k1 k2 or k3, which is near impossible with 32-bit registers, and plausible only with smaller registers and code that does not use addition-with-carry or rotate-thru-carry.

    v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);

(I often met C compilers for 8-bit CPUs that generate code with data-dependent timing for addition of a small constant to a variable, or addition of variables of different size; but never one that did that for addition of variables of the same size, as would  be the case here in practice).

Note: in practice, the hardest part is generating and checking the nounce robustly, in the presence of random power loss and/or DoS. Write and erase in EEPROM or Flash is not atomic, sometime fails, and occasionally leaves the memory cells in a state where the value read varies (with temperature, supply voltage, or random noise).


A copy and paste from page 16 of NIST document Submission Requirements and Evaluation Criteria
for the Post-Quantum Cryptography Standardization Process;

Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 128-bit key (e.g. AES128)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for collision search on a
256-bit hash function (e.g. SHA256/ SHA3-256)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 192-bit key (e.g. AES192)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for collision search on a
384-bit hash function (e.g. SHA384/ SHA3-384)
Any attack that breaks the relevant security definition must require computational
resources comparable to or greater than those required for key search on a block
cipher with a 256-bit key (e.g. AES 256)


Does unbalancing a feistel cipher always improve security? Does it improve security at all?

Actually the article you link to does not say that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds.

Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions are "random enough". This deserves clarification: Luby and Rackoff use n-bit blocks, and their results holds up to, at least, $2^{n/4}$ queries (the attacker is allowed to submit up to that number of blocks to encrypt or decrypt to a black box which knows the key, and yet he still cannot predict the encryption or decryption of another value with non-negligible probability). Maurer and Pietrzak, and then Patarin, later showed that with more rounds, one can get as close as wanted to the $2^{n/2}$ limit (6 rounds suffice, as Patarin demonstrated). (Of course, "random enough" round functions are ideal objects whose existence is not clear; existing Feistel-based ciphers use faster functions which are certainly not "random enough", and compensate by adding more rounds.)

By making n big enough, $2^{n/2}$ is large enough to achieve sufficient security (e.g. use $n = 256$).

Morris, Rogaway and Stegers study the problem of encrypting very small blocks; thus, they cannot make $n$ "large enough". They must cope with a small $n$. The maximum theoretical security of a Feistel scheme (balanced or not) is $2^n-3$ queries (there are $2^n$ possible block values; if the attacker knows the encryption of all save two, then he can guess the remaining two with 100% accuracy, because Feistel schemes are always even permutations; this is the only known structural weakness of Feistel ciphers). The authors say quite clearly (end of page 4) that there is no known practical attack on a Feistel cipher with enough rounds, even with small blocks, so the $2^n-3$ security limit is in practice achieved. But they want more than practical security, they want proven security. A security proof works by assuming that the round functions are information-theoretically secure, and sees how the whole cipher stands up under that assumption. The trouble with a balanced Feistel cipher is that such proofs cannot go beyond $2^{n/2}$.

On the other hand, with an unbalanced cipher and many rounds (much more than 6; figures in the article go to about 64 rounds), it is possible to get a security proof close to $2^n$. This does not mean that unbalanced Feistel ciphers are "more secure", only that information-theoretic tools are more easily applied for proving security of an unbalanced Feistel cipher. And a single unbalanced round is certainly not more secure than a single balanced round; quite the opposite: security-wise, a single unbalanced round sucks. But if you accumulate enough such rounds, then you can boost the security proof to higher levels.


What is the limit of plaintext required to break the Vigenère encryption?

For chosen plaintext and a classic Vigenère cipher, you need only as many characters of plaintext as the length of the key to completely recover the key. It's a trivial reversal. (If the cipher uses 26 scrambled alphabets, it will take more.) if you don't know the length of the key, you will spot the repeating sequence after the second repeat.

For an unknown ciphertext, that's when it gets interesting. You need enough repeats of the keylength to measure the index of coincidence. The Friedman test provides a way to estimate the amount of ciphertext.


Non interactive threshold signature without bilinear pairing (is it possible)?

The scheme as written is insecure if an attacker can get the same message signed twice.

The honest parties will compute their $m_i$ deterministically, but the attacker doesn't have to.

The attacker will get $(m_i - c \cdot y_i) = p_i$ and $(m_i - c' \cdot y_i)= p_i'$ for each participant.

These equations can be solved to get $y_i = \frac{p_i - p_i'}{c' - c}$. Since the attacker knows all the values on the right-hand side, the attacker can get $t+1$ shares and recover $y$.

One possible solution to avoid this is to ensure that the same message is never signed twice.


The problem with this approach is that it literally gains you nothing. In order to choose a random subsequence of a needed length from $\pi$, you need to generate a cryptographically random number of at least the same length of the desired key to use as the offset. But then you may as well just use that number as your secret key.

Other than that, yes, it's exactly the same as a one-time pad. Just with a silly and pointless key derivation protocol which cannot mathematically increase the security of the system, but could conceivably weaken it.

Edit: As Thomas points out in the comments, the distribution of digits of $\pi$ are not random, and so this mechanism of key generation actually discards a significant amount of entropy that had been generated while choosing a random offset.


No, likely this won't work. Almost all HSM's will only accept wrapping keys of a type that is compatible with the encryption / wrapping algorithm. Commonly it is impossible to get to the value of the key as well, so that won't save you.

Sometimes you can wrap a key to export it and then re-import it again. Then you might be able to create a new AES key from the remnants of the exported key. You would of course then use AES-192 or AES-128 if you use only the first 16 bytes of the ciphertext. Generally this won't work for FIPS mode though, so applicability might be limited. And you'd of course loose 16 bits or more of key space because of the parity bits - so security would be at the same level as 3DES.

A better option would be to derive an AES key from the triple DES key. Of course, this also needs to be possible in your HSM and the key must be usable for the key derivation mechanism. That way you would get a different key value, but one that is still linked to the value of the DES key(s).


Verify signature from set of public keys, but not revel which specific key it was

Yes:  https://en.wikipedia.org/wiki/Ring_signature

$\color{white}{I needed twenty-five more characters.}$


Does any popular symmetric cipher allow for direct re-ciphering?

Yes, this is possible for all synchronous stream ciphers where your plaintext $M$ is simply XoRed with a keystream $K_1$ to produce the ciphertext: $D_1=M\oplus K_1$ because then you can simply XoR again the ciphered data $D_1$ with $K_1\oplus K_2$ together to get: $$D_2= D_1 \oplus K_1\oplus K_2 = M \oplus K_1\oplus K_1\oplus K_2 =M\oplus K_2.$$

So modern stream ciphers such as Chacha20, but also older such as AES-CTR, support this.

This also means that you can also use this with any block cipher in CTR mode of operation, so Camellia, IDEA, AES etc. are all fine.

However, other stream cipher have ciphertext dependent operations, like AES-CFB, and won't allow for it as easily. Besides, if you want to have actual security you should also worry about authenticity and integrity of your data, which means you have to HMAC (or CBC-MAC) again with the new key afterwards... AEAD schemes won't typically support "re-keying" of the cipher.

It might also be possible for other ciphers, in ways similar to those explained in this recent answer.

There are also other malleable schemes which might allows you to change a part or all of the secret material without decryption, provided you know both the old and new secret material, for instance it is easy in RSA to change the public & private exponents, but then you need to use the same $N=pq$, so anybody knowing the factors $p,q$ would still be able to crack both private exponent, being given the public exponents.


DES: how does Richard Outerbridge's Initial Permutation operate?

By definition, applying the initial Permutation of DES is shuffling bits per

01 02 03 04 05 06 07 08           58 50 42 34 26 18 10 02
09 10 11 12 13 14 15 16           60 52 44 36 28 20 12 04
17 18 19 20 21 22 23 24      \    62 54 46 38 30 22 14 06
25 26 27 28 29 30 31 32   ----\   64 56 48 40 32 24 16 08
33 34 35 36 37 38 39 40   ----/   57 49 41 33 25 17 09 01
41 42 43 44 45 46 47 48      /    59 51 43 35 27 19 11 03
49 50 51 52 53 54 55 56           61 53 45 37 29 21 13 05
57 58 59 60 61 62 63 64           63 55 47 39 31 23 15 07

where the left table represents, in reading order, bits of the 64-bit input from first (most significant) to last; and the right table represents, in reading order, the Left then Right 32-bit registers, per that same convention.

That transformation has great regularity: each line of the output (in reading order) is a column of the input (from bottom to top). That's a property of a transpose except for inverted order. IP is a mirror of the input according to the / diagonal, followed by a regular shuffling of lines (lines 1 2 3 4 5 6 7 8 go to lines 4 8 3 7 2 6 1 5).

This structure of IP has a hardware rationale: the transpose allows an implementation with Left and Right registers implemented each as four 8-bit shift registers, with 1 bit entering in each of the 8 shift registers for each plaintext octet sequentially fed into the DES hardware. And the shuffling brings next to each others the bits that interact when XORing the Left and Right registers.

The question's code makes use of 5 "Half-Butterfly Permutations" (as I name them by analogy with the butterfly diagram) indexed with $k$ taking all values from 0 to 4. Each splits the 32-bit lleft and right registers into $2^{5-k}$ segments each $2^k$-bit, and exchanges odd-numbered segments of one register with the higher (even-numbered) segment of the other, with thus a shift by $2^k$-bit.

One general HBP is implemented with 3 instructions involving a total of 6 bitwise operations directly supported by C. It uses XOR in a way similar to exchanging x and y with the idiom x^=y; y^=x; x^=y; taking advantage of associativity and commutativity to avoid a work value; but uses one due to the shifting and masking.

There are some irregularities in the code to perform the prescribed shuffling of lines. Also, the code wants to end with the 32-bit lleft and right pre-rotated on the left by 1 bit, because then the low-order 6 bits of these registers are properly aligned to serve as index in an S-box (after XOR with sub-key); and the HBP with $k=0$ is performed between these two rotations, because that removes the shifts in that HBP.

Here is how it goes step by step. We start from

01 02 03 04 05 06 07 08     most  significant byte of lleft
09 10 11 12 13 14 15 16     :
17 18 19 20 21 22 23 24     :
25 26 27 28 29 30 31 32     least significant byte of lleft
33 34 35 36 37 38 39 40     most  significant byte of right
41 42 43 44 45 46 47 48     :
49 50 51 52 53 54 55 56     :
57 58 59 60 61 62 63 64     least significant byte of right

then perform the Half-Butterfly Permutation with $k=2$

work   = ((leftt >> 4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

giving

37 38 39 40 05 06 07 08     most  significant byte of lleft
45 46 47 48 13 14 15 16     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
49 50 51 52 17 18 19 20     :
57 58 59 60 25 26 27 28     least significant byte of right

then perform the HBP with $k=4$

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

giving

49 50 51 52 17 18 19 20     most  significant byte of lleft
57 58 59 60 25 26 27 28     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
37 38 39 40 05 06 07 08     :
45 46 47 48 13 14 15 16     least significant byte of right

then perform the HBP with $k=1$

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
57 58 41 42 25 26 09 10     :
53 54 37 38 21 22 05 06     :
61 62 45 46 29 30 13 14     least significant byte of lleft
51 52 35 36 19 20 03 04     most  significant byte of right
59 60 43 44 27 28 11 12     :
55 56 39 40 23 24 07 08     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the HBP with $k=3$

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
57 58 41 42 25 26 09 10     most  significant byte of right
59 60 43 44 27 28 11 12     :
61 62 45 46 29 30 13 14     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the pre-rotation of right by one bit to the left

right  = (right << 1) | ((right >> 31) & 1);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
58 41 42 25 26 09 10 59     most  significant byte of right
60 43 44 27 28 11 12 61     :
62 45 46 29 30 13 14 63     :
64 47 48 31 32 15 16 57     least significant byte of right

then perform the HBP with $k=0$, eased by the previous rotation

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;

giving

58 50 42 34 26 18 10 02     most  significant byte of lleft
60 52 44 36 28 20 12 04     :
62 54 46 38 30 22 14 06     :
64 56 48 40 32 24 16 08     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

then perform the pre-rotation of leftt by one bit to the left

leftt  = (leftt << 1) | (leftt >> 31) & 1);

giving

50 42 34 26 18 10 02 60     most  significant byte of lleft
52 44 36 28 20 12 04 62     :
54 46 38 30 22 14 06 64     :
56 48 40 32 24 16 08 58     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

Skipping the pre-rotations and accordingly adjusting the HBP with $k=0$ would have given exactly the permutation specified for IP.


The difficulty of computing discrete logs

I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$).

The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for characteristic 2, but can be defined here as well).

So let's define $Z(a)=\log_g(g^a-1)$ and note that it sets up a one-to-one correspondence between $a$ and $Z(a)$. Thus the difficulty of discrete logs is not really changed by introducing the kind of twist you ask about, in your reference to "trivial things".

I can't dig out the reference now, but there was a paper years ago by a French author, in a crypto related conference or journal, on whether precomputing Zech's logarithms on some subset of $F_p^{\ast}$ helped with discrete logarithms. The answer was, "not so much".


For key $k_0$, nonce $n$ (‘initialization vector’), and message $m = m_0 \mathbin\| m_1 \mathbin\| \cdots \mathbin\| m_{\ell - 1}$, the AES-CTR ciphertext is $c = c_0 \mathbin\| c_1 \mathbin\| \cdots \mathbin\| c_{\ell - 1}$ where $$c_i = m_i \oplus \operatorname{AES}_{k_0}(n \mathbin\| i),$$ where $n \mathbin\| i$ is some unique encoding of $n$ and $i$ as a 128-bit block.  ESSIV means we derive $$n = H_{k_1}(\mathit{sector\ number})$$ to encrypt each disk sector.  We usually call $n$ a nonce instead of an IV because the only rule is that it must never be repeated with the same key; the consequences of nonce reuse are catastrophic.

This means that ‘CTR-ESSIV’ not terribly useful for disk encryption unless you never rewrite a disk sector: the standard threat model for disk encryption is disclosure of multiple versions of a disk, which would be the case if the border police confiscate your laptop whose SSD had queued up old versions of many disk sectors for deferred erasure.  In this threat model, CBC-ESSIV leaks only how long a prefix of each sector changed between the two versions; in contrast, CTR-ESSIV may allow arbitrary decryption of disk sectors depending on what the adversary knows about the different versions.


Q1 : It won't weaken things assuming a few things. Normally storing cipher text is at worst equivalent to storing plaintext. Encryption is invertible. That means no information is lost in the process. It's not different, in that sense, from storing data in a different format. (Raw bytes, base64 encoded text, hexadecimal, etc.)

The assumptions are:

The cipher implementation is bug-free. (No guarantee that something doesn't go wrong in some way if encryption can go wrong in some known or unknown ways.)
The key is independent of inputs or personal data. (If a key is derived from the password or personal data, then cracking the key means that data gets leaked. Use a randomly generated key.)
No side channels. (Implementations of an algorithm can leak  plaintext or keys.)

Q2 : That defeats the purpose of encrypting hashes. If you don't have the private key then you cannot rotate keys. This also isn't going to help if people who can crack your passwords have access to the public key.

With the ciphertext, $E_K(H(\text{salt}, \text{password})$, and public key, $K$, the strategy for cracking the encrypted hashed password is about the same as the strategy for cracking hashed passwords.

Normally password cracking is done by generated candidate passwords and testing if
$$ H(\text{salt}, \text{password}) = H(\text{salt}, \text{candidate)}$$

Cracking encrypted passwords with known public key K instead tests

$$ E_K(H(\text{salt}, \text{password})) = E_K(H(\text{salt}, \text{candidate)})$$

I assumed the public key encryption method is deterministic. (Or if it includes a IV that value is known, making it deterministic.) If you cannot decrypt the data then you must have determinism because that leaves only comparing ciphertexts as a possible means of verifying passwords.

The intuition behind using public key encryption here is that it means the password cracker cannot decrypt encrypted data and that the encrypted password hashes are therefore no good to him. That's wrong because the public key (if it becomes "public" or at least known to the cracker) enables him to do, on his own computer, whatever the server does for verifying passwords.

Strong asymmetric encryption with a public key after deleting the private key will act like a one way function, just like hashing. You can compute $H(x)$ but not $H^{-1}(x)$. Similarly you can compute $E_K(x)$ with public key $K$ but not $E_k^{-1}(x)$ without $k$, the private key corresponding to the public key $K$. A password cracker does not need the ability to compute the inverse operation. It suffices to use the forward (one-way) function and compare his result to stored data.

(Also, there are scenarios where I wouldn't worry about symmetric ciphers inadvertently having side channels, but I might worry about public key side channels. If, for example, it didn't have a constant time implementation or if attacks requiring physical proximity were a concern.)

Should you encrypt password hashes?

It shouldn't (and probably won't) hurt. It's a plus to be able to rotate keys.

One "helpful" (odd) scenario: Your password database gets stolen, then your encryption key. You find out so you tell your users to change their passwords. The hacker gets your password database again (but not your encryption key for some reason) and wants to crack new passwords. The new password database isn't useful then.

If you're using a typical database it also helps to encrypt data before it goes into the database. If you delete or modify rows, then that doesn't necessarily mean the data disappears from the hard drive. It will disappear from database dumps, but instead of overwriting the space where data used to reside with zeros it might set a "deleted" bit flag or simply change what address a pointer points to. With encrypted data you can do a sort-of-delete of arbitrarily long ciphertext simply by overwriting the key used to encrypt it. It's good to encrypt your hard drive for the same reason.

It's best if you can store your key in a HSM. This means if your password database gets leaked it won't be possible to do offline cracking.

If a hacker can bypass your password check rate limit or is able to execute arbitrary code on your server, however, then he can still do online cracking or use your server for cracking passwords.

Maybe if you have a second server you can implement a kind of poor man's HSM. Use the first server as your front facing web server, allow the public internet to access it. Use your second server to verify passwords on behalf of the first. Do not allow access from the public network to the second server. The second server can store salts and hashes but only return salts in response to a user-id or true/false in response to a hash. It can do rate limiting on verifications against individual user-ids.


How to deal with collisions in Bitcoin addresses?

Cryptography (and real security in general) offer quantitative analysis of the security provided - Meaning, real security products will describe how long they will resist a certain class of attack.

With cryptography, we select our parameters such that the time required to perform the best attack would exceed the amount considered to be practical, realistic, or feasible.

With a larger input space then output space, collisions must exist - therefore the only solution is to:

Accept that collisions must exist
Make collisions so rare as to not be a problem

This is exactly what the bitcoin protocol has more or less done. Granted, $2^{80}$ could arguably be a little bit bigger for more comfort; Bitcoin could have used bigger hash functions, but they may have been limited by availability at the time. If you were going to re-design it, I'm sure you would use larger sizes now. But that's always easy to say in retrospect...


Is the following authentication protocol insecure?

Bob needs proof that Alice is authentic:
A-Open Connection-Cert partial random key->B Both keys combine to form an access key.

Standard one-way authentication protocol only requires submitting a correct password once, in order to gain access and control. By randomizing part of Alice's password, significantly reduces the likelihood of her password becoming victim of replay attacks and man-in-the-middle-attacks, just to name a few. [Random Assymetric] Bob's server has been preset for random variations of Alice's hash value

Is there anything wrong with it in terms of security and performance?

Technically speaking, there is nothing wrong with your suggested one-way authentication protocol. However, the security function of your protocol can be increased by preconfiguring Bob's server with random hash variations of Alice's password for added security. Best of luck with your protocol


What Java actually stores inside Keystore when generating Keys?

Nitpick: keytool accepts both alias and keypass if specified; if not specified it prompts for key password if needed but defaults alias to mykey. A JCEKS file can be operated on either by keytool or by other code.
JCEKS can support three types of entries: privateKey, trustedCert, and secretKey (the older and default JKS file can do the first two).

The operations and algorithms you ask about are "symmetric" (not "synchronous") and use a "secret" key NOT "public" and "private" keys which apply to algorithms like RSA, DSA, ECC.
Also symmetric keys including AES are NEVER in certificates.

A secretKey entry contains the secretkey encrypted using the keypassword (using a PBE aka key-stretching algorithm). The password itself is not stored, which would be totally insecure, and instead must be provided on any attempt to access the privatekey. Note that you can change the alias of a secretkey entry and/or re-encrypt with a different keypassword without changing the key.


Using Euler's theorem.. how can I get appropriate x..?

This is RSA with $p=7, q=13$. First compute $d \equiv 29^{-1} \pmod {\varphi (pq)}$ and then $x \equiv 4^d \pmod{(pq)}$


Questions about the Curve25519-donna implementation

You have 5 limbs because it is based on DJB's papers and as the Ed25519 paper mentions, it's using a $2^{51}$ radix representation for performance reasons.

It does so in order to avoid carries when performing field multiplication. Because otherwise the carry bits need to be handled by subsequent additions, which slows down even modern CPUs.

So according to the paper, to reduce the number of expensive adc/subc instructions, they represent an element $x$ of $\mathbb{F}_{2^{255}−19}$ as $(x_0,x_1,x_2,x_3,x_4)$ with $x =\sum_{i=0}^{4} x_i 2^{51i}$.

So in the end the multiplication should be accepting inputs with each limb having up to 54 bits.

Working with polynomial form allows to efficiently perform computation modulo the field's order. It allows to simplify the code required to implement the different arithmetic operations and thus is more comfortable to work with. Polynomial form is the natural way to represent integers modulo something.

Now regarding the bit manipulations done on the secret key, they are done in order to convert (random) 32 bytes into integer scalar.

The bit manipulation are there to set the three
   least significant bits of the first byte and the most significant bit
   of the last to zero, set the second most significant bit of the last
   byte to 1.  This means that the
   resulting integer is of the form $2^{254}$ plus eight times a value
   between $0$ and $2^{251} - 1$ (inclusive).

Now, as for why they are performed, the lower three bits are cleared to prevent a small subgroups attack.
And now regarding the MSB, it is set to 1 in order to avoid timing leaks.

Regarding the reason for the presence of two multiplication cmul first and fmul next, that's because cmul is actually computing, for an integer $n$ and a point $V$ the value $Curve(nV)=x/z$, so we have that $z\cdot Curve(nV) = x$.

Since we don't want the x-coordinate of the resulting point in this short form $x/z$, we need to convert it into the actual x-coordinate value, hence the crecip and fmul calls.

Finally, yes you should be able to derive private key and public keys independently of each other à la BIP32.


Vertical bar and comma in hash function input

I don't know anything about IEEE 802.11i, so I can't be sure about my answer, but hopefully this provides some insight.

From the way in which the formula is written, $H$ is probably some sort of keyed hash algorithm—probably HMAC.  HMAC takes two parameters: the secret key to the MAC and the data to hash.  The first parameter is probably the secret key to HMAC, with the concatenated data being the data to hash with HMAC.


For 192 bit key(AES-192), there are 6 columns of 32 bit each i.e 4x6 Matrix. These 192bits of Master Key are shown as k0,k1...k5, i.e 6 words of 32 bit each.

(See page 44 of Book "The Design of Rijndael")

Now k6 will be

k6 = SubByte((RotateWord(k5)) xor K0 Xor Rcon1

k7 = k6 xor k1

k8 = k7 xor k2

and so on...

Since the state in al variants of AES is 128 bit(its the key which is either 128 or 192 or 256 bit) i.e 4 words of 32 bit, the Round Key 0 will consist of k0,k1,k2,k3. The Round Key 1 will consist of k5,k6,k7,k8 and likewise.

We only need 13 x 4 = 52 keys, because the input state is still of 4 words of 32 bit each (128-bit) and each Round Key is also 128 bit. Its only the Master Key which is 192-bits(6 words of 32-bit)

This Animation explains AES-128.


Can an altered RSA private key still work as the original?

I would be surprised that a proper system will work with this;

It fails in openssl check.

    openssl rsa -in sample_rsa_prv_mod.key -check RSA key
    error: n does not equal p q

If you look at an ASN1 parser like ASN.1 JavaScript decoder you will see that your modifications change the modulus. Why the rest didn't corrupt, since the ASN.1 format uses delimiters.

The modulus is not correct. The Khan Academy provides no warning about this i.e. doesn't check as OpenSSL and this implies not a good library. Their implementation may use CRT and from the modulus with $n = p \cdot q$. This is the only plausible explanation since I've tested for some other plaintexts, too.
How the OpenSSL command line behaves with these two private keys;
$cat input.txt
1234567890

$ openssl rsautl -encrypt -pubin -inkey sample_rsa_pub.key -in input.txt

$ openssl rsautl -decrypt -inkey sample_rsa_prv.key -in encrypted.txt
1234567890

$ openssl rsautl -decrypt -inkey sample_rsa_prv_mod.key -in encrypted.txt
RSA operation error
140083785925952:error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error:../crypto/rsa/rsa_pk1.c:251:
140083785925952:error:04065072:rsa routines:rsa_ossl_private_decrypt:padding check failed:../crypto/rsa/rsa_ossl.c:491:

As we can see, it fails to decrypt. So, the only plausible explanation is again they construct the $n$ from $p$ and $q$. They don't use $n$ in the file.

Note: They use various sources in their JS and probably one fails on their usage.

Textbook RSA little 101

Select target security $t$, today  $t> 2048$
Select public exponent $e$, $e= \{3, 5, 17, 257,65537\}$ are possible candidates;
Generate two unifrom random prime $p$ and $q$ where each has 1024-bit
Form the modulus $n = p \cdot q$
Calculate Euler's totient function $\phi(n) = (p-1)\cdot(q-1)$ ( Actually use Carmichael Function $\lambda(n) = \text{LCM}(p-1,q-1)$ that can produce shorter private exponent $d$)
Check $\gcd(e,\phi(n))=1$, if not 1 return to step 3.
Find $d$ with Ext-GCD such that $e \cdot d = 1 \bmod \phi n$.
Publish the public key as the pair $(n,e)$, the RSA modulus, and the public exponent.
Keep secret the private key $(n,e,d,p,q)$ ( possible more: $n,e,d, p, q, d_p,d_q,d_{inv}$. The values $d_p,d_q,d_{inv}$ are used for CRT based calculation that can speed up modular exponentiation up to 4-time s)

Now encrypt a message $m$ as $c = m^e \bmod n$ and decrypt with $m = c^d \bmod n$.
TextBook RSA as the name suggests should never be used in practice. If you want to use RSA to encrypt some small messages use PKCS#1 v1.5 or OAEP padding to mitigate the attacks, see 20 years of RSA.
If you want to use RSA for signature, use it with PSS padding.
Today RSA mostly used in signatures. For encryption, we prefer hybrid-cryptosystem like key exchange with DHKE (better the ephemeral elliptic curve version ECHKE) and encrypt with authenticated encryption modes like AES-GCM(-SIV) and ChaCha20-Poly1305. It is possible to use RSA-KEM to send the key, too.


I am interested in theoretical answers, assuming there is infinite time for decryption.

We call such an attacker a 'computationally unbounded adversary'

  Is it necessary to work out the private-key exponent for decryption? Are there no alternative options?

One approach that a computationally unbounded adversary could is as go through all possible values $M$, and find one which has $M^e = C \bmod n$; such a message $M$ is the decryption of the ciphertext $C$.

This approach actually takes longer than the more traditional approaches that involve factoring $n$ (and from that, rederiving the decryption exponent); however a computationally unbounded attacker might not care.

  Can a message encrypted using RSA be decrypted using only the public key? If so, how? If not, why?

Actually, there are a number of different ways that RSA could be decrypted by a computationally unbounded attacker

They can brute force the message (as listed above)
They could factor the modulus, and rederive the decrypion exponent
As pointed out here, they could generate every possible public/private keypair, and pick out the public key that they actually see.  Any public key cryptosystem can be broken by this method.

So, if RSA can so easily be broken by a computationally unbounded adversary, why do we still use it?  Well, we don't believe that computationally unbounded adversaries exist, and so that's not considered a real world requirement on crypto systems.  Actually, if they do exist, we don't have that much in the crypto toolbox that they can't trivially break anyways.


Difference Between Gravity-SPHINCS and SPHINCS+?

Gravity-SPHINCS and SPHINCS+ are two different improvements of the original SPHINCS algorithm. Both change the few-time signature scheme HORST (used in SPHINCS) in slightly different ways. However, both are variations of HORST.
This leads to variable length signatures for Gravity-SPHINCS and fixed length signatures for SPHINCS+ which are as long as the signatures one would obtain from using the Gravity-SPHINCS few-time signature scheme in SPHINCS+ in the worst case. However, the often shorter variable length signatures come at the cost of far more complicated signing and verification.

Moreover, both change the way the index of the used few-times signature scheme gets computed. While different, both achieve that the index can be verified by the verifier which was not the case for SPHINCS. Finally, Gravity-SPHINCS uses the assumption that collision-finding for quantum computers is as slow as second-preimage finding under certain assumptions about storage access times. Hence, Gravity-SPHINCS slightly simplifies the way hashing is done in the construction at the cost of only achieving a security reduction from collision resistance of the internal hash function. On the opposite, SPHINCS+ gets a security reduction from second-preimage resistance of the internal hash function (there are different assumptions on the hash function used to compress the message in both proposals).

So to summarize, the schemes follow the same high level design principle but instantiate it in very different ways. Which one is better probably depends on what you want.


Optimized modular multiplicative inverse for Bitcoin (secp256k1)

Half-extended binary GCD

The extended binary GCD of the HAC's algorithm 14.61 mentioned in the question, when given positive integers $x$ and $y$ , computes integers $a$ , $b$ , $v$ with $ax+by=v=\gcd(x,y)$ . When $v=1$, it follows that $a$ is the multiplicative inverse of $x$ .

In our context, $0<x<y$, $y$ odd, $\gcd(x,y)=1$ (the last two conditions are met since $y$ is $p=2^{256}-2^{32}-977$ of secp256k1$v=1$ , which is prime); thus $a$ is always the inverse. Importantly, we do not need $b$ , which allows simplifications. This leads to the half-extended binary GCD, which I hope can help to some degree:

If $x$ is odd then $u\gets x$ ; else $u\gets x+y$ ;
$v\gets y$ ; $a\gets0$ ; $d\gets 1$ ;   [or $d\gets y-1$ in unsigned variant, see note]
While $v\ne1$
[invariant here and at start of the next while loop: $u$ and $v$ are odd and distinct]

While $v<u$

$u\gets u-v$ ; $d\gets d-a$ ;   [or $d\gets d+a$ in unsigned variant, see note]
While $u$ is even (that's at least once)

If $d$ is odd then $d\gets d+y$ ;
$u\gets u/2$ ; $d\gets d/2$ ;

$v\gets v-u$ ; $a\gets a-d$ ;   [or $a\gets a+d$ in unsigned variant, see note]
While $v$ is even (that's at least once)

If $a$ is odd then $a\gets a+y$ ;
$v\gets v/2$ ; $a\gets a/2$ ;

$a\gets a\bmod y$ ; that's the desired inverse.

Note: As shown, $a$ and $d$ are signed. In an unsigned variant we can keep them non-negative, by making the three changes noted.

As shown, $a$ and $d$ can grow to several times $y$ (in absolute value for the signed variant). We can devote some extra bits to this. I conjecture without proof that $\max(|a|,|d|)<4y\log_2(y)$ (or $\max(a,d)<8y\log_2(y)$ for the unsigned variant). Alternatively, we can change $a\gets a+y$ into $a\gets a-y$ when $a\ge0$ for the signed variant (for the unsigned one, that can be when $a\ge y'$ for some convenient $y'\ge y$, e.g. $y=2^{256}$ ); and same for $d\gets d-y$ . This is enough to ensure everything stays below $4y'$, or $2^{258}$ in the context.

Possible optimization: the number of times $i$ that the "While $u$ is even" loop is run is predictable from the low-order bits of $u$, and we can group the overall effect on $u$ and $d$ into a single loop. What needs to be added to $d$ depends on $i$, the $i$ low-order bits of $d$, and $y$ . It can be precomputed since $y$ is fixed. Even if we do this for $i$ up to 2 or 3 only (then iterate if necessary), that saves significantly (on a classical CPU at least). Same for $v$ and $a$.

The (half)-extend Euclidean algorithm (see this answer) also computes the multiplicative inverse, and has a simple variant avoiding multiplication (the quotient is made a power of two). It can be competitive. The two can be blended.

GPUs are best at SIMD workloads

GPUs shine at workloads where the same instruction flow applies to different independent jobs launched in parallel. Taking different code paths in simultaneously launched jobs at best dramatically reduces performance. Thus GPU-friendly algorithms are those with long sequences without tests, and tests which predictably mostly take the same path in different jobs. Algorithms often need to be tweaked towards that.

[hopefully more to come there]

It's a brute force attack

The attack require about $2^{b-1}$ point addition to find a private key with $b$ unknown bits, or about $256-b$ known bits (e.g. at zero). I see no reason why there should be such keys, other than deliberately. Thus I'm doubtful on the overall usefulness of the thing. We can still think about it for educational purposes.

Starting from addresses forces using Cartesian coordinates

Because a version of the attack is said to be hash-bound, we know that the attack tries to find a private key from the hash (known as address) of the corresponding public key, rather than from the public key. This has been confirmed in comments of that other answer, which proposes a mathematical technique assuming the public key is known. I'm not exploring that avenue.

Thus, the bulk of the sequential version of the algorithm is to compute public keys $kG$ for incremental private key $k$ using point addition of $G$ to move from one public key to the other; hash the resulting public key (essentially) in its Cartesian uncompressed $X\|Y$ form; and check the hash.

The attack should be multi-target

There is a tremendous potential benefit in targeting multiple addresses simultaneously; only the comparison of the final hash is made slightly more compute intensive (it becomes a search among the addresses targeted), and all the rest is shared. That's too good to ignore.

Outer loop for GPU (it's fine)

When optimizing an algorithm for GPU or other highly parallel architecture, it is essential to split the task into independent jobs. That part of the question made me think it was not done:

  search starting from public key G (private key 1) and point increment (addition of G) to get next key

With this algorithm, the overall search speed would not scale up with more GPU power: point increment is going to be a bottleneck no matter how optimized it is.

But the question now also has:

  Main program computes an array of public keys using scalar multiplication.

and that suggests "starting from public key G (private key 1)" does not apply to the OpenCL jobs/kernels. Instead, the private key search interval is subdivided, the corresponding public key computed, and the search performed; that's fine.


Why does openssl derive IVs from a password?

If you read the manpage you referenced a bit more carfeully, you will find the following lines:

  -nosalt

do not use a salt

  -salt

use salt (randomly generated or provide with -S option) when encrypting (this is the default).

and

  The -salt option should ALWAYS be used if the key is being derived from a password unless you want compatibility with previous versions of OpenSSL and SSLeay.

  Without the -salt option it is possible to perform efficient
  dictionary attacks on the password and to attack stream cipher
  encrypted data. The reason for this is that without the salt the same
  password always generates the same encryption key. When the salt is
  being used the first eight bytes of the encrypted data are reserved
  for the salt: it is generated at random when encrypting a file and
  read from the encrypted file when it is decrypted.

Putting this together we learn:

You should use a random salt, which gets used in the key derivation process (calculating the encryption key and the IV from the password)
If you use a salt, the key and the IV and thus the ciphertext won't be deterministic
Using a random salt is the default behaviour of openssl enc

You can easily check this by running

echo foo |openssl enc -aes-128-cbc -out encrypted -nosalt

and

echo foo |openssl enc -aes-128-cbc -out encrypted

In the first case, the output will be 16 bytes long (one block of AES), in the second case it will be longer, because the salt has to be stored.


Verification of signed message with encryption

There is some confusion in your question, because a signature in a public key cryptosystem is (usually) not just a hash, but a hash of the message that is signed using the private key. E.g. in RSA it would be a hash value padded and raised to the private exponent.

There are two ways to have an authenticated encryption in a public key system: Should we sign-then-encrypt, or encrypt-then-sign? In encrypt-then-sign, the receiver can verify the signature just as if they had received a signed plaintext message. In sign-then-encrypt they would first have to decrypt the message, but then they have just a signed plaintext.

In either case the message hash can be calculated by anyone since it does not include keys. The keys only come into play when verifying that the signature was taken over the hash, and there the public key is enough.

For low level details of how it works in the case of RSA you can refer to PKCS #1.


What is the difference between a Vigenère cipher and a one time pad cipher?

The Vigenère cipher is essentially a series of interwoven Caesar ciphers, in which the size of the shift is different for each character and is defined by the keyword.

The one-time pad (OTP) is a very similar technique in which the only difference is that key is generally:

truly random,
at least as long as the message,
and never reused (thus the name),

making it provably confidential if the key is kept secret.

In this way, both ciphers make use of modular addition, which is still in use in most modern digital cryptography. But, in the case of the OTP, the length of the key guarantees that the ciphertext is not vulnerable due to repetition in the way that the Vigenère cipher is.


Semantic security IND-CPA of Affine Hill Cipher

Let $G:\{0,1\}^{r+l}\to\{0,1\}^*$ be some pseudorandom generator, let $K\in\text{GL}(\mathbb K,d\times d)$ be any invertible matrix over some field $\mathbb K$ and let $k\in\{0,1\}^{r+l}$ be the secret key for $G$ and $f:\{0,1\}^*\to \mathbb K^d$ be some bijective function mapping the PRG outputs to vectors, then $E_{K,k}(m):=m\cdot K+f(G(k))$.

This scheme is deterministic, that is given the same keys and the same message, it will always return the same encryption and thus cannot be CPA-secure.

However, we can easily modify the above scheme to make it CPA-secure. Let $G,K,f$ be as above and let $k\in\{0,1\}^r$. Define $E_{K,k}':=n\stackrel{\$}{\gets}\{0,1\}^l;n\parallel m\cdot K+f(G(k\parallel n))$, where $\stackrel{\$}{\gets}$ means that $n$ is sampled uniformly at random from $\{0,1\}^l$.

Essentially for every encryption we generate a nonce $n$, append it to the ciphertext and then use combination of the nonce and the key to generate the random bitstream. This is how stream ciphers work, but we are using vector-addition instead of XOR. Actually one could make appropriate choices for $f,K$ to turn this into a classic stream cipher by picking $K=\mathbb F_2$ and $f$ mapping bitstrings to vectors of the same strings. The bijectivity of $f$ is needed to preserve the uniformly random distribution of the output elements to make it an appropriate "pad". As for why $K$ is there, I don't know, it doesn't serve any purpose for the security in this scheme.


What role does the mode of operation play in Veracrypt vs. Bitlocker?

The final part of your question ignores that there are multiple reasons to choose an encryption mode, other than bits of security. Different encryption modes offer different levels of performance, and there is more trust in modes that have been around longer.

The model of an attacker used for disk encryption is slightly different than the model used for other attacks.

To quote wikipedia:

  Disk encryption methods aim to provide three distinct properties:

  The data on the disk should remain confidential.
     Data retrieval and storage should both be fast operations, no matter where on the disk the data is stored.
     The encryption method should not waste disk space (i.e., the amount of storage used for encrypted data should not be significantly larger than the size of plaintext).

  The first property requires defining an adversary from whom the data is being kept confidential. The strongest adversaries studied in the field of disk encryption have these abilities:

  they can read the raw contents of the disk at any time;
     they can request the disk to encrypt and store arbitrary files of their choosing;
     and they can modify unused sectors on the disk and then request their decryption.

  A method provides good confidentiality if the only information such an adversary can determine over time is whether the data in a sector has or has not changed since the last time they looked.

Plain CBC mode is susceptible to a watermark attack in these cases.  When it comes to disk encryption however, normally CBC mode + ESSIV is used which takes care of the watermarking attack. CBC also suffers from the possibility of a malleability attack. (Basically another word for the commonly known CBC bit flipping attacking)

XTS mode offers protection against watermarking built in, but the chief reason to choose XTS is due to its support for ciphertext stealing. Basically ciphertext stealing is a property which allows data sectors whose length is not evenly divisible by the block size to be securely encrypted without expanding the ciphertext.

XTS however has two disadvantages. The size of the key is doubled for the same strength of encryption, and it does not provide protection against data tampering. (Modifying the ciphertext will result in valid decryption to gibberish plaintext) Redundancy for sectors is handled at an application level, and it is needed in both modes. Both veracrypt and bitlocker support XTS mode.


algorithmic scheme to compare these two number encrypted using paillier cryptosystem

I am currently stuck at understanding how to code a comparision scheme
  for any two encrypted values

This is to be expected as what you are trying to do is impossible with standard Paillier encryption. To see this, first note that Paillier encryption is IND-CPA. We are now going to construct an attacker that wins the IND-CPA game with probability $1$ assuming they can relieably check for equality of two encrypted messages and thus proves that a scheme supporting this cannot be IND-CPA and thus Paillier can't actually allow for this.

Let $=_p:\mathcal C\times \mathcal C\to\mathbb B$ be a predicate that returns true for a given pair $(c_1,c_2)$ iff $D(c_1)=D(c_2)$ that is if the decryptions of the given ciphertexts are equal. This predicate models the functionality you are trying to realize. Now let's start with the IND-CPA game:

We pick two arbitrary distinct messages $m_0,m_1$ of the same length (the exact values don't matter) and send them to the challenger.
We receive $c_b=E(m_b)$ with $b$ being randomly chosen by the challenger. We compute $c_0'=E(m_0)$ on our own using the public key.
If $c_b=_pc_0'$ we return $b=0$, else we return $b=1$.

As $c_b=_pc_0'$ if and only if $b=0$ due to the construction of $c_0'$ and the way $=_p$ works, we always win the game with probability $1$ which yields the "advantage" $0.5$ which is clearly non-negligble and thus breaks IND-CPA security.


Known plaintext attack without knowing the location of the plaintext

As you're aware your crypt/decrypt function works because  A $\bigoplus$  B $\bigoplus$  B = A. So for:

P = plaintext
K = Key
C = ciphertext = (P $\bigoplus$ K)

You can retrieve your plaintext as C $\bigoplus$  K == (P $\bigoplus$  K) $\bigoplus$  K = P.

You also know that C $\bigoplus$  P == (P $\bigoplus$  K) $\bigoplus$  P == K, i.e. you can retrieve the key if you know the plaintext.

Basic stuff, you already knew this.

You've asked "how would I attempt to get the key" if I only know a piece of the plaintext? In that case you cannot retrieve the key directly. However, you can narrow the search space for K considerably.

Consider the case where you know the plaintext less 1 character and, for the sake of simplicity, lets assume lower case alphabet characters only in the plaintext.

In that case, there are two positions that your known plaintext fragment can be in, in the original message, at the beginning or at the end. There are 26 possible plaintext solutions with the plaintext fragment at the beginning and 26 with it at the end, so there are 52 possible plaintext solutions. If you xor all those solutions with your ciphertext, one of the 52 results will be your key.

Knowing that you have "the key" is helped by having lots of ciphertext (like in the case where Mallory has stolen your million-record encrypted database). Identifying the key involves testing the 52 candidates against the million stolen records and seeing which candidate keys create the most plausible plaintexts (e.g. if the original plaintext is known to be English words, finding the key that generates the most of those)

Each fewer character that you know in the plaintext fragment (greatly) increases the search space. In the case where you know a plaintext fragment less two characters then there are three positions that the fragment could occupy and, for each of those positions there are $26^2$ possible combinations (for a total of 2028 combinations).

The search space grows exponentially with the number of characters that you do not know. But the converse is, therefore, true: the search space decreases exponentially with every character that you do know. And that is why an attacker having access to plaintext and ciphertext is scary.

So, no, you cannot directly retrieve the a key knowing a piece of the plain text and, yes, you do need to search the space. However, knowing part of the plaintext, you can greatly narrow a search and combined with other factors (like knowing the structure of the plaintext or encryption algorithm) can make a search that would be intractable either money or time-wise into something that an attacker can afford.

This is just a simple example, more complex ciphers are less straightforward to attack but, the concept is similar; each piece of knowledge (plaintext structure, key structure, algorithm) reduces the search space.


Parameters for elliptic curve prime192v3

You need to look at the constructors and see which values correspond to which parameters.

The ECCurveFp reference is here

Note that $P$ is given in decimal

$P = \texttt{6277101735386680763835789423207666416083908700390324961279}$

$a = \texttt{fffffffffffffffffffffffffffffffefffffffffffffffc}$

$b = \texttt{22123dc2395a05caa7423daeccc94760a7d462256bd56916}$

The X9ECParameters reference is here

Note that $G$ is in compressed form

$G = \texttt{027d29778100c65a1da1783716588dce2b8b4aee8e228f1896}$

$n = \texttt{ffffffffffffffffffffffff7a62d031c83f4294f640ec13}$

$h = \texttt{1}$

$seed = \texttt{c469684435deb378c4b65ca9591e2a5763059a2e}$


Why are there $q^2$ keys for each equivalence class in Pedersen-van Heyst Signature Scheme?

I did not know the scheme, so I had to google it to find the missing part of its description - here it is, in case someone else wants it.

So, two keys are in the same equivalence class when they have the same $\gamma_1$ and $\gamma_2$, id est, when $\alpha^{a_1}\beta^{a_2} = \alpha^{a'_1}\beta^{a'_2} \bmod p$, and $\alpha^{b_1}\beta^{b_2} = \alpha^{b'_1}\beta^{b'_2} \bmod p$, with $p = 2q+1$. Note that the exponents of $\alpha$ "live" in a cyclic group of order $q$ (as I do not know how familiar you are with cyclic groups, I assume this statement is clear for the moment, don't hesitate to ask if it is not the case). If we denote by $s$ the discrete logarithm of $\beta$ in base $\alpha$ modulo $p$, we can rewrite the "same $\gamma_1$ and $\gamma_2$" condition as follows:

$a_1+ sa_2 = a'_1 + sa'_2 \bmod q$ and $b_1+ sb_2 = b'_1 + sb'_2 \bmod q$

Now it should become more clear to you: we have exactly two equations modulo $q$, and four variables ($s$ is uniquely determined by $\beta$ given $\alpha$), hence exactly $q^2$ solutions. Does that make sense to you ?

EDIT: regarding your last question, $\gamma_1$ and $\gamma_2$ are group elements, they are in the group of order $p$. Only the exponents (which correspond to the secret key, $\gamma_1$ and $\gamma_2$ being the public key) are elements of $\mathbb{Z}_q$.


Prove the branch of number of Advanced Encryption Standard

The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument.

We have two definitions for MDS (Maximum Distance Separable) Matrix:

First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular.

Second definition: A matrix $M_{n\times n}$ is MDS if and only if

$$
Y_{n\times 1}=M_{n \times n}\, X_{n \times 1} \Longrightarrow \mathop{\rm min}_{X\neq 0}(W(Y)+W(X))=n+1
$$

where $X={[x_0,x_1,\cdots , x_{n-1}]}^T$ and $Y={[y_0,y_1,\cdots , y_{n-1}]}^T$ are vectors  in an arbitrary
 field and $W(X)$ is the number of non-zero elements of $X$.

Now, suppose that we use a MDS matrix( by first definition) of order $4$ and
we want to proof by second definition that it's branch number is 5. Consider our MDS matrix be as follows

$$
 M=\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
$$
the entries $m_{i,j}$ are non-zero because $M$ by first definition is MDS. Now consider the following equation
$$
MX=Y \Longrightarrow
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 where $x_i$'s and $y_i$'s are elements of finite field. By second definition $X$ should be non-zero. For simplicity, consider $x_1\neq0$ and other $x_i$ can be zero or non-zero.

We should consider some cases to show that for every selection of $x_2$, $x_3$ and $x_4$, at least four elements of $x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are non-zero.

The first case is $x_2=x_3=x_4=0$. in this case we have:

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\0
\\ 0\\ 0\end {array}
 \right]=
 \left[ \begin {array}{c} x_1\,m_{1,1}\\ x_1\,m_{2,1}
\\ x_1\,m_{3,1}\\ x_1\,m_{4,1}\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ y_{{3}}\\ y_{{4}}\end {array}
 \right]
$$
 because $m_{i,j}$'s and $x_1$ are nonzero then the elements $y_1,y_2,y_3,y_4$ are nonzero. The next case is that are there non-zero
 values for $x_2,x_3,x_4$ such that

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
 \left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
due to the $M$ matrix is non-singular we can conclude that
$$
 \left[ \begin {array}{c} x_{{1}}\\x_{{2}}
\\ x_{{3}}\\ x_{{4}}\end {array}
 \right]=
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]^{-1}\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]=\left[ \begin {array}{c} 0\\ 0
\\ 0\\ 0\end {array}
 \right]
$$
and it contradict to our assumption that $x_1,x_2,x_3,x_4\neq 0$ and so one of the $y_1,y_2,y_3,y_4$ should be non-zero.

The next case is that: are there for example $x_1\neq0, x_2\neq0 ,x_3=x_4=0$ that result
 $y_1\neq0, y_2\neq0 ,y_3=y_4=0$. Consider there was this case as follows

$$
\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}}
\\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}}
\\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}}
\\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}}
\end {array} \right]
 \left[ \begin {array}{c} x_{{1}}\\x_2
\\ 0\\ 0\end {array}
 \right]=
\left[ \begin {array}{c} y_{{1}}\\ y_{{2}}
\\ 0\\ 0\end {array}
 \right]
$$
so we have
$$
 \left[ \begin {array}{cc} m_{{3,1}}&m_{{3,2}}\\ m_{
{4,1}}&m_{{4,2}}\end {array} \right]  \left[ \begin {array}{c} x_{{1}}\\ x_{{2}}
\end {array} \right]=
\left[ \begin {array}{c} 0\\ 0\end {array} \right]
$$
from the first definition all sub-matrix of $M$ has non-zero determinant and hence we can conclude from the above equation that the values of $x_1=x_2=0$ and it contradict to our assumption.

The other cases are similar to mentioned cases and use from this fact that all sub-matrix of $M$ have non-zero determinant.

I hope you find it useful.


would this be classed as a cipher text attack?

Neither, as you've described the prerequisites or - in a theoretical model - the setting for an attack to take place, but not the attack itself.

What you seem to have is a ciphertext oracle which can be used within a Chosen Plaintext Attack (CPA). As you can "enter any plaintext" I presume you can investigate the results and the request encryption of another plaintext from the oracle. If you can use this to attack the cipher then it is known as an Adaptive Plaintext Attack.

If the cipher resists such attacks and the ciphertext doesn't give you any information about the key (or any other unkonwn plaintext) then the cipher is IND-CPA2 secure.