Byte size of Diffie-Hellman public values

$A$ and $B$ have values between 1 and $P-1$, and can in fact take on half the values in that range.  As $P$ is 256 bytes long, so will $A$ and $B$.  As there are approximately $2^{2047} > 256^{255}$ potential values that they can take on, we can't express them in 255 bytes.


Generate Elliptic Curve Private Key from User Passphrase?

Using PBKDF2/Bcrypt/Scrypt might be the least-bad way, but that doesn't mean it's a good way.  If your passphrase is puppies, it doesn't matter whether you use PBKDF2, Bcrypt, or Scrypt: you've got serious problems.  If someone tries to crack your key, you're going to be toast: your key will be cracked within minutes.

Bottom line: this sounds like a bad idea to me, if there's any possibility at all that the passphrase might be weak (which, in practice, there will be).
I would not use this to protect my money.

Instead, you should be generating a truly random or cryptographically-strong random number for the private key, then storing the private key somewhere safe.  If you want to store the private key in encrypted form, you can derive a symmetric encryption key $K$ from a passphrase and store the private key encrypted under $K$ (though please understand that this will likely be vulnerable if someone manages to steal a copy of the encrypted private key).


Can a PRNG be made into a CSPRNG by hashing the outputs?

No, the question's construction is not guaranteed to turn a PRNG into a CSPRNG. In some cases, the hashing worsens the generator. In more, undesirable characteristics remain detectable after hashing. There are better methods to build a CSPRNG from a hash.

The question's construction, hereafter WBCSPRNG for Would-Be Cryptographicaly Secure Pseudo RNG, is a PRNG with the same input characteristics and state size (within a few bits depending on how that's counted) as the original PRNG. It has a period demonstrably not smaller than the PRNG by a large factor (at worse 1024/256=4) under the hypothesis that the hash behaves as a random oracle. I do not see anything else comforting that can be said unless we add some hypothesis about the PRNG.

In particular, we can devise a PRNG, with a large state and long period, such that the WBCSPRNG fails most existing PRNG test suites, when the original PRNG consistently passes them. Start from a good CSPRNG, and modify it so that after having output 1023 bits, the next bit is produced by hashing these and a zero bit, summing the 256 bits yielding $b\in[0,256]$, outputting zero if $b<128$, one if $b>128$, and the low-order bit of the hash otherwise.

Our constructed PRNG is no longer a CSPRNG, but still pass any pre-existing RNG test (no pre-existing RNG test will catch how the extra bit is generated). Yet the WBCSPRNG is biased towards zero, and most RNG test suites will detect that.

The above counterexample is maliciously constructed, and in a way that  needs to know the hash, which we could forbid. That's not good enough: a whole class of accidental defects are amplified. For example, if a PRNG has the undesirable characteristic that the first 1024-bit block of each 242-bit output block is identical, the WBCSPRNG has the characteristic that the first 256-bit block of each 240-bit output block is identical, which is likely to cause issue sooner.

The hypothesis when academically evaluating the security of a CSPRNG is that its design is public, here including the WCSPRNG's hash step and the PRNG. If the PRNG has the characteristic that a class of 1024-bit blocks are likely to appear in its output, that again can be detectable in the WCSPRNG output, after testing 4 times less bits.

The method has no practical interest as a way to construct a CSPRNG, for we do not need a PRNG to make a CSPRNG out of a hash such as SHA-512/256, and one more efficient than the question's one: we hash the seed input, set a counter to that, then to produce 256 bits of output we hash the state then increment it.


Can anyone elaborate why KP-ABE is better than CP-ABE for television program broadcasting?

Let's say if we want to encrypt a cartoon musical movie, and it can be watched by children users:

In KP-ABE, we can encrypt the movie with attribute cartoon and musical, and then generate a secret key with attribute structure cartoon AND musical for children users.

In CP-ABE, we have to think in the way that only users attributed with cartoon AND musical can decrypt, and then generate the secret key with attribute cartoon and musical for children users.

Although both encryption works, KP-ABE is more intuitive for broadcasters, because we only need to encrypt the movie with its types during production. Besides, it is also more flexible because we can add new users with personalized types without re-encrypting the video.


Is Commitment Scheme with hash function is a perfectly hiding scheme?

No, the proposed commitment scheme is not perfectly hiding. Depending on what you require from the hash function, it may not be hiding at all.

If you only require collision resistance (which would be the standard security property of a hash function) you cannot prove the construction even computationally hiding. This is because a collision resistant hash function may leak some limited information about its input. E.g., it might leak the first bit of its input which immediately breaks hiding.

However, the construction you're looking at is a folklore commitment scheme in the Random Oracle Model, where $C$ is modeled as a random oracle. In this case, the construction is computationally hiding, but it is not perfectly hiding.
The reason is the following: While you observation that, due to compression, there must exist some $m',r'$ such that $C(m,r)=C(m',r')$ this is not sufficient.

Perfect hiding would require that for any $m'$ there exists an $r'$, such that $C(m,r)=C(m',r')$. And this is generally not the case (and indeed unlikely) for a random function.


Elliptic curve as a product of 3 cyclic groups possible?

Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $\mathbb{Z}_r \times \mathbb{Z}_r$. This is probably not what you want.

For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $\mathbb{Z}_n$ is cyclic, but it is also isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_q \times \mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.

It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} \bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.

Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $\mathbb{Z}_e$ with $e$ prime and $e = 2 \bmod 3$, the curve $y^2 = x^3 + B$ (for some $B \neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 \bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $\mathbb{Z}_e$ (for constants $B \neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.

In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.


Half of any bitcoin (crypto) public key - (public key half) is possible

ECC is cryptography over an elliptic curve group.

Firstly you have an elliptic curve, e.g. Bitcoin uses a Koblitz curve secp256k1 $y^2 = x^3 + 7$.

The group is defined over curve points over a finite field $F_p$ (integer modular $p$). The group elements are points on the curve. A point in the affine form consists of two coordinates $P =(x,y)$ where $x,y\in F_p$.

For group elements, you can do point addition $P+Q$, as well as scalar multiplication $sP$, where $s$ is an integer in $Z_n$ where $n$ is the order of the group (how many elements in the group).

A public key in bitcoin is a point $P$. To do $\frac{P}{2}$, you multiply $\frac{1}{2}$ to $P$ where $\frac{1}{2} $ is the multiplicative inverse of $2$ in $Z_n$. It is an integer that can be found using the extended Euclidean algorithm and is 57896044618658097711785492504343953926418782139537452191302581570759080747169 in the case of secp256k1.


Trying to udnerstand textbook sample solution

You are correct; your "proof" is invalid; even if you show that $d$ is the correct value modulo $e$, that doesn't immediately imply that it is the correct value.  If you replace $d$ with $d+e$, that is also is correct modulo $e$, but is also obviously wrong (it is even).

Instead, here is a better line of reasoning:

Two integers $d, e$ work as the private, public exponents modulo a product of two primes $pq$ iff both the following hold:

$$de \equiv 1 \pmod{p-1}$$
$$de \equiv 1 \pmod{q-1}$$

What you need to show is:

That $d$ as specified in the above formula is actually an integer; that is, that $(p-1)(q-1)(e-1)+1$ is a multiple of $e$
That $de \equiv 1 \pmod{p-1}$
That $de \equiv 1 \pmod{q-1}$

None of these three should be difficult to prove.


Is there some recommended way to parse a PEM X.509 certificate?

Well, this site is not for software recommendations (Software Recommendations is, who would have thought), but if the certificate is well-behaved it is possible to generate code for the ASN.1 constructs. You need a parser/generator for ASN.1.

  Any third party product I can use? Is it complicated to write such parser on my own?

There are various ASN.1 and X.509 libraries online. Is it hard to write on your own? Yes, expect a low minimum of 3 months work to write something pretty OK, if you already understand ASN.1 / DER.

  Where is the structure described?

ASN.1 and DER are described in the ISO/IEC 8824 and 8825-1 specifications respectively. X.509 certificates and CRLs are described in RFC 5280. The appendix of the RFC contains the ASN.1 module.

  My biggest concern is about writing a good ANS1 parser together with a base64 decoder on my ow, but maybe it is not that complicated as I expect from now.

Creating a base 64 decoder is absolutely peanuts compared to the parsing of ASN.1 structures. You may however get away with just DER encoding and looking up paths within the certificates (if you want to live dangerously). You may run into some trouble when converting between implicit and explicit input for the signature algorithm, just to name one issue with the ASN.1 structures.

Note that ASN.1 BER/DER codecs are very vulnerable against stack overflow attacks (especially in non-managed languages like C of course), and that the decoding of the certificate comes before authentication.


Is this PRG secure? Different on halves of input

The PRG $H$ is still secure, and your intuition is right: $x_\text{Left} = x_\text{Right}$ happens with a very small probability, so this shouldn't be a problem.

The way to formally prove this would be as follows. Consider a distinguisher $\mathcal{D}$ and the experiment in which a random $x\in\{0,1\}^n$ is chosen and $G(x)$ is given to $\mathcal{D}$, we want to see that the probability that $\mathcal{D}$ outputs 1 in this case is very close to the possibility that $\mathcal{D}$ outputs 1 when we feed it with a truly random string $r\in \{0,1\}^{2n}$. Let $\text{eq}$ denote the event in which $x_\text{Left} = x_\text{Right}$ (where $x$ is the uniform seed of the experiment), then we know that

\begin{multline}
\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] \\ = \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}]\operatorname{Pr}[\text{eq}] + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c]\operatorname{Pr}[\text{eq}^c] \\ = (\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}] - \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c])\operatorname{Pr}[\text{eq}]\\ + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c]
\end{multline}

So

\begin{multline}
|\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]| \\ \leq \operatorname{Pr}[\text{eq}] + |\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]|
\end{multline}

The first term is negligible as you mentioned, and the second is because of the assumption that $G$ is a PRG, since whenever $\text{eq}$ does not occur, the experiment is the same as the experiment for $G$.


Does it make sense that a hash is separated by hyphens

That's a UUID format. Note that this is a representation of a 128 bit string. Just like "9" is a representation of "1001".
The actual output of the hash is a random looking 128-bit string.
If it is a UUID, it can be different hash functions depending on what version it is.


Is it safe to use XOR to encrypt data key using master key

XORing a master key (presumably a long term key) with data is a very dangerous idea. If any data key is leaked, then the master key may be easily calculated, thus leaking all keys. ($m$ for the master key, $d_x$ for all data keys)
$$c_x = d_x \oplus m$$
then somehow $d_4$ is leaked
$$m = d_4 \oplus c_4$$
$$d_x = c_x \oplus m$$
You'd be better off applying a block cipher (like AES) instead. One of the main properties of block ciphers is that given the plaintext and ciphertext, it is infeasible to generate the key.
$$c_x = E_m(d_x)$$
then again $d_4$ is leaked (who keeps doing that..) yet $m$ is still hidden.


Floyd's cycle finding algorithm on SHA256

We usually use raw bytes, because this doesn't require extra step (convert hex to string). But technically speaking any representation will allow you to find a cycle (just a different one).

When talking about shortened-hash cycles, same rules apply: we usually use raw bytes just cut to desired length or we fill rest of hash with zeros, because that requires least steps to complete. But you can use anything that will cut entropy to desired value.


Verification of data on an untrusted remote storage server

Proof of Data Possession (PDP) is a challenge-response protocol enabling a user (for example in the cloud network) to check whether a data file stored on a remote server is available in its original form or not. Data integrity is an important factor in almost any data and computation related context. It is not only one of the qualities of service, but also an important part of data security and privacy.

In PDP, data owners have a limited storage to store all messages so process their sensitive data to generate verifiable authenticators which are outsourced along with the data to the server (cloud). Although the servers promise a reliable environment to the users, the integrity of data is a subject to scepticism, as an untrusted cloud can easily be lost or corrupted, due to the existence of hardware and software failures or human errors.

In this point, data owners can download the entire message and check whether it is stored without any corruption or not. But it is not acceptable for users who have a limited capacity so PDP schemes provide a solution for data owners to check the cloud's claim for data storing.

There are different concepts for PDP schemes but share PDP amongst some servers is a good scenario for your question such as LINK.

On the purpose of reducing the hardness in the data owner side, Third Party Auditor is considered. When the data owner wants to upload the data on the server, calculates the tag corresponding to the message which has less size than the original message (Hash of message) and stores it. When he/ she plans to check the integrity of the message provide a challenge and get a response corresponding to the stored message from the server. Each PDP scheme should satisfy these properties:

•   Completeness: A valid proof generated by the server based on the protocol, should convince the TPA during the auditing process.

•   Soundness:  This property guarantees that for every untrusted cloud server, it is computationally impossible to generate an invalid proof that can pass the verification under the proposed scheme.

•   Perfect data privacy: The TPA is only trusted to check data integrity on behalf of users and should not learn any information about the data content. Perfect data privacy guarantees that nothing but the correctness of the proof is revealed to the TPA during protocol execution.


Does this describe an invalid key share attack?

Can you please correct me if I am wrong?

What you have is essentially correct; however it can be generalized a bit.
In real systems that use DH, the honest system will take the shared secret and do something with it; commonly putting it (and some public information that the attacker knows) through a KDF, and then using the keys generated by that KDF to either encrypt or decrypt a message.  TLS would be an example of this.
What this means is that the attacker can verify a guess to the shared secret (by sending that guess through the KDF, and then seeing if the keys generated will decrypt the message from the honest system, or using the keys to encrypt a message that is sent to the honest system (and seeing if the honest system acted as if he could decrypt the message)
Here is how the attacker can exploit that to find $x \bmod t$ (where $t$ is a small factor of $(p-1)/q$); he finds a value $j$ that is of order $t$, he picks a random $y$ and sends as his key share the value $j \cdot g^y$.  The honest system will compute $(j \cdot g^y)^x = j^{x \bmod t} \cdot g^{xy}$.  The attacker knows the value $g^{xy}$; this gives him a way to test various values of $x \bmod t$.

Of course, it can be easily thwarted by having the oracle check whether or not the query is indeed a quadratic residue modulo $p$.

Or more generally making sure that $y^q = 1$.  However, that is expensive; other possible defenses are:

Simply never reusing a private value; this means that an attacker can learn some information about the value $x$ we used with an exchange with him - however, we wouldn't care if he could retrieve the entire $x$ value, as we allow him to learn the shared secret, and that's the only thing that $x$ would give him.

Use a slightly larger value of $x$; for safe primes, $h=2$, which means that the attacker can learn the lsbit of $x$ and nothing else.  Hence, if we select our $x$ value from a range 1 bit larger than we would have otherwise, then we have kept the discrete log problem just as hard (even if he learns that lsbit)


The secondary data or metadata are stored in plaintext.

Should you receive an encrypted mail by pgp, you will notice that you have 2 files attached: noname.pgp and encrypted.asc. Thus the content of the message is hidden but not the metadata.

Why don't we also encrypt the metadata? Well how would we know who to give the mail to then? If you give your mailman a letter and don't tell him who the receiver is, how do you expect him to give it to the right person?

By the same principle, your receiver should be able to at least know what the message is about. Should you not want anyone to know, you could also leave the field blank.

Hence no, only the content is encrypted the meta data are still in clear text.


Why HAIFA and sponge constructions are not prone to length extension attacks?

Sponge Construction
In sponge construction, the block size $b$ has two parts, $r$ is the rate and it is the written part and $c$ capacity is the untouched part by the input/output, $b= c+r$

The output is taken from $r$ in the squeezing stage. Therefore not all of the $b$ is the output. This prevents the length extension attack like in the truncations of SHA2, which are standardized after Keccak.
The idea is: when someone wants to extend a message $abc$ into $abcde$ they should be able to continue the hash output where it is left, the hash value. $h=H(IV,\text{"abc"})$ then using the $h$ as the IV for the $H' = H(h,\text{"df"})$ then the length extension is possible (here we did not consider the padding and not a big issue, either). Originally the length extension attack worked on MAC with $H(\text{secret}\mathbin\|\text{message})$ construction. Although the output will be different, the attacker can inject this with the new MAC tag, without the knowledge of the key, and the server will accept it. So. it works even the attacker cannot have the secret and the message. It doesn't work with HMAC, which is designed to be secure against this. On the other hand, KMAC based on SHA3 has much simpler design since SHA3's immunity.
The sponge constructions' two-stage design, that is absorbing and squeezing together with the $c$ prevents the length extension attack with a calculatable countermeasure.
Below is the capacity against the length extension attack of SHA-3.
\begin{array}{|c|c|c|c|c|}\hline
\operatorname{SHA3}\text{ variant}\  & \text{output size} & \text{internal block size} & \text{rate } r& \text{Capacity against LEA} \\ \hline
\operatorname{SHA3-224} & 224 & 1600 & 1152 & 448= 1600-1152\\ \hline
\operatorname{SHA3-256} & 256 & 1600 & 1088 & 512 = 1600-1088 \\ \hline
\operatorname{SHA3-384} & 384 & 1600 & 832 & 768 =1600-832\\ \hline
\operatorname{SHA3-512} & 512 & 1600 & 576 & 1024 = 1600-576\\ \hline
\end{array} LEA stands for Length Extension Attack.
HAIFA construction
The HAIFA construction is not mentioned about countermeasure about length extension, however, it can be designed/modified simply using a different salt in the last block as in BLAKE2 Is Blake2b vulnerable to length extension attacks?, like using $true$ for the last block and using $false$ for any other block. The HAIFA construction is simple as;
$$C:\{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s  \to \{0,1\}^{m_c}$$ or
$$h_i = C(h_{i-1}, M_i, \#bits, salt)$$ $\#bits$ is the number of bits hashed, $h_0 = IV$, and $salt$ is the usual salt value.


The question is actually about Simplified DES (rather than Simple DES as stated), which is an extremely simplified mock-up of Single DES.

From reading the definition of S-DES in the reference used in the question, we get that:

  The S-boxes operate as follows. The first and fourth input bits are treated as a 2-bit number that specify a row of the S-box, and the second and third input bits specify a column of the Sbox. The entry in that row and column, in base 2, is the 2-bit output.

Now let $a b c d$ be the input bits, $q r$ the output bits, use big-endian convention, and reformat that table as:

abcd qr     abcd qr    abcd qr    abcd qr
0000 01     0010 00    0100 11    0110 10
0001 11     0011 10    0101 01    0111 00
1000 00     1010 10    1100 01    1110 11
1001 11     1011 01    1101 11    1111 10

In order to verify the equations $q=abcd\oplus ab\oplus ac\oplus b\oplus d$ and $r=abcd\oplus abd\oplus ab\oplus ac\oplus ad\oplus a\oplus c\oplus 1$, just compute what $q$ and $r$ they give for each of the $2^4$ combinations of input, and compare that to the reformatted table; this is left as an exercise to the reader.

There is no systematic practical method to derive the most compact equation for a sizable bit table, and in the case of DES S-boxes this has been the subject of intense research. One systematic method leading to the most compact representation of an arbitrary boolean function as OR-of-AND-terms is known as Karnaugh map, but here the equations are wanted as XOR-of-AND-terms, and I know no analogous method. With 4 entries, finding the shortest equation (by some metric) that match would be tractable by brute force with a computer.

Still, here is how one of the equation could have been derived by hand. First we rewrite the table with the arguments in Gray order

a | 0000000011111111
b | 0000111111110000
c | 0011110000111100
d | 0110011001100110
--|-----------------
q | 0110100101111010
r | 1100110001011110

By comparing the line for $d$ with the line for $q$, it is striking that a bit flip of $d$ cause a flip in $q$, except when $a=b=c=1$; in other words, $q'=q\oplus d\oplus abcd$ is independent of $d$. We have reduced the problem to finding an equation for $q'$, with table

a | 00001111
b | 00111100
c | 01100110
--|---------
q'| 00110110

and some trial and error is enough to find $q'=ab\oplus ac\oplus b$, from which $q=abcd\oplus ab\oplus ac\oplus b\oplus d$ follows.


How do I communicate the value of the initialization vector to the end user? Should it be part of the encrypted message?

For CBC encryption, you would store the initialization vector as the beginning of

the ciphertext, regardless of whether you read in an IV or generated it yourself.

The CBC decryption algorithm would do what you described at the end of your post.

Your implementation should also offer access to the block cipher itself, without any mode of operation.


Shamir Secret sharing - Can share generator keep x values secret?

Each share in Shamir-type secret-sharing schemes has two parts: the share value
$f(x_i)$ which is the value taken on by a certain polynomial $f(\cdot)$, and the share "location" $x_i$. The "dealer" who constructs the shares and hands them
out to individual shareholders is assumed to have handed out $(x_i, f(x_i))$
to the $i$-th share holder. In this scenario, any $k$ (or more) shareholders in a
$(k,n)$ scheme can get together and reconstruct the secret, and fewer than $k$
shareholders cannot reconstruct the secret.

If the dealer
hands out only $f(x_i)$ to the $i$-th share holder and merely makes a note
in his records that the $i$-th share holder's share location is $x_i$,
then only the dealer can reconstruct the secret when $k$ or more shareholders
make an application to the dealer; the $k$ shareholders cannot
reconstruct the secret by
themselves because while they all know their share values, they do not know the
location of those shares.  This scheme is, of course, fraught with danger in
case the dealer's list is lost or is corrupted in various ways: the secret
might be irretrievably lost.

See also this answer for
how enemies can attack a Shamir-type secret sharing scheme by tampering
with share values and by tampering with share locations, and how to
get around such problems.


While generating a random Elliptic curve what are the conditions i have to considerd?

Baring other requirements that you did not explain:

An elliptic curve can be written as $y^2=x^3+ax+b$. To generate a random curve over a prime field, choose $a,b$ at random from the prime field.


How and why can a decryption program tell me that a key is incorrect?

It's not a security problem but a necessary feature. It's not an exact science to distinguish a "good decryption" from a "bad decryption". What if the user had encrypted random data? you would not be able to figure out if the key is correct or not from that sole information, since in both cases the decrypted output would look completely random!

Similarly, what if the user typed his key wrong? You want to be able to inform him he made a typo ("invalid password") instead of blindly decrypting garbage and waiting for the user to realize he typed it wrong and try again.

What most programs do is store the hash of the key (or an HMAC of the encrypted file, using the encryption key) so that they can verify if the key is correct (or if the file is corrupt - you get free integrity/authentication with the HMAC method) without disclosing the key at all. An attacker would need to find an exact preimage to obtain the actual encryption key, which is designed to be infeasible.

In essence, you use a one-way function to store the key's image somewhere in the file, so that anyone without the key cannot invert the function and retrieve the key, but anyone who has the key can easily feed it into the one-way function and compare the result with the value that's in the file. If it matches, it's the correct key! (with very high probability)


MD5 processes a message into a fixed-length output of 128 bits, typically represented as a sequence of 32 hexadecimal digits.

This process is not random, but it’s a so called „pseudo-random“-process (A pseudo-random process is a process that appears to be random but is not 100% random).

There is actually no proof that every hash-value of the MD5-process is reachable for some input, but it is expected to be true.

So MD5 can hash every input to an „arbitrary“ hash-value of 128 bits, bits can be 1 or 0, so $2^{128}$ possible outputs.


Protocol for Randomized Oblivious Transfer?

No, as written, your protocol doesn't work -- the problem is that Bob is supposed to be allowed to choose $b$, your protocol selects a random one for him.

However, it is close -- here is a modification that I believe does work:

First, suppose Alice has her values $(x_0, x_1)$, and Bob has his bit $b$.

They run their Random functionality R, and so Alice gets the values $(z_0, z_1)$, and Bob gets the values $(c, z_c)$.

Now, Bob sends the Alice the bit $e$ defined as $e = b \oplus c$; Alice sends back a pair of values $(y_0, y_1)$ defined as $(y_0, y_1) = (x_0 \oplus z_e, x_1 \oplus z_{1 \oplus e})$.

Bob then computes $z_c \oplus y_b = x_b$.

I claim that Alice gets no information about the value of $b$, and that Bob gets no information about the value of $(x_{1 \oplus b})$, and thus this is a valid Oblivious Transfer function.


Multiparty Computation to calculate addition of shares without revealling individual shares

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their individual secrets.

A simple application of arithmetic secret-sharing based secure multi-party computation ("arithmetic GMW") can do that.
The protocol for that goes as follows:

(One-Time Setup) Pick a prime $p$ that is guaranteed to be larger than the sum of all input values (you can safely overshoot the sume by a large margin here, e.g. pick a prime larger than $2^{96}$ for 64-bit inputs). This prime will be used to define the finite field we will work in. If you already have a preferred one, use it here. All arithmetic that follows will be carried out in this field.
Have every party $P_i$ choose $n-1$ random integers uniformly at random from the finite field. Call them $s_{i,j}$ and let $s_{i,n}=x_i-\sum_{j=1}^{n-1}s_{i,j}$. This creates an arithmetic $n$-out-of-$n$ sharing of $x_i$
Have every party $P_i$ send $s_{i,j}$ to $P_{j}$.
Have every party $P_i$ compute $r_i=\sum_{\ell=1}^{n}s_{\ell,i}$, that is, have them all sum up all the shares they receive.
Have every party $P_i$ broadcast their result $r_i$ to all other parties (or only to the one needing to know the sum).
Have every party with with all $r_j$ compute $\sigma=\sum_{j=1}^{n}r_j$. This value is the desired sum.


Lattice Crypto worst case to average case

You are right.  A worst-case to average-case reduction from problem P to a distribution D over instances of problem Q would mean roughly that $$\Pr_{q\leftarrow D(Q)}[q\text{ is hard} ~|~ \exists~\text{any instance of P that is hard}]>1-\text{negligible}.$$ So even if the support of distribution D is the entire set of instances of problem Q, this does not of course imply that every instance of problem Q is hard.

As an aside, it should be pointed out that the way in which parameters are set for lattice problems does not result in a particularly meaningful worst-case to average-case reduction because the reduction is not tight -- the dimension of the lattices in problem P is smaller than in problem Q.

Still, the big utility of having had such a reduction was that it was this reduction that led people to the problems of (Ring/Module)-SIS and (Ring/Module)-LWE and distributions over these problem instances (uniform) that are currently used in practical lattice cryptography.  Analyzing the hardness of random instances of these problems became an independent matter.


What papers describe the rationale behind cryptography algorithms

First, I understand your question and the frustration that comes along with it, and it is not uncommon. I will warn you that from my perspective, there isn't really an easy answer that provides quick satisfaction. But let me try to point you in the right direction.
For a simple beginning path, I will point you to Jean-Philippe Aumasson's book, "Serious Cryptography" in Chapter 6 page 111 there is a section on "Building Hash Functions" but also notice that the section BEFORE this one talks about the characteristics of hash functions. If you read the "Building Hash Functions" section you won't really get the answer I think you are looking for asking (i.e. Why these constants?), however you will get some clues to constructions.
Looking into the characteristics of what hash functions need to provide (i.e pre-image resistance, 2nd pre-image resistance, and collision resistance) you see the goal that is trying to be achieved by a hash function. Until you study attacks on these goals, and deep security proofs of the functions, you will not come close to answering the questions you are asking. They are not easy question.
Two papers I will recommend. Bellare, Kilian and Rogaway "The Security of the Cipher Block Chaining Message Authentication Code" gives a formalism for MACs, PRFs and PRPs which is essential for your deeper understanding. Also Bellare, Canetti and Krawczyk "Pseudorandom Functions Revisited: The Cascade Construction and its Concrete Security" which discusses the iterative construction used in hash functions. These will give you some of the formal basis used in constructing hash functions (IMHO). Another paper that I believe is absolutely fundamental for going to this deeper level in cryptography is Bellare, Desai, Jokipii and Rogaway "A concrete security treatment of symmetric encryption"
Once you really consume these papers, and you get a handle on the simulation games used to prove security, and the attacks that you need to present, certain things will become more transparent. In addition, you will be able to read some proofs and attacks on algorithms with more clarity.
I would then recommend some reading on the Random Oracle Model, which is often used in proofs that use hash functions, and then look at papers around the SHA3 competition. I think it is really illuminating to read papers on SHA3 and thesis on hash functions - I will recommend one though I won't make any claim that it is the best (Ozgul Kucuk "Design and Analysis of Cryptographic Hash Functions" 2012).
These references should start you in your journey to acquire the knowledge you want so you can answer the questions you posed. I hope you find this direction useful.


Cipher feedback mode with shift registrers

To address the last bit first: CFB and AES aren't really the same thing. AES is a block encryption algorithm (encrypts a single block of data, 128-bits in the case of AES). CFB is a mode of operation, which defines how multiple blocks are encrypted, and is agnostic to the algorithm. CFB is used the same way no matter what the "Encrypt" function in the middle is.

For your first question.. I'll start by saying that I have no idea what's going on in the second photo; between the hand writing and abbreviated notations, not to mention the literal hand, I can't follow it.

But the first one is much clearer.

For each block...

Either the IV or previous ciphertext is encrypted using the AES algorithm (or whatever algorithm is being used) to produce what's effectively a key stream (like a stream encryption algorithm)
The current block of plaintext is XOR'd with the key stream to produce the ciphertext

It's basically using a block encryption algorithm (AES) as a stream encryption algorithm.

The cool thing about this is that (with the key) you can easily decrypt arbitrary data from the middle of the stream - all you need is the ciphertext of the previous block (or the IV), which you encrypt and XOR with whatever you're decrypting. But you can't encrypt new data in the middle - changing a block changes the entire rest of the cipher. So it's optimized for encrypting in-order and decrypting in any order.

Typical attacks against stream ciphers may also work; for example, you don't get any real integrity protection. Somebody can XOR a byte from the block to change it to something they control (although I suspect this can only be done in the final block, otherwise it's going to change the remainder of the ciphertext).

But yeah, I think the first diagram is pretty straight forward. No clue what the second is talking about..


How are subkeys, in Feistel block ciphers, derived for each round?

I know that all the subkeys $k_i$ are derived from the main key $K$, but how?

However the cipher designer feel like.  The Feistel design gives guidance as to how the block is processed (and in a way to make inverting the cipher easy), however it gives no guidance as to actually generate the subkeys.  The designers can do anything they like, and still call themselves a "Feistel Network".

  It is specified in the exercise that the Feistel cipher uses 8-bit independent round keys ki. I'm not sure if this aligns with my assumption above.

The point of that instruction is that you aren't supposed to assume any necessary relationship between different round keys.  It might be because they're from independent part of the keys; it also might be because the subkeys are generated via an noninvertable function.  How it happens is irrelevant to the exercise.


How to find out the block size of Xchacha20 in Libsodium?

TL;DR; ChaCha's block size is 64-byte i.e. 512-bit.

Xchacha20 extends the nonce of ChaCha20 without changing the function of ChaCha20. The aim of Xchacha20 is to extend the 128-bit nonce size of ChaCha20 to 192-bit in order to generate random nonces to use safely in the long-lived keys without the fear of the nonce-collision.
The RFC 7539 in Section 2.3 mentions clearly.

2.3.  The ChaCha20 Block Function
The ChaCha block function transforms a ChaCha state by running multiple quarter rounds.
The inputs to ChaCha20 are:

A 256-bit key, treated as a concatenation of eight 32-bit little-endian integers.

A 96-bit nonce, treated as a concatenation of three 32-bit little-
endian integers.

A 32-bit block count parameter, treated as a 32-bit little-endian
integer.

The output is 64 random-looking bytes.

The ChaCha, a variant of Salsa20 paper;

This paper assumes that the reader is familiar with Salsa20, and focuses on the changes from Salsa20 to ChaCha

on the intro

The Salsa20/20 stream cipher expands a 256-bit key into $2^{64}$ randomly accessible streams, each containing $2^{64}$ randomly accessible $64$-byte blocks.

And the The Salsa20 family of stream ciphers paper wrote it more clearly;

Salsa20 generates the stream in 64-byte (512-bit) blocks

Some words on this

I heard that Xchacha20 works like a block cipher

Salsa and ChaCha are stream ciphers both build on Pseudo-Random Function (PRF).
A PRF defined over $(K,X,Y)$:
$$F: K \times X \mapsto Y$$ such that exists efficient algorithm to evaluate $F(k,x)$
They use CTR mode to turn a PRF into a stream cipher. CTR mode is designed for PRF by Whitfield Diffie and Martin Hellman in 1979;

Privacy and Authentication: An Introduction to Cryptography

In contrast, a block cipher is a family of permutations and is expected to be a Pseudo-Random Permutation (PRP). A PRP defined over $(K,X)$:
$$E: K \times X \mapsto X$$
such that:

There exists efficient algorithm to evaluate $E(k,x)$
The function $E( k, \cdot )$ is one-to-one ( and therefore permutation)
There exists efficient inversion algorithm $D(k,x)$

Note that a PRP is also PRF.
The CTR mode doesn't require the inverse of the function and therefore enables more range of functions to use. If we fix the output space into the same space for PRF's then there are $2^{n^{2^n}}$ PRFs and $2^n!$ PRPs from $n$-bit input space to $n$-bit output space.
If you need to use a PRP in the CTR mode then you need to be careful on the  PRF-PRF switching lemma. , Bellare et. al, 97 provide the security bounds.

A concrete Security of Treatment of Symmetric Encryption

In contrast to conventional stream cipher that output bits per clock, Salsa and ChaCha both produce long outputs per encryption by design and are still stream ciphers.


If I understood correctly, this solution could be susceptible to an attack called surreptitious forwarding?

If CryptSignAndEncryptMessage is implemented in the naive way, then it would seem that it is vulnerable to a forwarding attack. Microsoft has not published the exact details (AFAIK), so it is difficult to tell for sure.

  Does this in turn mean, if I include the receiver in the signed data, I am not susceptible to this attack?

There is a published recommendation done by a few very respectable cryptographers. It is in Section 7 of On the Security of Joint Signature and Encryption, and is along similar lines to what you propose. Specifically, they recommend:

  Whenever encrypting something, include the identity of the sender $ID_S$ together
  with the encrypted message.
  Whenever signing something, include the identity of the receiver $ID_R$ together with
  the signed message.
  On the receiving side, whenever either the identity of the sender or of the receiver
  do not match what is expected, output $\bot$.


What does universal look like? What is the complexity(size/depth) of universal circuit

The state of the art in optimizing the efficiency of universal circuits is, to my knowledge, this paper. At a high level, a universal circuit to evaluate any size-$s$ circuit has size $O(s\cdot \log s)$ I guess the depth should be roughly similar ($O(s\cdot \log s)$), since a size-$s$ circuit can have depth-$s$ in the worst case, and we do not know of generic techniques to reduce the depth of a circuit while increasing its size by only a logarithmic factor.


NO. Without changing the API, it is not possible to coerce a 40-bit-key or 128-bit-key implementation of RC4 to behave like a 256-bit-key one, because there is no way to inject any key material in the RC4 state after initialization.

Dave_Thompson_085 has an interesting comment for OpenSSL specifics.


Can data over a very low bandwidth channel still be encrypted?

If the sender and recipient can agree on the nonce of every message from existing context, so that the nonce either doesn't need to be transmitted or can be derived from metadata that must be transmitted anyway, then a stream cipher can be used to encrypt with no length expansion.

But the problem here is that you likely don't want just plain encryption, but authenticated encryption (AE), and AE algorithms generally require an authentication tag to be transmitted along with messages, which is an overhead that expands message size.

There do exist however AE algorithms that under limited circumstances could be used to encrypt and authenticate with no length expansion.  One example is the still experimental CAESAR competition candidate AEZ, which claims the following property (from the v5 spec, p. 10):

  Exploitation of domain-specific redundancy. In many contexts, plaintexts have a certain expected structure. This might arise because the message was produced by or for a particular protocol. We intend that if the user checks for the anticipated structure and regards messages as inauthentic if they don’t comply, then this check augments authenticity and correspondingly lessens the need for the nominal redundancy that is inserted by AEZ before enciphering (that is, the extra ABYTES zero bytes).

The following guideline is given for when a very low ABYTES (authentication tag length) value may be safely used (p. 13):

  Applications should not reduce ABYTES to zero or some other small value without ensuring that, combining the ABYTES zero bytes with
  any decryption-verified redundancy, there remain enough total bits $r$ of redundancy that forging each message with probability $2^{−r}$ is alright.

AEZ however is still very much at an experimental, cryptographic competition phase, so if you need a solution today you're just going to have to use a well-established AE scheme, and that will require length expansion.


ASN.1 encoding off RSASSA-PSS default parameters

Bouncy Castle is correct. Bouncy Castle contains a BER/DER encoder that changes ASN.1 objects into encoding by explicitly coding it that way - manually, as far as I understood. As this structure is represented using the distinguished encoding rules (DER) the structure should be empty. DER uses the minimum number of bytes to encode values.

DEFAULT ASN.1 values - just like XML default values in XSD schema's - should be filled in when the structures are parsed. So the HSM should automatically replace the values when parsing the data. If it doesn't contain a fully featured ASN.1 parser it may be that this needs to be coded explicitly (making this relatively vulnerable to implementation mistakes).

As I'm currently at home I'll use the venerable "A Layman's Guide to a Subset of ASN.1, BER, and DER" instead of directly quoting from the ITU-T X.690 / ISO/IEC 8825-1 specs:

  Contents octets are the same as the BER encoding, except that if the value of a component with the DEFAULT qualifier is the default value, the encoding of that component is not included in the contents octets.

Note that that quote is for the encoding of a SEQUENCE.


Proper implementation of AES-256-GCM with PHP OpenSSL

This is a question for codereview.se or a PHP forum.  As an aside: if you're building a new protocol for your own application, rather than trying to interoperate with an existing application, you will almost certainly be better served by libsodium than by OpenSSL's byzantine API.  Even if you have to use older versions of PHP that don't have it as core, you can use sodium_compat from Paragon IE.

Note that AES-GCM tends to be vulnerable to timing attacks on AES and on GCM in software implementations, and has small limits on the number of messages that can be exchanged with random nonces.  So if you're not restricted to interoperation with an existing application, it may be safer to use libsodium's crypto_secretbox_xsalsa20poly1305, or if you have associated data as well, crypto_aead_xchacha20poly1305_ietf.  I would suggest a nonce-misuse-resistant scheme, but they are not widely available yet and the world hasn't standardized on one yet.
Your obligations for using AES-GCM are: (a) The key must be uniform random from the perspective of the attacker, and (b) the nonce (here confusingly called ‘IV’) must never be reused with the same key.  In exchange, AES-GCM guarantees an active adversary can't learn anything about message content (length and timing are not concealed) or forge messages not previously seen, even if they could adaptively learn the encryption of chosen messages.  If you break your side of this contract, then AES-GCM may provide no security to you.

You can't just set the key down alongside the ciphertext, of course: then the attacker knows what the key is, and it is no longer uniform random from the attacker's perspective.  In order for this to work, the peers have to know the key ahead of time.  Maybe it's a shared secret obtained by hashing the output of an authenticated Diffie–Hellman key agreement, $H(g^{ab})$; maybe it's a pre-shared secret you pulled out of /dev/urandom on your laptop and copied over an authentic channel to an application server.  If you have a password, rather than a uniform random string of 16 or 32 bytes, then you must use a password-based key derivation function such as scrypt or argon2 to derive a key from it.

You will have to study the documentation to figure out how to supply a 16- or 32-byte key.  To confirm your understanding, write an experiment of reproducing an AES-GCM test vector with your understanding of how to supply the bytes of a key exactly, and save that experiment as a unit test.

The peers have to agree on the nonce to use for each message, too.  In the best case, they exchange messages in order, or mostly in order; in that case, you can use message sequence number as a nonce.  If this is a bidirectional channel, make sure to use one key for each direction, or odd nonces in one direction but even nonces in the other direction, or similar.  If you use message sequence numbers, there is no meaningful limit on the number of messages you can use AES-GCM for.  (The limit is $2^{96}$.  Exercise: How many centuries are in $2^{96}$ picoseconds?)

If you can't use a message sequence number as a nonce, you can pick the nonce uniformly at random from $2^{96}$ possibilities (AES-GCM is defined to accept larger nonces, but hashes them into only $2^{96}$ internal possiblities), but random nonces severely limit the number of messages you can exchange—you should avoid using them for more than a billion messages or so, to be on the safe side.
I can't tell you about $tag because again it's a PHP programming question.  But it is good that you are paying attention to this, because there are some APIs that inexplicably have a separate step for verifying the authentication tag, which is probably what $tag is.  You must never touch message data before you verify the authentication tag.  Unauthenticated message data is pure evil—don't touch it!  In a sensible API, the AES-GCM decryption operation will throw an exception or return an error code if verification fails, before you can even touch the evil.

I'd suggest you triple-check your API documentation—but that's not enough, because OpenSSL's documentation is notoriously bad.  So write an experiment to flip a bit in a message before you try to decrypt it that confirms it fails, and save that experiment as a unit test.


How does authentication work for SSH login with a public key?

The goal of authentication is to verify the identity of a party to communication, i.e. to check that they are who they claim to be. Two parties are involved: the verifier, and the requester. Here the verifier is the server and the requester is a remote user, but in other cases they could have different roles.

Authentication using asymmetric cryptography involves several steps of reasoning.

Only the legitimate requester knows the private key. Everybody else is unable to make computations that require the private key.
The verifier is able to tie the public key with an identity. Maintaining the association between the public key and the identity is the responsibility of the verifier. In this case, the association is made through a configuration file on the server that says “the public key whose has is … is user #42 authorized to log in as admin”.
In order to be authenticated by the verifier, the requester must perform a computation that requires the private key corresponding to a public key. This can be either a signature that the verifier verifies, or an encryption whose result the verifier decrypts.
The combination of (1), (2) and a successful (3) allows the verifier to conclude that the requester has the identity associated with the public key.

In order to perform step 2, the server needs to have the public key. But it doesn't need to store the public key. It's ok if the requester sends the public key. The verifier calculates the hash of the public key sent by the requester and compares it with its stored hash. If the hash is correct then the requester has proved the association between the public key and the identity (because it's unfeasible to find a public key with the same hash as the expected one). When the requester proves that they know the associated private key, they have thus proven their identity to the verifier's expectations.

In a nutshell, it's ok for the verifier to store only a hash of the public key because:

functionally, because the requester sends the public key;
in terms of security, because knowing the hash allows the verifier to validate the public key.

This principle of hashing a public key is used all the time on the web, when browsers authenticate websites (so in this scenario, the requester is the website and the verifier is the browser). On the web, there's an extra step where a browser doesn't even know the hash of the website's public key before connecting. What the website sends in addition to its public key and to the proof of possession of the private key is an assertion of the form “this is the hash of the public key of www.example.com”, cryptographically signed by a certificate authority that the browser trusts. This assertion is called a certificate. (In fact, things are more complicated, but I gave the basic principle.)


Is it possible to decide the base of a discrete logarithm?

It's obviously possible to decide if $R=g_1^r\mod p$ or  $R=g_1^r \mod p$ simply by computing successive powers of $g_1$ and $g_2$ until either $R$ is matched or $g_1$ or $g_2$ respectively is reached. However this is slow.

We can call $g_1$ and $g_2$ "generators" and the set of all values $g^x \mod p$ the "subgroup generated by $g$". You can find $R=g^x$ if and only if $R$ is a member of the subgroup generated by $g$. The number of elements of the subgroup is the "order" of $g$ and a factor of $p-1$

If $g$ is a quadratic residue mod $p$ (i.e it is possible to find an $x$ such that $g=x^2 \mod p$) and $R$ is not a quadratic residue then it's not possible that $R=g^r$. It's possible to determine very quickly (by calculating the legendre symbol) whether a number is a quadratic residue or not for any prime.

This generalises to cubic etc residues for suitable primes.

As Ricky Derner mentions in a comment, the problem is a staple of cryptographic constructions and can be made easy or hard based on the factorization of $p-1$ and the order of $g$.


How to construct a hash function into a cyclic group such that its discrete log is intractable?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(x)^2 \bmod (2q+1)$ (that is, square $H(x)$ modulo $2q+1$).

If we treat $H$ as a random oracle, then $H_2(x)$ is a random element (uniformly distributed, other than 1) of the subgroup of $\mathbb Z^*_{2q+1}$ that consists of quadratic residues. We can see this is a random element because each possible value of $H(x)$ yields a distinct quadratic residue, and there are $q-1$ subgroup elements (other than 1), and so each output is generated with equal probability.

This subgroup is the order $q$ subgroup has that you're thinking of, and if the DLP is hard, then it's hard to solve DLP on random elements.


Can a repeated random sequence be considered random?

Remember, sequences themselves are not random or not; the process for generating the sequence is random or not.  The question is: is your repeated sequence compatible with the hypothesis that its source is random?

Given a uniform random bit generator, the chance that it will generate any one sequence of $n$ consecutive bits is $2^{-n}$.  The chance that, given that the previous $n$ bits were $x$, a random bit generator will proceed to produce $x$ again as its next $n$ bits is also $2^{-n}$.  So in your case with $n = 10^6$ the chance that a random bit generator is $2^{-10^6}$—a crazy small number.  If we observed such a sequence, then, we would reject the hypothesis that the bit generator is random with near certainty.


SSH not using TLS is mostly historical; see for instance this answer (on security.SE). In practice, one could perfectly define a sort-of SSH that would use TLS for the data transport part; but, of course, it would not be compatible with existing SSH servers and clients. From a pure cryptographic point of view, SSH actually has some shortcomings with its encrypt-and-MAC encryption, and encrypted "length" field; this does not lead to really exploitable vulnerabilities due to the specific usage of SSH (attackers don't get to trigger thousands of new silent connections with partially chosen data, contrary to TLS, where such things can be done thanks to the magic of JavaScript), and recent AEAD integration mostly fixes them anyway.


Reusing encrypted message on MITM attack?

You didn't mention the mode of encryption used.
If you are using CBC, predictable IVs maybe an issue.
I would recommend not reusing IV to prevent message replay. You can add a counter inside the encrypted payload and ensure it is increasing.
Notice when you add protection against replay you need to think about out of order etc.
In many cases protocols add timestamps and allow only a limited discrepancy.


Does it increase security if the CBC chunks of a AES-256 encrypted bytestream are uploaded to different clouds?

First of all, AES-256 is considered the gold standard on the market by the industry.   The quantum attack on a block cipher is performed by Grover's algorithm that can provide at most quadratic speed up on the key search. The qubit requirements, setup, and running time even for AES-128 is not easily solvable in a near future, and AES-256 is safe. The below table is from

M. Grassl et. al, Applying Grover's algorithm to AES: quantum resource estimates, 2015.

\begin{array}{cccccc}\hline
& \#gates & & depth & & \#qubits\\
k & T & Clifford & T & overall & \\ \hline
128 & 1.19 \cdot 2^{86} & 1.55 \cdot 2^{86} & 1.06 \cdot 2^{80} & 1.16 \cdot 2^{81} & 2953 \\
192 & 1.81 \cdot 2^{118} & 1.17 \cdot 2^{119} & 1.21 \cdot 2^{112} & 1.33 \cdot 2^{113} & 4449 \\
256 & 1.41 \cdot 2^{151} & 1.83 \cdot 2^{151} & 1.44 \cdot 2^{144} & 1.57 \cdot 2^{145} & 6681 \\
\end{array}

Does it increase the security of my data if I split the CBC chunks to let's say 2 clouds? Uploading the even-numbered CBC elements to e.g. Google and the odd-numbered elements to Amazon. Since one storage hoster is constantly missing the next part of the CBC-Chain (1/2 in total) shouldn't this increase security of the data even if the AES key is known by the hoster(s)?

This is a security question on unidentified risks. What if both X and Y are combining their power or they are forced by the government to combine the data, so no benefit there.
What if a huge regression occurs and one of the companies goes out of business so fast. Will you able to get the other chunk? and even in a more catastrophic scenario that your copies are already corrupted.
The hard disks are failing, DVDs degrading, computer systems are not perfect, etc. Solving these is out of Cryptography, the common techniques are multiple copies and raid system like NAS.
Your main issue is the integrity and authentication of your data. To solve this issue you need authenticated encryption and for CBC you can achieve this with HMAC, or better you can use authenticated encryption modes like AES-GCM, Chacha20-Poly1305 those will provide Confidentiality, Integrity, and Authentication. Each has pros and cons mainly take care of the $(IV,key)$ reuse problem.


Timing attacks against a function $f_k$ generally require two things:

The attacker might observe the target perform $f_k(x)$ for a large number of sufficiently diversified known inputs $x$.
For each $k$, there are inputs $x$ and $x'$ such that $f_k(x)$ and $f_k(x')$ are expected to execute at different speed.

Now, let's assume $f_k$ is the private key operation of Diffie-Hellman or RSA, that $k$ is the (fixed) private exponent of the target, and that the inputs are, say, 2048 bit integer values. Normally, the implementation of the operation $f_k(x) = x^k \mod p$ is such that it executes the exact same number of CPU instructions regardless of the value of $x$, so there will be no timing difference to observe (presuming the CPU performs e.g. a MUL or DIV at a fixed number of clock cycles).

There are however things to watch out for. If some $x$ is significantly smaller than the maximum size of 2048 bits and the implementation of modular multiplication is optimized to account for that, some of the least or most significant bits of $k$ might leak, depending on if the exponentiation implementation iterates the bits of the exponent from right to left or the other way around. Since the intermediate result grows exponentially, this will only reveal at most 11 bits of the exponent in the most unfavorable case of $x=2$.

To prevent this leak (again assuming the CPU performs a MUL instruction etc at a fixed number of cycles independently of the value of the operands), all that is needed to prevent such leaks is to justify the size of all inputs to the size of the modulus at the beginning of the exponentiation function implementation.

Now, next case, suppose the attacker is able to repeatedly slow down the system, at a time that averages out at the moment the target will either perform a modular multiplication because the corresponding bit of the private exponent $k$ is $1$, or not perform a modular multiplication because the bit is $0$. It suffices to say that if the modular exponentiation is e.g. performed by the CPU in a multi-threaded application, this can be done with some statistical accuracy, if the attacker somehow might control what else is executed by the CPU, either passively or actively.

One trivial way to blind the private key even in such cases, would be to always generate a fresh random integer $z$ that is invertible $\mod q$ where $q$ is a multiple of the order of $x$ (e.g. $p-1$ if the order is not known). Instead of calculating $f_k(x) = x^k \mod p$, you would calculate

$k' = kz \mod q$
$y = x^{k'} \mod p$
$w = y^{z^{-1}\mod q} \mod p$
return $f_k(x) = w$

The only step here that depends on the private exponent is the first, which has to be assumed to not vary in performance time depending on the value of $k$. The overhead of this method is on average a factor of 2, presuming modular inverses in $Z_q$ can be calculated in negligible time.

Another technique would be to make the number of modular multiplication completely independent of the bits of the private exponent, e.g. by using a sliding window technique. This means that a table of $2^m$ integers is built, and one of these values is picked for every $m$ bits of the binary representation of the private exponent. It should however be noted that this technique might make matters worse, e.g. if the time for picking one of the integers from the table depends on the index of that element.

It should also be noted, that while it has been advocated to blind the input value $x$ to-be-raised, instead of the private exponent, this will have no effect on a CPU that executes MUL independently of the value of the operand, and have no effect at all against both passive and active timing attacks that measure the timing differences relative to which bit position in the exponent is being processed.


Yes (assuming $A$ knows the Paillier private key and $B$ knows the Paillier public key and the values of $x$ and $y$)

With Pallier, someone with the public key can:

Homomorpically multiply a ciphertext by a known value; that is, given $x$ and $E_{pkA}(m)$ compute $E_{pkA}(xm)$
Encrypt a known value; that is, given $y$, compute $E_{pkA}(y)$
Homomorphically add two encrypted values; that is, given $E_{pkA}(xm)$ and $E_{pkA}(y)$, compute $R = E_{pkA}(xm + y)$

The resulting $R$ value can be decrypted by $A$; $A$ cannot deduce anything other than the value $xm + y$


There are many possible constructions but the simplest is probably to initalize a counter with a random seed and hash the counter to produce more random bits and then increment the counter.


How to calculate entropy of a combined key

With proper hashing the entopy of $Z$ is roughly the sum of both individual entropies, capped to the strength of the hash-function. For SHA-256 the limit is 256 bits, for SHA-512 it's 512 bits. Since entropy above 256 bits is meaningless, this isn't a practical limitation.

For XOR computing the entropy of $Z$ is tricky and depends on how your keys are distributed. It's probably only as strong as the stronger of the two key, which is clearly worse than the sum. If the keys are correlated it might even fail catastrophically.

=> Use HKDF with a good underlying hash


Is it safe to derive a password from a signature provided by ssh-agent?

Is this approach (deriving a password from a signature) cryptographically sound?

Not in general. There are signature algorithms that are completely deterministic and signature algorithms that aren't. With the latter kind you would be unable to reproduce the password later.

With a deterministic algorithm, yes, the basic idea of using the signature as a password is sound (assuming no attacker can get the signer to sign the same token in some other situation). If it wasn't secure, that would mean the attacker had some way to produce the same signature, which would mean the signature algorithm itself would be broken.

Note that rather than sending a token for the client to sign, an SSH v1 server actually encrypts a token, sends it to the client and stores a hash. The client must decrypt the token and reproduce the same hash in its response. (See section 2.3 of the document you linked.) This is likely why the linked program talks about 160-bit passwords.

A similar argument as above makes this secure: to know the hash an attacker has to either know the original token generated by the server or be able to decrypt the challenge (which they can't do without the key, unless the encryption algorithm is broken).

  Is this approach secure? For example, when SSH agent forwarding is used, is the signing request and response (exchanged between remote host and local ssh agent) safe from eavesdropping?

As for whether that's safe from eavesdroppers... yes, if you assume they are outside the systems involved. An attacker with sufficient control over the final destination machine could eavesdrop the original challenge generation. An attacker with sufficient control over the source machine where you authenticate could similarly eavesdrop the response generation.

I'm not entirely sure whether an attacker on the middle machine would be able to do the same, but I believe so. As I understand the forwarded traffic passes unencrypted from ssh to sshd and is only encrypted between the hosts. That's (one reason) why some people have suggested using more complicated layered ssh connections instead of agent forwarding.


Difficulty of collision vs preimage vs second-preimage attacks

For a $n$-bit ideal hash:

Finding a collision is expected to require a little above $2^{n/2}$ hashes, in short because after having computed $m$ hashes, there are $m(m-1)/2$ opportunities of collisions. For details, see Birthday problem for cryptographic hashing, 101.
Finding a preimage (first or second) is expected to require about $2^n$ hashes, in short because the best known method is to try until hitting the hash thought, and each try has odds $2^{-n}$ to succeed.

The naive algorithm to find collisions with about $2^{n/2}$ hashes requires to store the previous hashes and search among these, thus requires in the order of $2^{n/2}n$ bits of memory, which is totally impractical for cryptographic hashes. However, with better methods, memory becomes essentially a non-issue.

The simplest such method is Floyd's cycle finding, which uses negligible memory, at the expense of like tripling the expected number of hashes. Better methods exist that achieve a lower increase of the expected number of hashes, or/and allow a near arbitrary number of independent search engines to cooperate with modest data exchange. The reference article is Paul C. van Oorschot, Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology (1999).


Is it ever unsafe to compress an EC point?

I would argue the opposite: it's safer to compress a point.

The reason is fairly simple.   During decompression- whose most expensive operation is a modular square root - your are guaranteeing that the resulting point either is on the curve, zero or infinity.

One of the most frequent errors in elliptic curve operations is failing to properly validate a point before operating on it.   The most public example of this is the Bluetooth pairing vulnerability - which, had it used compressed points, would not have been vulnerable to MITM attacks.

While validation is less expensive than decompression - it's one of those "seemingly optional" steps that people can forget to do.   With compressed points there's no option.


Yes, AES is just used as a 128 bit / 16 byte block cipher in this scheme. The paper specifies:

Poly1305-AES feeds each nonce $n$ through $AES_k$ to obtain the 16-byte string $AES_k(n)$.

There is no mention of AES without this key $k$ or nonce $n$. So, as far as AES - the block cipher - is concerned, $k$ is the key and the nonce $n$ is the data / message.
The reason that no mode-of-operation such as ECB / CBC is mentioned is that the specification uses the block cipher itself, without any mode. If you only have access to AES-ECB then you should use ECB without padding (or, if padding is always performed, just taking the first 16 bytes after feeding the nonce). You can use CBC with an IV using 16 zero valued bytes in a similar manner. Or you could use CTR with the nonce $n$ and an all zero plaintext of 16 bytes - probably makes most sense as CTR mode won't pad.

FYI the reason that you don't find an example in a TLS library is possibly that they use ChaCha20/Poly1305 where the ChaCha20 cipher is used instead of AES
From RFC 7905 section 1:

The variant of ChaCha used in this document has 20 rounds, a 96-bit
nonce, and a 256-bit key; it is referred to as "ChaCha20".  This is
the conservative variant (with respect to security) of the ChaCha
family and is described in [RFC7539].

From RFC 7539 section 2.8.1:
 otk = poly1305_key_gen(key, nonce)

...
 poly1305_key_gen(key,nonce):
     counter = 0
     block = chacha20_block(key,counter,nonce)
     return block[0..31]
     end

So here chacha20_block is used instead of AES - they did say it was nothing special right? Note that the encryption then helpfully starts with counter 1 instead of zero, so it is a simple continuation of ChaCha20...


Elliptic curve ElGamal with homomorphic mapping

There is a way to use ECEG that gives us an additive homomorphic property, however the addition in this case is Elliptic Curve point addition, not addition over the integers.

One way to use ECEG to encrypt a point $M$ is to have the encrypted value be the pair of points $(kP, M + kY)$

That way, if you have the encryption of the points $M, M'$ as $(kP, M + kY)$ and $(k'P, M' + k'Y)$, you can add each element in the pair to form $( kP + k'P, M + kY + M' + k'Y) = ((k + k')P, M + M' + (k + k')Y)$, which is a valid encryption of the point $M + M'$


Solving for $D$ in this case is known as the discrete logarithm problem. This is a known hard problem, as there are no known algorithms to calculate it in polynomial time. In other words, as the size (i.e. the number of digits) of the numbers increase, the time it takes to calculate gets higher exponentially. For this reason, it's used in cryptography as a one-way function for many things including RSA and Diffie-Hellman.


What happens when domain parameter $q$ in DSA is not prime number

Well, it makes the discrete log problem easier; hence it makes recovering the private key easier

The DSA private key is a value $k$, and his public key is the value $g^k \bmod p$.  $g$ has order $q$; if $q = q_1 \cdot q_2$, then the attacker can compute $(g^k)^{q_2} = (g^{q_2})^k$. The value $g^{q_2}$ has order $q_1$, and so he can solve that problem in $O(\sqrt{q_1})$ time; that gives him the value $k \bmod q_1$.  Similarly, he can recover the value $k \bmod q_2$ in $O(\sqrt{q_2})$ time; from that, he can reconstruct the original value $k$ in what turns out to be a total of $O(\sqrt{ max(q_1, q_2) })$ time, rather than the $O(\sqrt{q})$ time it would take if $q$ were prime.


a homomorphic operation on Paillier encryption

Question 1: Given $c$ and $(r_i)^{-1}$, can we "always" perform $c^{(r_i)^{-1}}=E((r_i)^{-1}\cdot (r_i)\cdot m)$ such that its
  decryption value only contain $m$?

Yes. You can multiply arbitrary values $x$ into a message using paillier encryption and it will result in multiplication $\bmod n$ and thus you'd get $m$ back.

This would happen by  exponentiating the cipher text with the $x$, as $c^x\bmod {n^2}$ as you described.

  Question 2: given $E(m)$,  how can we chose its additive inverse $m'$ such that $E(m).E(m')=E(m+m')$ so its decryption value would be
  0? should $m'\in \mathtt{Z}_N$ or $m'\in \mathtt{Z}_N{^2}$

I don't think there's any way given a ciphertext of $m$ to construct a plaintext $m'$ that would yield $m+m'=0$ as this would trivially equal a plaintext recovery and thus a (nearly) total break of the encryption.

However, you can use the answer from question one to calculate the additive inverse ciphertext, which would be $c^{n-1}\bmod{n^2}$. If you multiply this with the original cipher text, you will get an encryption of $0$, to which you can add whatever you want (e.g. an encryption of 1?).

Alternatively you might as well just exponentiate the ciphertext with $0$ to get the same result...


Weaker Notion of Target Collision Resistance

We often rank cryptographic problems according to how hard they are. One problem is not harder than another problem if an algorithm that solves the second problem can easily be turned into an algorithm that solves the first problem.

Your question considers two issues: how hard the adversary's job is, and the strength of our assumption. If one problem is not harder than another problem, then if we assume that the first problem is hard, we must also assume that the second problem is hard. However, if we assume that the second problem is hard, the first problem may still be easy.

Since assuming that the first problem is hard has more implications than assuming the second problem is hard, we say that the first assumption is stronger than the second assumption, and correspondingly that the second assumption is weaker.

Any adversary against TCR is trivially an adversary against collision resistance, so TCR is not harder than collision resistance. Therefore, we say that TCR is a weaker notion than collision resistance.


AES-GCM recommended IV size: Why 12 bytes?

From the proposal of GCM (rewritten if statement):

  if $\operatorname{len}(IV) = 96$ then $Y_0 = IV || 0^{31}1$ else
  $Y_0 = \operatorname{GHASH}(H, \{\}, IV)$.

So there are additional calculations for IV's other than 96 bits. This is why the original proposal has this recommendation:

  96-bit IV values can be processed more efficiently, so that [ed: this] length is recommended for situations in which efficiency is critical.

but also in the security section it is explained that the IV-processing of GCM was not previously taken into account for GHASH:

  Counter mode was suggested in 1979 by Diffie and Hellman [21], and was shown to be secure in a strong, concrete sense by Bellare et. al. [22]. While the proof of security for GCM rests on those proofs, there are some differences. The derivation of the hash key $H$ from the block cipher key $K$, the hashing of the $IV$, and the use of that key for both IV-processing and message authentication are important details.

NIST SP-800 38D has a whole chapter - chapter 8 - dedicated discussing key and IV uniqueness and the maximum number of invocations of GCM.

If the uniqueness of the IV / key combination cannot be met then security of GCM fails catastrophically.

Then again, that goes for any other cipher as well, particularly those build upon CTR mode encryption (which includes GCM, but also EAX, CCM etc.).

My suggestion is that if you've got small but unique IV input that you expand that input yourself to 12 bytes, if possible according to the hints in NIST SP-800-38D: 8.2.1 Deterministic Construction.

If it is not possible to generate a value that is unique and 12 bytes or below then you might want to consider a fully random IV consisting of 12 bytes.


You can search for root certificates of a given CA.

E.g.:

http://www.symantec.com/page.jsp?id=roots, but this page is served over plain HTTP so maybe you shouldn't trust it!
or https://www.mozilla.org/projects/security/certs/included/.

From there when you want to check a certificate you can check whether it belongs to/was signed by a root CA you trust. If you trust it, then you can get its public key.

More commonly as CodesInChaos said, trusted certificates are shipped with your OS/browser.


For an easy to grasp explanation, you can have a look at the talk Obfuscation I at the Cryptography Bootcamp by Amit Sahai. Here's a link to youtube. In this context he also explains matrix branching programs, which are also used in the construction of indistuingishability obfuscation. He starts explaining them at the minute 40.

In short: You're given $2k$ of invertible matrixes $A_{x,y}$ with  $y\in\{0,1\}$, $x=0,1,\dots,k-1$. For an (previously fixed) input of $n$ bits $b_i$ ($i={0,1,\dots,n-1}$), ($k$ should be a multiple of $n$), you multiply them like this:
$$\prod_{x=0}^{k-1} A_{x,b_{x \text{ mod }n}}$$

And if you evaluate it honestly (following this rule), you either get the identity matrix or a different, fixed matrix $B$, and this is equivalent to an output of a single bit of the function, which is realized by this matrix branching program.

A nice feature is that you can realize all programs in $NC^1$ this way in poly sized matrix branching programs. But I really suggest watching the video, even if just for the matrix branching part.


So for an unknown number of parties $x$, I make $x-1$ random $n$-bit strings represented by {$r_1, r_2,...,r_{x-1}$}. Where  $s$ is the complete string split up between $x$ parties (yes?).

  I then send each party one of the fragments $s_i$, so party 1 would get $s_1$, party 2 would get $s_2$ etc. all the way through to $s_{x-1}$. Along with these fragments. I then send $r_1⊕...⊕r_{x-1}⊕s$ to party $x$.

That is not how it is typically done.  One issue is that two parties (say, party 1 and party $x$) get partial information of the shared secret, that is, the part that was masked by $r_1$.

Instead, what we do is make $x-1$ random strings (each as long as the secret $s$).  Then, we send party 1 the string $r_1$ (not $s_1$), party 2 would get $r_2$, etc.  And then send $r_1 \oplus r_2 \oplus ... \oplus r_{x-1} \oplus s$ to party $x$.

This can be seen to yield no information about $s$ to any $x-1$ parties, and still makes $s$ recoverable to someone with all $x$ shares.

Studying this version of the protocol may answer your questions.


Playfair cipher - questions about inserting 'X'

As Maarten notes in the comments, you're indeed expecting rather too much from an old classical cipher designed to be used by hand.  Ciphers from that era were simply not designed to be able to mechanically and unambiguously encode all possible messages.

Basically, as you've noted, the Playfair cipher as you've described it cannot encrypt all messages; specifically, it cannot handle messages where two consecutive identical letters fall into the same group, nor messages of odd length.  (There are Playfair variants that can handle both of those in various ways, but you don't seem to be using any of those variants.)

It is thus the encryptor's responsibility to somehow ensure that their message is of a suitable form to be encrypted with the cipher, while still (hopefully) conveying the appropriate meaning to the recipient when decrypted.

One common convention for doing that is to break up unencryptable plaintext segments (or pad messages with an unsuitable length) by inserting a dummy letter that is obviously misplaced, and which the recipient can therefore safely ignore while reading the message.  X and Q are common choices for such dummy letters, being rare in normal English text, but really any letter can be used.  So, for example, if you needed to break up a rare double X, you could e.g. turn it into XQX or XZX or whatever; it just needs to be something that the recipient can spot as an obvious error, and which they can be expected to be able to reliably correct.

But note that you also have other options: for example, you could simply choose to rephrase your message using different words that don't contain the problematic double letter.  Or, for the specific case of the Playfair cipher, you could simply choose to insert an extra dummy letter somewhere earlier in the message (or just adjust your word choice to change the length of the message) so that the double letter now gets split between two encrypted letter pairs.

In any case, note that the Playfair cipher (like most ciphers of its era) has a much more significant limitation: it cannot encode spaces or punctuation.  Thus, it cannot distinguish "inverse" from "in verse" or "No retreat!" from "No, retreat!".  So you will in any case have to take care when composing your messages to avoid potential misunderstandings due to run-on words and sentences.

(Some of that ambiguity can also be reduced by conventions like, say, inserting an X between words and a Q between sentences.  But such conventions are also just imperfect patches on top of a fundamentally limited encoding scheme.)

Of course, the Playfair cipher has other limitations too, like the inability to express letters outside the English alphabet.  Indeed, it cannot even represent all the letters in the English alphabet, typically conflating I and J into a single symbol.  Again, this is just something that the receiver is expected to be able to disambiguate based on context.


My answer to a multi-sig question may shed some more light if you're interested in more flexible groups.

I don't see the date of the paper you've linked, but it does not reference anything after 2k. The following is from 2001.

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

As far as I know there isn't anything that would compete directly without being a distinct protocol. If you want n-of-n, you may look at MuSig, which is a recent advancement in the n-of-n signing of a common message. If you want a subset, you can select the signers directly. This isn't anonymous between cosigners as in t-of-n; but it is directly traceable.

Joining a new member to the group does not change old signatures, but it does change the identity of the group. Evolving t-of-n produces opaque new identities; while n-of-n MuSig evolves transparently. In either case you'll need to have some method and protocol to manage which identities are valid and when. I.e. Git code signing could be relative to the state of the commit.

What properties are you interested in?

If you want t-of-n anonymous groups. AFAIK you'll need to do a re-key and establish a new identity for any group changes. This would certainly be annoying to maintain, especially if this is frequent.

If you want a traceable subset of a larger known, and trivially dynamic group; then you may prefer a direct n-of-n through identity-aggregation.


Decoding an MD5 hash where I already know most of the string


Anubis (128-bit block) and Khazad (64-bit block) work by using involutional components in sequence. The complete ciphers are not fully involutional, as the key schedules and round constants prevent that from occurring. Decryption requires a different key schedule, but all other operations remain the same. They are SP-network ciphers, which are generally not involutional.

Feistel ciphers also use the same core components for encrypt and decrypt, but work differently, in that they generally do not use components that are involutions. As orlp pointed out, changing the key schedule can make a Feistel cipher into a full involution.

The advantage to involutional components is code reuse; you have a single encrypt/decrypt operation, and most parts of the key scheduling algorithms. It may also be easier to analyze the algorithm. The disadvantage is the components may be suboptimal, which means it usually will require more rounds to provide the same level of non-linearity and diffusion when compared to say, the AES candidates.

For the diffusion component (P) of the cipher, a Cauchy matrix is the go-to operation, since it provides a high branch diffusion, is an involution, and is simple to implement in reference and table-lookup designs. Large matrices can be implemented to provide full diffusion in a single round, but are slow outside of a table-lookup implementation. Khazad uses a large 8x8 matrix operating on the whole 64-bit block, whereas Anubis uses a 4x4 matrix like AES multiple times.

Here is the 8x8 MDS diffusion matrix for Khazad:

\begin{bmatrix}
01_x~~ 03_x~~ 04_x~~ 05_x~~ 06_x~~ 08_x~~ 0B_x~~ 07_x \\
03_x~~ 01_x~~ 05_x~~ 04_x~~ 08_x~~ 06_x~~ 07_x~~ 0B_x \\
04_x~~ 05_x~~ 01_x~~ 03_x~~ 0B_x~~ 07_x~~ 06_x~~ 08_x \\
05_x~~ 04_x~~ 03_x~~ 01_x~~ 07_x~~ 0B_x~~ 08_x~~ 06_x \\
06_x~~ 08_x~~ 0B_x~~ 07_x~~ 01_x~~ 03_x~~ 04_x~~ 05_x \\
08_x~~ 06_x~~ 07_x~~ 0B_x~~ 03_x~~ 01_x~~ 05_x~~ 04_x \\
0B_x~~ 07_x~~ 06_x~~ 08_x~~ 04_x~~ 05_x~~ 01_x~~ 03_x \\
07_x~~ 0B_x~~ 08_x~~ 06_x~~ 05_x~~ 04_x~~ 03_x~~ 01_x \\
 \end{bmatrix}

As you can, see, all 4x4 diagonal corners of the matrix are same, all 2x2 diagonal corners of those matrices are the same, and all 1x1 diagonal corners of those matrices are the same. That is the property that makes the Cauchy matrix an involution. The matrix can be built at runtime from a single row and a recursive algorithm.

For the substitution component (S) of the cipher, using an involutional s-box is not optimal. Even the best involutional s-boxes have inferior properties when compared to modern block ciphers. Anubis and Khazad use the same s-box, here is a comparison to some of its primary properties against the AES s-box:

                          AES       Anubis/Khazad
Nonlinearity:             112       96             higher is better
Differential Uniformity:  4         8              lower is better
Autocorrelation:          32        104            lower is better
Sum of Squares Indicator: 133120    270208         lower is better

AVAL Relative Error:      3.52%     11.72%         lower is better
Bit Independence Rel Err: 13.4%     27.6%          lower is better
SAC Relative Error:       12.5%     34.4%          lower is better
Distance to SAC:          432       620            lower is better

These suboptimal s-box properties are the main reason that Anubis requires more rounds than AES for the same key size, as their diffusion component is essentially the same. The s-box has an iterative period of 2, with every element paired to another.

If you wish to create a cipher that is a full involution, your best bet is a Feistel structure. You can use involutional components but that is not a requirement. If your goal is code reuse and simplicity of description, look at the design principles of Anubis.

You can also use a stream cipher mode such as CTR on any block cipher, as XOR is its own inverse.


Hint:

Combine the usual definition of perfect secrecy $$\Pr[M=m\mid C=c]=\Pr[M=m]$$ with a non-uniform distribution $M$, e.g. $\Pr[M=0]=0.25, \Pr[M=1]=0.75$.


Based on the example given in the question (see here) the following (hex-encoded) bytes would be hashed:
From the Public-Key Packet
Ciphertype Byte: 99

Key Length: 01 0d

Version: 04

CreatedAt: 5e f4 a2 c6

Algorithm: 01

n (with tag): 08 00 a8 14 6d b3 75 12 72 33 1e 92 54 c5 43 f6 44 d2 22 5d 4d 9b 0c b8 5d 60 60 8b f0 39 08 1e 31 29 e2 f5 4c 83 e0 71 b7 22 e3 f8 78 9b c4 a2 c1 aa 70 72 3a eb c5 1e ec d1 65 9b 58 50 20 f4 d0 36 db 79 c8 24 6a bd 43 3f 08 28 6c 35 b2 16 30 6b 14 4c 94 74 5a fa 85 5a 05 8d 06 3b 94 29 f1 98 71 f4 04 48 9b 84 ef b9 94 65 eb 9c 0a 97 b6 d2 46 13 64 42 57 13 ea 08 48 62 5f 24 ea f3 d5 f5 2b 72 b6 96 e0 af ac 4b 68 41 af fc 64 cd 55 a1 75 05 33 ed 0b 78 a2 6c d4 33 d5 db 6a 72 78 78 9c ae 45 74 08 d2 40 72 30 4d f2 62 ea 29 6e d9 e8 5d 12 cf a0 7a e6 60 44 29 06 75 4f d0 71 c8 9f 35 8a 45 52 45 20 04 7a 79 cc 54 8e ba 10 1b ae f0 9e 24 68 56 98 18 10 2b f5 95 c1 5a 50 57 5a 47 6f e5 61 44 f7 2f 86 fe 8c 54 a1 4d a8 13 68 e6 e2 b4 57 aa 2f fa c5 06 fc 13 47 98 23 c7

e (with tag): 00 11 01 00 01

From the User ID Packet
Ciphertype Byte: b4

Length: 00 00 00 1c

UserID: 47 50 47 20 54 65 73 74 20 4b 65 79 20 3c 74 65 73 74 40 74 65 73 74 2e 63 6f 6d 3e

From the Signature Packet
Version: 04

Signature Type: 13

Public Key Algorithm: 01

Hash Algorithm: 0a

Hashed Data Count: 00 38

Undefined Subpacket Length: 16

Undefined Subpacket Type: 21

Undefined Subpacket Data: 04 43 3f bc 55 ab 6d 09 17 21 13 18 3a 79 1a 5a be 3e 62 44 95

Creation Time Subpacket Length: 05

Creation Time Subpacket Type: 02

Creation Time Subpacket Data: 5e f4 a2 c6

Key Flags Subpacket Length: 02

Key Flags Subpacket Type: 1b

Key Flags Subpacket Data: 2f

Preferred Symmetric Algorithms Subpacket Length: 05

Preferred Symmetric Algorithms Subpacket Type: 0b

Preferred Symmetric Algorithms Subpacket Data: 09 08 07 02

Preferred Hash Algorithms Subpacket Length: 06

Preferred Hash Algorithms Subpacket Type: 15

Preferred Hash Algorithms Subpacket Data: 0a 09 08 0b 02

Preferred Compression Algorithms Subpacket Length: 04

Preferred Compression Algorithms Subpacket Type: 16

Preferred Compression Algorithms Subpacket Data: 02 03 01

Features Subpacket Length: 02

Features Subpacket Type: 1e

Features Subpacket Data: 01

Key Server Preferences Subpacket Length: 02

Key Server Preferences Subpacket Type: 17

Key Server Preferences Subpacket Data: 80

Other Data
Trailer: 04 ff

Big-Endian Count of Hashed Signature Packet Data: 00 00 00 3e

Full Byte Array
(i.e. a concatenation of the bytes in 'From the Public-Key Packet', 'From the User ID Packet', 'From the Signature Packet', and 'Other Data'):
99 01 0d 04 5e f4 a2 c6 01 08 00 a8 14 6d b3 75 12 72 33 1e 92 54 c5 43 f6 44 d2 22 5d 4d 9b 0c b8 5d 60 60 8b f0 39 08 1e 31 29 e2 f5 4c 83 e0 71 b7 22 e3 f8 78 9b c4 a2 c1 aa 70 72 3a eb c5 1e ec d1 65 9b 58 50 20 f4 d0 36 db 79 c8 24 6a bd 43 3f 08 28 6c 35 b2 16 30 6b 14 4c 94 74 5a fa 85 5a 05 8d 06 3b 94 29 f1 98 71 f4 04 48 9b 84 ef b9 94 65 eb 9c 0a 97 b6 d2 46 13 64 42 57 13 ea 08 48 62 5f 24 ea f3 d5 f5 2b 72 b6 96 e0 af ac 4b 68 41 af fc 64 cd 55 a1 75 05 33 ed 0b 78 a2 6c d4 33 d5 db 6a 72 78 78 9c ae 45 74 08 d2 40 72 30 4d f2 62 ea 29 6e d9 e8 5d 12 cf a0 7a e6 60 44 29 06 75 4f d0 71 c8 9f 35 8a 45 52 45 20 04 7a 79 cc 54 8e ba 10 1b ae f0 9e 24 68 56 98 18 10 2b f5 95 c1 5a 50 57 5a 47 6f e5 61 44 f7 2f 86 fe 8c 54 a1 4d a8 13 68 e6 e2 b4 57 aa 2f fa c5 06 fc 13 47 98 23 c7 00 11 01 00 01 b4 00 00 00 1c 47 50 47 20 54 65 73 74 20 4b 65 79 20 3c 74 65 73 74 40 74 65 73 74 2e 63 6f 6d 3e 04 13 01 0a 00 38 16 21 04 43 3f bc 55 ab 6d 09 17 21 13 18 3a 79 1a 5a be 3e 62 44 95 05 02 5e f4 a2 c6 02 1b 2f 05 0b 09 08 07 02 06 15 0a 09 08 0b 02 04 16 02 03 01 02 1e 01 02 17 80 04 ff 00 00 00 3e

Resulting Hash
2f 9b ad fd 89 90 e9 34 f3 15 c6 9c c5 8e 45 12 47 29 fe ab e6 18 a2 e2 71 fb bf e1 9e 20 10 8a 86 ea d9 dd 5b 87 58 87 45 85 98 2a 68 14 e9 e2 ef 9e b6 07 12 1d 9b 7c 15 8f 58 79 c2 92 c5 e9

The two first bytes of the generated hash are shown in the signedHashValuePrefix of the used example (which was generated with the GPG CLI).


How to perform Stampery.com's Merkle Proof?

You seem to be doing everything right. The problem here is that you are using the verification process from BTA v5 on a proof generated by BTA v6 (the LTS version of our API). The v6 whitepaper is here.

Put simply: you'll need to use SHA256 instead of SHA3:

r = SHA256(SHA256(mP[2]+SHA256(SHA256(hash+mP[0])+mP[1]))+mP[3]);

Also make sure your hash functions operate on a byte level, not on the hexadecimal representation of the hash digests.

Please don't hesitate to ask for clarification!


How to optimise Euclidean Algorithm for large numbers? -RSA

This answer covers use and implementation of the Euclidean algorithm in RSA, first straight for computing the Greatest Common Divisor of two integers; then (half-)extended for the computation of modular inverses.

The (straight) Euclidean algorithm is often used at one step in RSA: when it comes to choose odd $e>1$ and distinct primes $p$ and $q$ such that $\gcd(p-1,e)=1=\gcd(q-1,e)$. It has very little cost compared to other computations involved in that choice, in particular the test that $p$ and $q$ are prime (which is not performed using the Euclidean Algorithm). $e$ is usually small, thus only the first step of the algorithm needs to be carried with large numbers. Further, often $e$ is prime (including when $e=F_k=2^{(2^k)}+1$ with $0\le k\le 4$, the 5 Fermat primes); hence $\gcd(p-1,e)=1$ holds precisely when $p\bmod e\not=1$, and this simple test sidesteps explicit GCD computation.

Another possible use of the (straight) Euclidean algorithm in RSA is when computing $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ , if that's desired.

One possible efficient form of the Euclidean algorithm to compute $\gcd(a,b)$ for positive integers $a$ and $b$ repeats (until the algorithm stops):

$a\gets a\bmod b$ .
That is, replace $a$ with $a'$ matching $0\le a'<b$ and $b$ divides $a-a'$ .
Or equivalently, $q\gets\lfloor a/b\rfloor$ followed by $a\gets a-q\,b$ .
If $a=0$, then output $b$ and stop.
Exchange $a$ and $b$ .

Practical implementations often replace the exchange with a copy of the other steps with permutation of $a$ and $b$ .

The average number of steps is significantly reduced in this optimized version, but each step is slightly more complex:

$q\gets\lfloor(a+b/2)/b\rfloor$ (that is $a/b$ rounded to nearest, sometime noted $\lfloor a/b\rceil$ )
$a\gets|a-q\,b|$ .
If $a=0$, then output $b$ and stop.
Exchange $a$ and $b$ .

In RSA, the extended Euclidean algorithm is often used to compute one or more of the following modular inverses:

$d=e^{-1}\bmod\varphi(N)\;$ with $\varphi(N)=(p-1)(q-1)$ .
$d=e^{-1}\bmod\lambda(N)\;$ with $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ .
$d_p=e^{-1}\bmod(p-1)$ .
$d_q=e^{-1}\bmod(q-1)$ .
$q_\text{inv}=q^{-1}\bmod p$ .

The last three are used by optimized implementations using the Chinese Remainder Theorem. One of the first two is customary in introductory material on RSA, and useful in practice when $d$ is required (for archival/interchange, or because the CRT optimization is not used).

In all cases, the half-extended Euclidean algorithm can be used to efficiently compute $a^{-1}\bmod b$ for non-negative integer $a$ and positive integer $b$ , manipulating non-negative integers only:

$x\gets0$ and $y\gets1$ and $m\gets b$ .Note: $ax+by=m$ will keep holding, with $m$ the original modulus.
if $a=1$, then output "the desired inverse is $y$" and stop.
If $a=0$, then output "the desired inverse does not exists" and stop.
$q\gets\lfloor b/a\rfloor$ .
$b\gets b-aq$ and $x\gets x+qy$ .
if $b=1$, then output "the desired inverse is $m-x$" and stop.
If $b=0$, then output "the desired inverse does not exists" and stop.
$q\gets\lfloor a/b\rfloor$ .
$a\gets a-bq$ and $y\gets y+qx$ .
Continue at 2.

Note: $a$ and $b$ evolve as in the straight Euclidean algorithm; $x$ and $y$ are the (half) extension. The (full) extended Euclidean algorithm keeps two more variables, in order to fully solve the Bezout identity.

Various optimizations apply to the Euclidean algorithm and its (half)-extended variant:

The quotient $q$ needs not be computed exactly. If it is too small, the penalty is that the next $q$ will be 0. If $q$ is too large, numbers can get negative (and that can be either dealt with, or corrected). We can thus get away with a rough estimation of $q$ (and it pays to round to nearest if we can deal with that).
Usually, $q$ is small. When the numbers handled use multiple limbs/digits, it pays to optimize the case when $q$ fits a single limb. It may even pay to special-case $q=1$ and $q=2$.
Large $q$ need to be handled (otherwise worst case execution time becomes linear with the inputs), but is infrequent thus not critical. We can round large $q$ down to a power of two. In fact, restricting to $q$ a power of two is not disastrous, and has the advantage of replacing multiplication with shifts.
Usually, it is possible to predict the next few values of the (small) $q$ from the high-order bits of $a$ and $b$. That allows to group several transformations of $a$, $b$, $x$, $y$ into linear transformations with moderate multipliers computed from the predicted values of the $q$.

Off-topic since strictly speaking that's no longer the Euclidean algorithm: there is a binary GCD algorithm that performs only subtraction, additions, and divisions by 2. It also has an extended version fully solving the Bezout identity (see the Handbook or Applied Cryptography, algorithm 14.61), and a half-extended version specialized towards computing the modular inverse (see the first section of this answer). It can be competitive with the Euclidean algorithm when multiplication is expensive; and the two can be blended.


How can we determine if two discrete logarithms are equal?

This problem is equivalent to the decisional Diffie-Hellman problem, and hence your problem is intractable (assuming, of course, that the group is well chosen).

Here's how we can use an Oracle that can solve the above problem to solve the DDH problem:

In the DDH problem, we're given values $g, g^x, g^y, g^z$, and we're asked whether $xy = z$.
We call the Oracle with the following instance: $n=2$, $g_1 = g$, $g_2 = g^x$, $y_1 = g^y$, $y_2 = g^z$.
The Oracle will return that $x_1 = x_2$ is a matching pair iff, for that same $w$, $g_1^w = y_1$ and $g_2^w = y_2$, that is, if $g^w = g^y$ and $g^{wx} = g^z$, which is to say, if $g^{xy} = g^z$

It's also obvious how to solve your problem with an Oracle that solves the DDH problem (using $n (n-1)/2$ calls to the Oracle).