How are points on an elliptic curve discretized?

How is the set of discrete points on elliptic curves determined for ECC applications?

One common method to define a point on an elliptic curve over a suitable finite field $(\Bbb F,+,\cdot)$ is that such point is one of

any pair of coordinates $(x,y)$ with $x$ and $y$ elements of the field that obey an equation $y^2\,=\,x^3+a\cdot x+b$, where $a$ and $b$ are suitable constant elements of the finite field;
an extra point called the point at infinity, noted $\infty$ (or $\mathcal O\,$), often assimilated to $(0,0)$, where $0$ is the additive neutral for the field and $b\ne0$.

That defines a finite (discrete) set: in principle, we can enumerate all the $(x,y)$ (say, with two nested loops) and for each pair test if the equation is met; then throw in the extra $\infty$. That form $(x,y)$ is a standard discrete expression of a point on the curve: Cartesian coordinates.
We can define a binary law on the curve, using the same equations¹ as for a continuous elliptic curve group law, only operating in the finite field. We'll note that new law $\boxplus$ (in order to distinguish it from the addition $+$ in the field, though $+$ is often used for both laws), such that for all points $U$, $V$, $W$ on the curve (including $\infty\,$)

$U\boxplus V$ is a well-defined point on the curve.
$(U\boxplus V)\boxplus W\,=\,U\boxplus(V\boxplus W)$ (that is: $\boxplus$ is associative).
$U\boxplus V\,=\,V\boxplus U$ (that is: $\boxplus$ is commutative).
$U\boxplus\infty\,=\,U$ (that is: $\infty$ is neutral for $\boxplus\,$).
There exists a point $I$ on the curve with $U+I\,=\,\infty$. That $I$ is uniquely defined, and can be noted $\boxminus U$ (that is: the inverse of $U$ is $\boxminus U\,$). $U\boxplus\,\boxminus U\,=\,\infty$ becomes $U\boxminus U\,=\,\infty$. When $U\ne\infty$, $U$ is $(x,y)$ with $x$ and $y$ in the field and meeting the curve's equation $y^2\,=\,x^3+a\cdot x+b$, and $\boxminus U$ is $(x,-y$), also meeting the curve's equation since $(-y)^2\,=\,y^2\,$. If holds $\boxminus\infty\,=\,\infty$. Thus when $\infty$ is noted $(0,0)$, it holds $\boxminus(x,y)\,=\,(x,-y)$ for all $(x,y)$ of the curve.

In the above construction, we "discretized" a continuous elliptic curve and it's addition operation $\boxplus$ by

changing from an infinite field to a finite field;
keeping the curve's equation and the addition formula.

We can define² multiplication of an integer $k$ and a point $U$ of the curve, by using repeated addition:
$$k\times U\,\underset{\text{def}}=\;\begin{cases}
\infty&\text{if }k=0\\
((k-1)\times U)\boxplus U&\text{if }k>0\\
(-k)\times(\boxminus U)&\text{if }k<0
\end{cases}$$
It follows $0\times U\,=\,\infty\,$, $1\times U\,=\,U\,$, $2\times U\,=\,U\boxplus U\,$, $-1\times U\,=\,\boxminus U\,$.
It can be shown that there exists a point $G$ such that the set of all $m$ points $U$ on the curve is precisely the set of $U=k\times G$ for $k$ from $0$ to $m-1$. And when we take any point $G$ of the curve, the set of all $k\times G$ forms a group of $n$ distinct elements of the curve under the law $\boxplus$, with $n$ dividing $m$. In cryptography, we typically arrange things so that $n$ is prime, either because $m$ is prime and $n=m$ (the whole curve is used), or by choosing an appropriate $G$ of prime order $n$ (the group is a subgroup of the whole curve).
The construction as $U=k\times G$ with $k$ from $0$ to $n-1$ is another (discrete) way to express a point of the elliptic curve (sub)group, and the one used to construct a public key $U$ from a private key $k$. However, $U$ is not made public in this form, for that would reveal the private key. $U$ can be revealed as a pair $(x,y)$.
There are other common (discrete) ways to express a point of the elliptic curve. In particular, when the field is $\Bbb F_p$ (the integers modulo prime $p\,$), any point $U$ other than $\infty$ can be expressed as $x$ and the parity of $y$ (in this construction, not all $x$ yield a valid point).
Another common way is as a triplet $(x,y,z)$ of elements of the field with $z\ne0$ and $y^2\cdot z=x^3+a\cdot x\cdot z^2+b\cdot z^3$, which makes the evaluation of $\boxplus$ simpler. We can get back to the curve in Cartesian coordinates by projecting to $(x/z,\,y/z)$ when desired.

¹ These equations are:
$$U\boxplus V\underset{\text{def}}=\,\begin{cases}
U&\text{if }V=\infty\\
V&\text{if }U=\infty\\
\infty&\text{if }(x_U,y_U)=(x_V,-y_V)\\
\big(\lambda^2-x_U-x_V,\lambda\cdot(2\cdot x_U+x_V-\lambda^2)-y_U\big)&\text{otherwise}
\end{cases}$$
with in the otherwise case
$$\lambda\,\underset{\text{def}}=\;\begin{cases}
(3\cdot {x_U}^2+a)/(2\cdot y_U)&\text{if }U=V\\
(y_V-y_U)/(x_V-x_U)&\text{otherwise}
\end{cases}$$
Note: $/$ is division in the finite field, such that for all $r$ and $s$ in the finite field with $s\ne 0$, it holds $(r/s)\cdot s=1$. Here $1$ is the multiplicative neutral for the field; $2$ is $1+1\,$; and $3$ is $2+1\,$. When the field is the integers modulo prime $p$, the quantity $r/s$ can be computed as r*pow(s,-1,p)%p in Python starting with version 3.8 ( r*pow(s,p-2,p)%p works in more versions).

² This definition involves a number of field operations linear with $k$. For efficiency, an implementation can use
$$k\times U\,=\;\begin{cases}
\infty&\text{if }k=0\\
(-k)\times(\boxminus U)&\text{if }k<0\\
U&\text{if }k=1\\
((k/2)\times U)\boxplus((k/2)\times U)&\text{if }k>1\text{ and }k\text{ is even}\\
((k-1)\times U)\boxplus U&\text{if }k>1\text{ and }k\text{ is odd}
\end{cases}$$


Why is 224 bit ecdsa faster than 192 bit ecdsa?

Both curves have similar form and primes close to powers of two ($2^{192}-2^{64}-1$ and $2^{224} - 2^{96} + 1$), so you wouldn't expect large differences in performance – all things equal, P-224 might be anywhere from 30%  to 60% slower due to the computational scaling of curve operations.
However, in practice different implementations will have different performance and some curves' will be better optimized. In this case it looks like P-192 might only have a 32-bit portable implementation and P-224 an optimized 64-bit one:

Changes between 1.0.0h and 1.0.1  [14 Mar 2012]
[...]  Add optional 64-bit optimized implementations of elliptic curves NIST-P224, NIST-P256, NIST-P521, with constant-time single point multiplication on typical inputs. [...]

(Note: I haven't actually checked if P-192 is unoptimized. You should do it with your version if you are interested.)
As for why they would optimize P-224 better, it is the minimal acceptable size according to e.g. NIST recommendations. Doesn't make much sense to spend time optimizing something that's recommended not to be used.


Orignal Schnorr Signature vs Discrete logarithmic Schnorr Signature

The first publication using the Discrete Logarithm Problem (DLP) for asymmetric cryptography is in Diffie-Hellman key exchange. The original works in the multiplicative group $\Bbb Z_p^*$, or a typically large subgroup of that.

The first use for signature is ElGamal signature. It uses the same kind of groups, and that makes its signature rather large. It does not use a hash. That and other issues make the original description unsatisfactory; it's more a building block for later signature schemes based on the DLP.

The most notable is the original Schnorr signature. It works in a slightly different group, called Schnorr group, which is a small subgroup of $\Bbb Z_p^*$, with $q$ elements where $q$ is a prime dividing $p-1$, and much less wide/large. That provides what long was (and if we restrict to practice, remains) the shortest known secure signature with appendix (that is, added to the unmodified message): $3b$-bit signature for $b$-bit security. The signature consists of a $b$-bit hash and an integer modulo $q$ over $2b$ bits.

A variant differing only by using a $2b$-bit hash is cleaner from a math standpoint and slightly less difficult to prove secure, thus was much studied, and is stated as being Schnorr signature in many textbooks. That one has a $4b$-bit signature, for a group with a little less than $2^{2b}$ elements. The exposition in the HAC is among these, and it's signature has the hash second, contrary to the original. It is followed by an example with small integers.

The later DSA of FIPS 186 is often seen as a way to work around Schnorr's patent. It is significantly different and more complex. It has $4b$-bit signature.

There are many later signatures also called Schnorr signature, typically with $4b$-bit signature, also based on the DLP, but in an Elliptic-curve group. Study these later!

"original Schnorr signature" unambiguously means a scheme in a Schnorr group, with $3b$-bit signature having one component a $b$-bit hash, the other $2b$-bit coding an integer.
"Schnorr signature" can be any number of things. In introductory material that could be either the original, or the variant where the hash is made $2b$-bit. Other possibilities are too many to enumerate.

Note: "Discrete logarithmic Schnorr Signature" is a naming error. "Logarithmic" is an adjective applying to quantities, mostly continuous. A complexity can be logarithmic, perhaps by extension a count including the bit length of a bitsring, rather not a bitstring like signatures are, not a signature scheme which is a method to obtain and verify a signature. Make that: "Schnorr signature" (thus) based on the Discrete Logarithm Problem (in some group).

Remark: some videos are a great way to learn for their author.


Comparing two values without revealing them

From the last part of your question, I understand that you need order preserving hash function or encryption. Look into this thread
How does order-preserving encryption work?


They are, effectively, the same thing.

PKCS#5 describes a padding that wrote down 8-n padding bytes, but was only valid for DES and RC2.

PKCS#7 described a padding scheme which wrote down k-n bytes for a k-byte block cipher.

Most libraries call the scheme PKCS#7 padding, since that’s the more generalized one (and is defined for AES), but some decided that “7 fixed 5, so credit really goes to 5”.


Blockchain is a decentralized append-only ledger.
If it does not use cryptography to achieve the goal of being append-only, then it would likely not provide any real guarantee of being append-only. It would only provide such a guarantee as long as it was used as prescribed.
For instance, we could create an append-only data structure in a program, and simply program the API to refuse to make any modifications other than appending new data.
However, that does not guarantee that no other modifications could be made to the underlying data, there could exist many ways to work around the provided API to insert/remove/etc. as desired - if you don't use the provided API you can do anything you want to the underlying data. If there is no form of cryptography protecting the integrity of the information, then any peers that attempt to read this data structure have no way of knowing it has been tampered with.
Without cryptography, "append-only" is more of a suggestion/recommendation rather than a matter of technical capability. It is merely inconvenient rather than computationally intractable.


How are security proofs done in ABE Schemes?

Given your answer to my comment, I'll try to give you an intuition about why simulators are used in cryptographic proofs (but as already mentioned, I cannot help much for the particular case of ABE).

Disclaimer: this will be a very (very) informal explanation

Imagin two players, Alice and Bob, performing some cryptographic protocol. Alice has an input $a$, Bob has an input $b$, and both players would like to reveal securely $f(a,b)$ to Alice, for some public function $f$, without revealing anything more. Now, let's say you wish to prove that the protocol is secure for Bob, namely, that Alice cannot learn anything about $b$ by interacting with Bob, except, obviously, for $f(a,b)$. How to show that? Here is the trick: we replace Bob by another entity, which has the two following features:

From the viewpoint of Alice, the behavior of this entity is exactly the same as Bob's behavior. In other words, Alice's view when interacting with Bob is indistinguishable from her view when interacting with this entity. We say that this entity simulates Bob, hence we call it a simulator.
The entity does not know Bob's input at all. We assume that it does only know the output $f(a,b)$ of the protocol.

Now you can already see how the proof goes: when Alice interacts with Bob, from her viewpoint, she could be interacting with the simulator, because she wouldn't be able to see the difference. But this simulator does not even know $b$, it does only know $f(a,b)$. Therefore, Alice cannot learn anything more than $f(a,b)$ from Bob, because if she could, she would be able to tell that she does not play with the simulator (who only knows $f(a,b)$), which she cannot do, according to our first feature.

So, in general, the proof will consist in describing such a simulator, and then showing step by step that its behavior cannot be distinguished from Bob's behavior.

Let us look at a toy example. As you are talking about ABE, which are already quite complex primitive, I assume that you might have already heard of simpler (but still far from trivial) primitives, such as additively homomorphic encryption. But in short, an additively homomorphic encryption scheme $E$ allows you to compute sum and external products inside ciphertexts: from $x,y,E(a),E(b)$, one can compute $E(ax+by)$. Moreover, we say that it is semantically secure, informally, if given $E(x), a, b$, where $x \in \{a,b\}$, no player (without the secret key) can tell whether $x=a$ or $x=b$. Consider the following protocol:

Alice's input: $x,y$.
Bob's input: $a,b$.
Output: Bob learns $ax+by$, Alice learns nothing.
Protocol: Bob sends $E(a),E(b)$, where $E$ is an additively homomorphic encryption scheme for which he knows the secret key. Alice homomorphically compute $E(ax+by)$ and sends this ciphertext back; Bob decrypts it to get $ax+by$.

Let us now show that this protocol is secure for Bob, by showing that Alice learns nothing. We replace Bob by the following simulator: the simulator knows absolutely nothing, pick two random values $a',b'$ and send $E(a'),E(b')$ instead of $E(a),E(b)$ (and does nothing afterward). From the viewpoint of Alice, this is indistinguishable from Bob's behavior, because of the semantic security of the scheme. As this simulator does not even know $a,b$, this shows that Alice cannot learn anything from the protocol.

In this particular, oversimplified case, there are probably more straightforward ways to argue the security. But in more general cases, simulators quickly become unavoidable. Let me try to explain why:

If you want to perform some task securely with a protocol, you can list all the security requirements that you want for this task, and try to prove that your protocol satisfies these requirements. But what if there are requirements that you forgot? Things you did not think of? To avoid this, there is a better solution: describe the task that you want to perform as an ideal functionality For example, for the previous toy example, this could be the following description:

Alice and Bob communicate with the functionality via perfectly secure authenticated channels.
When receiving $(a,b)$ from Bob and $(x,y)$ from Alice, the functionality computes $ax+by$ and sends it to Bob (again, via a secure channel)
The functionality ignores any input which does not have the correct form.

Now, take your protocol, and consider an adversary against this protocol. To show that this protocol is as secure as the ideal functionality that you defined, you will proceed as follows: the adversary will interact with a simulator, which will play the role of an interface between this adversary and the ideal functionality. In other words, the adversary plays the real protocol, but not with an honest player: he plays it with a simulator. This simulator does not know the inputs of the honest players, but can interact with the ideal functionality, playing the role of the adversary. In a way, here is what happen: the simulator tricks the adversary into thinking that he plays the real protocol (by behaving in a way which is indistinguishable from that of honest players), while the adversary is in fact playing against the ideal functionality: the simulator interacts on his behavior with the functionality, and plays the protocol using only the answers he got from this functionality.

If you can exhibit such a simulator, then you have shown the security of your protocol, because whatever the adversary does in the real protocol, he could be interacting with a simulator which does only interface it with the functionality, hence can only learn things that he could have learned by directly playing against the ideal functionality. Recall that this functionality is our definition of a secure protocol for the task we have in mind, so by definition, what an adversary can learn by playing with it is at most what we agree to let him know.

In practice, this require some care in the design of the ideal functionality (using session IDs to avoid attacks in which the adversary plays several versions of the protocol and try to learn things by mixing inputs and outputs, etc). This does also not guarantee that your protocol will remain secure if composed with other protocol (this require a stronger model).

I hope this gave you an intuition. If now you want more practical knowledge on how to do cryptographic proofs using simulation, I agree with user94293 that the recent tutorial of professor Lindell on this topic should be an excellent starting point (I have to admit I have not read it yet, but it seems safe to assume that it'll be a good tutorial, given its author).

If you have any question, please don't hesitate. If anyone wants to point out parts of my explanations that are prohibitively informal and should be removed/rewritten, I accept it too :)


Why use two affine transformations in Multivariate Cryptography?

In the majority of multivariate cryptographic schemes (MQ) the encryption/signature function $E$ is a composition of secret affine invertible transformations $A,B$ and a nonlinear transformation $P$ (can be secret or public):
$$
E = B\circ P\circ A
$$

$P$ is typically invertible, and the goal of the scheme is to make $E$ non-invertible even though it is fully exposed to an attacker as a polynomial.

The mere fact that $P$ is invertible explains why we need both $A$ and $B$. Indeed, suppose that $A$ is missing, then in the equation
$$
E(x) = B(P(x))
$$
we substitute
$$
x = P^{-1}(y)
$$
and obtain
$$
E(P^{-1}(y)) = B(y),
$$
so we know $B$ and are able to invert $B$.

This is the simplest case; there are other variants, where $P$ is secret, or its inverse is not available in the closed form, or some of the output polynomials are dropped (OK for signatures). In some of these variants both $A$ and $B$ are still required as otherwise you could invert the scheme just by looking at the structure of the polynomial and comparing monomials of $E$ with monomials of $P$. However, say, if $P$ is secret, then both $A$ and $B$ can be considered as part of $P$.


What are the vulnerabilities of this OTP-like system?

I've read that a OTP is only perfectly secure if the key is perfectly random, and the pad is never reused.

But you've left out the most important condition: the key space must be as large as the message space.

  If you encrypt documents using two keys, where one is random but stays constant for some period of time, and the other is only pseudo-random but unique to each message, is the security of the OTP better or worse than if you used only one key or the other?

You don't specify how the keys are used to encrypt documents, but since you've been talking about one-time pads I will assume the keys are as long as the documents and the encryption works by XOR.

Encrypting messages with distinct pseudorandom key streams is called a stream cipher, and is already secure if the pseudorandom stream generator used is secure and the same keystream is not used twice.  So we can refactor your idea into two components, applied in sequence:

Encrypt the documents with a stream cipher, applying a different keystream to each document;
XOR each ciphertext with a the same true random long-term key.

This has to be at least as secure as the stream cipher is; even if the adversary knows the long-term key for step #2, they'd still have to break the stream cipher.
 This is theoretically less secure than the OTP's "perfect security," but can be plenty secure in practice; my browser session to this site, for example, is protected by such a stream cipher.

Now, the question is whether the addition of the reused long-term true random key enhances the security in any way.  The answer is no, because an adversary who can break the stream cipher is able to exploit the reuse of the long-term key to break the composite system.  Notating the long-term key as $K_L$, the pseudorandom key streams as $K_1, K_2$, the plaintexts as $P_1, P_2$ and the ciphertexts as $C_1, C_2$, the encryptions satisfy these equations (where $\oplus$ is bitwise XOR):

$$
\begin{align}
C_1 &= P_1 \oplus K_1 \oplus K_L \\
C_2 &= P_2 \oplus K_2 \oplus K_L
\end{align}
$$

Solving both equations for $K_L$:

$$
\begin{align}
K_L &= P_1 \oplus K_1 \oplus C_1 \\
K_L &= P_2 \oplus K_2 \oplus C_2
\end{align}
$$

By transitivity of equality:

$$
\begin{align}
P_1 \oplus K_1 \oplus C_1 &= P_2 \oplus K_2 \oplus C_2
\end{align}
$$

And now I can solve for the XOR of the two plaintexts:

$$
\begin{align}
P_1 \oplus P_2 &= K_1 \oplus C_1 \oplus K_2 \oplus C_2
\end{align}
$$

This is significant, because obtaining the XOR of two plaintexts is the basis for the standard two-time pad attacks:

How does one attack a two-time pad (i.e. one time pad with key reuse)?
Many time pad attack
http://www.juliansanchez.com/2012/07/06/a-friday-puzzler-un-xoring-two-plaintexts/

$K_1$ and $K_2$ are pseudorandom keystreams, I can use a brute force attack to enumerate possible values for them, and use statistics on the implied values $P_1 \oplus P_2$ to infer whether I've hit the right key.  And then when I've found the value $P_1 \oplus P_2$, I can try the two-time pad attacks on it.

So your proposal's security is more or less the same as just using the stream cipher.  Lesson: just use the stream cipher.


Perfect Forward Secrecy in PGP/asynchronous email

Keeping a complete history of messages/keys

Perfect forward secrecy is great to protect "stream kind" of messages, but that does not really fit what OpenPGP is (mostly) used for. Often, OpenPGP messages are sent and read from different machines, at different times, in different order. While OTR (offering perfect forward secrecy) does not rely on external mailboxes (like IMAP servers) holding messages for long periods of times, mails often are kept a long period of time, and you might want to store them in their original, encrypted form. Perfect forward secrecy does require to have a unique store of a message (or at least key) history, something OpenPGP does not require. And storing such a history would again partially counterfeit the benefits of perfect forward secrecy, anyway.

Perfect forward secrecy might simply have been too young

Finally, OpenPGP had its first revisions pretty much at the same time perfect forward secrecy was discussed first. A likely (additional) reason is perfect forward secrecy wasn't on Phil Zimmerman's scope at all at that time.


Hash function and Digital Encryption Algorithm

One reason ECDSA (the elliptic curve variant of DSA used by Bitcoin) first hashes data is to make forging signatures harder. Consider the first two steps in ECDSA:

  Calculate $e = \text{HASH}(m)$, where $\text{HASH}$ is a cryptographic hash function, such as SHA-2.
  Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$is the bit length of the group order $n$.

Suppose instead that $z$ is the $L_n$ leftmost bits of the message $m$ instead. In that case the resulting signature is a valid signature for any message $m$ with the same $L_n$ leftmost bits. In the case of ECDSA in bitcoin $L_n = 256$, or 32 bytes (which would be 32 characters in ASCII encoding). This gives a lot of possible ways to forge a message as only 32 characters need to be the same for the signature to be valid.

The way to avoid this would be use all the bits of the message in the signature, but with arbitrarily large messages this can cause huge performance issues as we're now performing public key crypto on potentially much larger amounts of data.

So the idea of using the hash function is to take an arbitrarily large amount of data and transform it into a much smaller amount of data before performing any of the expensive operations on it. But we also need this to happen in a way such that it is hard, given message $m_1$, to find another message $m_2$ that produces the same hash output. Otherwise we again have the case that the signature for $m_1$ is also valid for $m_2$. The property of cryptographic hash functions (which SHA-2 falls under) known as (second) pre-image resistance gives us this property.


Some brief thoughts:

Shared secret Generation:
$$s=E_a(B)=E_b(A)$$
The shared secret is generated by encrypting the other users public key with your private key. This is effectively an ECDH step, which is very reasonable, and one of the key aims of C25519$^{[1]}$.

Key Generation:
$$s_0=\mathrm{SHA256}(s); s_i=\mathrm{SHA256}(s_{i-1})$$
First, using the definition above, they generate seeds. This doesn't seem an unreasonable way of expanding one seed into many.
$$k_n = \mathrm{SHA256}(\overline{s_n})$$
Yes, I'm happy that the $k_n$ should look pretty random.

Xor combinator:
This isn't at all unreasonable, and most stream-ciphers use this technique for combining their stream with the plaintext.

Overall?
Assuming the relation required in the first step holds, which I'm unsure and sceptical about, then first impressions are that this scheme should be ok. At the end of the day it's basically using ecdh to seed a $\mathrm{SHA256}$-based stream cipher. Cryptographically, this means it will at best have the security bounds from the weakest of those primitives. Whilst this is certainly not genuinely 'unbreakable', it should be computationally secure. However, there are some far more significant issues with it that won't be addressed by 'is it secure'? I'll note some of them now...

Key reuse
As noted by the original author, this scheme only generates a single key-stream, seeded by the two public keys through the ECDH step. The dangers of reusing an xor keystream are severe - it leaks the xor of the plaintexts, which is often sufficient to allow a total break:
$$c_a=m_a\oplus K;c_b=m_b\oplus K \implies c_a\oplus c_b = m_a\oplus m_b$$
This could be resolved by adding a nonce to the original step, which is arguably the biggest issue of the scheme. That is,
$$s_0=\mathrm{SHA256}(s||N)$$
Where $N$ is a nonce, although it does not have to be unpredictable.

Why should I care?
This is the biggest issue with most homebrew schemes. Unless a scheme can demonstrate some advantage over the other schemes in existence, then why on earth wouldn't I just use those? In this case, it won't be particularly quick given the number of SHA calls made, won't be very nice to parellelise due to the recursive nature by which the stream is generated, and after all that it's just an xor-based stream cipher. See this question for why you should always think at least 3$^{[1]}$ times before using an encryption algorithm rather than an authenticated encryption algorithm.

[1]: Thanks to DrLecter for clarification on this point.

[2]: In the old days, people used to be told "think twice before doing $x$". However, as we are all aware, lots of people still did $x$. As such, I'm pushing for raising the number of "think's" required. Obviously as a cryptographer I'd like to go for at least 64-bit security, but for now 3 will have to do.


A NIST P-256 secret key (for ECDH or ECDSA) represents any scalar modulo $\ell$ for $$\ell = 2^{256} - 432420386565659656852420866394968145599,$$ whereas an X25519 secret key represents an integer multiple of 8 between $2^{254}$ and $2^{255}$, interpreted as a scalar modulo $8 p_1$ for $$p_1 = 2^{252}  + 27742317777372353535851937790883648493.$$  In both cases, the secret key should be chosen uniformly at random from all possibilities, so that every possibility has equal probability.  Here $\ell$ and $p_1$, both large primes, are the orders of the standard base points on the respective curves.

The NIST recommends, in FIPS 186-4 Appendix B.4 pp. 61–64, that you either generate 320 bits uniformly at random, reduce modulo $\ell - 1$, and add $1$; or do rejection sampling, drawing 256-bit $n$ and starting over unless $0 < n < \ell$.  These methods keep the modulo bias respectively either small or nonexistent, and avoid $n = 0$.  The benefit of this negligible, so I would just accept the modulo bias of picking 256 bits uniformly at random and performing a single conditional subtraction, losing less than a single bit of theoretical security.  But if you're using NIST P-256, you're probably slave to compliance with government bureaucracy standards, so you should probably follow the letter of the standard.

Technical details, or, why is it different for (say) ECDH over NIST P-256 and X25519?

The curve group NIST P-256 has prime order $\ell$, and the standard base point generates the entire group, so even if you reveal $[n]P$ for attacker-controlled points $P$ where $n$ is your secret scalar, there are no active small-subgroup attacks possible on NIST P-256; and although the quadratic twist of NIST P-256 does not have prime order, it happens to have the modest cofactor $34905 = 3 \cdot 5 \cdot 13 \cdot 179$ which confers a degree of twist security.  Caveat: If you foolishly handle uncompressed $(x, y)$ inputs, twist security is not enough; you must still validate them to thwart invalid-curve attacks.

In contrast, the curve group Curve25519 has composite order $8 p_1$, and its twist has composite order $4 p_2$ for another large prime $p_2$, while the standard base point has order $p_1$.  So to thwart small-subgroup and twist attacks without requiring point validation, the secret scalar $n$ is always chosen to be congruent to zero modulo the cofactor 8 and the twist cofactor 4, and public keys are transmitted as $x$ coordinates only so the only possible invalid curve is the quadratic twist.


I'm not endorsing your encryption scheme (because frankly it sounds dubious), but libsodium's Public-key authenticated encryption sounds like what you're looking for. It uses Curve25519 internally, which should be less resource-intensive than RSA. There are also bindings for many languages available.


Vector dot product in Microsoft SEAL using the CKKS scheme

As suggested by Hilder Vitor Lima Pereira in the comments and KyoohyungHan on Github in the issue https://github.com/microsoft/SEAL/issues/138, it is possible to sum the elements with rotations:

  For example,
  {1, 2, 3, 4} is encrypted in a ciphertext.
  You can get encrypted {3, 4, 1, 2} using homomorphic rotation by index 2.
  With homomorphic addition, you have encrypted {4, 6, 4, 6}.
  After that, you can get encrypted {6, 4, 6, 4} using homomorphic rotation by index 1.
  Finally, you have encrypted {10, 10, 10, 10} with homomorphic addition which is the sum of the element in a ciphertext.


Do I need a salt for Scrypt if the data is client-side?

Can you guarantee that the users are going to use high-strength passwords like dicewire? What if they are using simple passwords? Are they going to sue you when they are hacked and their data exposed? Lots of questions?
Consider that all of your users are hacked due to a bug in your application, then the attackers can execute a batch attack, too. Using salts can prevent this batch attack.
Using salt is the countermeasure to the rainbow tables where applicable. Therefore you limit them to single searching. In this case, two vectors remain

How good are the users' passwords?
How much can the password hashing algorithm slow the attacker?

The answer to the first question has a human side. You can test the quality of passwords up to some point and reject if lower. Teach your users to use the dicewire. Not hard to learn, see XKCD 936
The second question has a better answer as the Argon2id is the best choice. You can parametrize;

Number of iterations $t$, affecting the time cost.
Size of memory used $m$, affecting the memory cost.
Number of threads $h$, affecting the degree of parallelism.

This parameter must be tuned according to your target systems.
Therefore you can limit the attackers to use Massive GPU/ASIC parallel search mostly single case and with the timing, you can cripple their effort.
The recommendation is to use the salt, it is not hard to generate one by using /dev/urandom or similar methods.
And remember that the entropy and output cannot exceed the entropy of the input. Make sure that users have high-strength passwords.


Is it safe to hold key file's hash in application

The only danger is that the application now holds a fingerprint of your key. Thus enables the possibility to do some attacks, like bruteforce, and something to check against. And so it really comes down to the "same old question" as of how to keep your password-storage safe. If the key-file is a large one and somewhat random, then bruteforce is most certainly out of the feasible picture, however if it's not or the key-file is a common file or just a text-file containing a common word, the attack methods doesn't differ that much from what every webapp developer is trying to secure.


If $$x \times \frac{1}{x} = 1$$

then $$g^{x\frac{1}{x}} = g^1 = g$$

Alternatively, you could denote $\frac{1}{x}$ as $x^{-1}$.

In the context of cryptography, $\frac{1}{x}$ will usually mean the modular multiplicative inverse of $x$, because cryptography usually works with modular arithmetic.

With modular arithmetic, the way to evaluate the division operation is to multiply by the inverse. For example: $$3 \times 7 \equiv 10 \bmod 11\\10 \times 4 \equiv 7 \bmod 11$$

You wouldn't be able to use the traditional division operation to divide $10$ by $3$ to obtain $7$. But you can use multiplication by the inverse of $3$ (which happens to be $4$ here) to obtain the correct result. So we could also denote the above by: $$10 \times 3^{-1} \equiv 7 \bmod 11$$ or equivalently: $$10 \times \frac{1}{3} \equiv 7 \bmod 11$$

So in general, $\frac{y}{x}$ means $y \times x^{-1}$.

  Q2: What is elliptic curve notation of the rational multiplicators? $(1/x)$G ?

What you've written looks plausible, but it wouldn't surprise me if they tended to use $x^{-1}G$ instead.*

Either way you denote it, people will probably understand the intent - especially if you provide helpful definitions for your notation.

* I'm not well-versed in literature on elliptic curves, so I'll leave it to someone else to confirm/deny that.


What is the sponge construction in simple terms?

I find that the following image from Wikipedia, though perhaps a bit too technical for your purposes, is still helpful with a little explanation:

Essentially, a function $f$ is used repeatedly in two phases, absorbing and squeezing.
In the absorbing phase, small chunks of the input data are mixed into the beginning of the buffer using XORs (using the variables from the image: $r \oplus P_i$). This updated buffer value is then passed through $f$ and the process continues.  With each step a small amount of input date (the bit-length of $r$) is "absorbed" into the buffer using $f$ to semi-randomize the entire buffer.
In the squeezing phase, the same process is repeated but instead of XOR-ing the first $r$ bits with data, they are extracted as the next $r$ bits of the output.
tl;dr: The input is mixed into a buffer in small chucks in between phases where a buffer is randomized, then the buffer is randomized repeatedly while small chucks of it are taken as output.
For more detailed information, see this webpage and this paper by the Keccak team.

It feels worth calling out that your purposes for recommending SHA-3 over SHA-2 may be more important.  Does their application of SHA-2 suffer from the possibility of length-extension attacks?  Are there other benefits of SHA-3 that you could benefit from?  As mentioned here the situation isn't really "move to SHA-3 because it's a better version of SHA-2."
It's possible you're already aware of this, but your client may not be.  As such, a simple description of how it works may not really be all they need, even if that's all they're asking for.


Can we replace IV increasing from addition to XOR in CTR mode?

A fairly common way to implement CTR mode is to construct the IV by taking a per-message nonce of, say, 96 bits and appending 32 zero bits to the right of it.  These 32 least-significant bits are then incremented by one for each cipher block in the message.

This method has the useful property that if the nonces are never reused, and if no message contains more than 232 cipher blocks, then the counter values can be guaranteed to never repeat.

For your purposes, another useful feature of this method is that, as long as the above conditions hold (i.e. as long as $i \le 2^{32}$ and the lowest 32 bits of the IV are all zero), then $IV + (i-1) = IV \oplus (i-1)$.  Thus, it makes no difference at all whether you combine the IV and the block counter using addition or XOR, or even just concatenate the nonce directly with the 32-bit block counter.


As mentioned by j.p., the original attack has been (quite significantly) improved in 2012 and some great tutorials are available online, often demonstrated with example.

If you want a more exhaustive list of test vectors, I suggest you take a look at Project Wycheproof, a tool developed by members of Google Security Team, designed to find vulnerabilities in cryptographic libraries. The idea behind this project is to use a large database of test vectors allowing to verify primitives conformance and check if they are vulnerable to some well known attacks.

You can find test vectors for RSA PKCS#1v1.5 for different key size (2048, 3072, 4096).

One of the maintainer of this project is Daniel Bleichenbacher himself (also Thai Duong, Emilia Kasper and Quan Nguyen), so test vectors should be valid!


Can Shannon's proof be applied to all ciphers

Can his proof be applied to positional ciphers.

Shannon's proof requires that there be at least as many possible keys as possible plaintexts; unless your positional cipher has that property, then no, it cannot.

(I'm not sure what you're referring to as a 'position cipher' - would that be a transposition cipher?)


What requirements would lead to the development of a new security protocol?

There are plenty of security issues which are not yet solved with widely used protocols:

At the low level there are reflection/amplification attacks. DNS (and in particular DNSSEC) is known to be vulnerable to this. DNS cookies have only recently been standardized, and is not yet widely deployed. Other protocols are lacking in this area as well.
Logins are still performed in ways that allow servers to see passwords in clear. Rather than fixing this at the protocol layer we have tried to educate users to use different passwords for all sites. It is still a possibility that improvements in this area may become popular.
Anonymity is not very well protected by current protocols. At the moment there are big players actively trying to undermine users' anonymity. New protocols might try to address this.
Confidentiality could be protected better with opportunistic encryption. Opportunistic encryption where identification of the peer being communicated with is optional can improve security compared to a setting in which communication is done unencrypted due to the complexities of key management.


Would this raise the security margin and allow use of 128-bit signatures for exactly 128-bit (classical) security?

Yes and no - yes, it would raise the security margin somewhat, but not to the full "128 bit classical security level".

As for why it wouldn't raise it to the full 128 bit level, well, for two reasons:

For one, the attacker could take a guess at S0, and compute TRUNCATE-128(HMAC(S0,i||"0")) and see if it happens to be the value in the public key; that can happen for two reasons:

His guess for S0 happens to be correct; if S0 is 128 bits, this happens with probability $2^{-128}$
His guess for S0 is wrong, but TRUNCATE-128(HMAC(S0,i||"0")) just happens to be the correct value anyways; if we model HMAC as a random function, then this happens with probability $2^{-128}$

Hence, the probability of either of these happening is approximately $2^{-127}$, giving us a security level that is slightly less than 128 bits.

For another, let us assume that the adversary has $M$ public key, messages and signatures (each message being $N$ bits); what he can do is try to guess S0 for the first bit of each private key; if he succeeds (for any message with a 1 first bit, hence S1 was used), then he can generate that forgery for that public key.  If we assume that the goal of the adversary is to generate a forgery for one of the public keys (and he doesn't care which), then the expected work effort is $2^{-128} / (N/2)$ (with the $N/2$ factor being the approximate messages with a 0 first bit); for large $N$ this is obviously a nontrivial decrease in security.

Now, the obvious defense against the first observation is to increase the size of S0 and S1 (which will cause an increase in the size of a signature).  And, against the second observation, you need to stir in some per-public-key distinguisher (along with the 'bit position' which your proposal does) somehow into the one-way-function.  If you look at the current standard hash based signature methods (LMS, XMSS, Sphincs+), they do that (using various techniques to stir things in - none of them use HMAC).


Is it possible to have a PAdES signature with only a timestamp?

Short answer: No. If you look at the PAdES specification, it is clear that each profile relies on at least one normal signature.

Longer answer: A timestamp and a signature serve different purposes. While a trusted timestamp does ensure the integrity of the data (alongside a notAfter date) it does not say anything about the authenticity of the the document itself, anyone can request a timestamp for any document.

The purpose of a normal signature (and PAdES is a signature standard) is to authenticate the author or issuer of a document.


Should Bob trust a certificate issued by delegated party?

This very much depends on what you mean by

  Bob trusts Y.

If Y is a root CA and Bob "trusts" them to do their job properly, then yes he would trust Alice's key. This is because the job of a root CA is exactly discerning whether a subordinate CA (in this case X) should be trusted to in turn do their job: I.e., check people's identity and sign their public keys if and only if they can be certain beyond reasonable doubt that the person presenting the public key is in possession of the corresponding secret key and that they are the entity they claim to be.

If on the other hand Y is just some random friend ob Bob, whom he trusts in the sense that they are sure that the key they is theirs and they probably genuinely believe whatever it is they signed with that key, then no, this is no basis to trust Alice's key. In fact in general Bob has no way of telling in what context and why Y ever signed X's key.

Which means that we lack the necessary information to answer the question, because the statement "Bob trusts Y." is underspecified.


Amateur question: Constant two way cryptography

Two reasons why cryptographic algorithm often behaves as you observe (non-deterministically):

When the objective is to encipher some secret, it is necessary for security in many scenario. Otherwise, an observation post sending its report which usually is "Nothing in sight anywhere" would always send the same cryptogram in this situation, allowing to discriminate this usual case from "Elbonian vessels by south".
Things get worse with public-key encryption: if the encryption was deterministic, it would be possible to check a guess of the message; thus knowing that the message is the name of someone in class, someone with the class roll could break the encryption.
In some other applications, some randomness is necessary for security, or strengthens it, because it makes internal values unknown or unpredictable to an adversary. An example is signature: many signature schemes (including DSA, ECDSA, and to a lesser degree RSASSA-PSS), rely on a random value drawn by the signer (that must imperatively remain secret in [EC]DSA), and influence the result.

Deterministic encryption can be done, but as stated above that tends to be a defect (in particular it prevents from meeting the standard academic goal of CPA security), thus this is uncommon.

I looks like what you are looking for is deterministic password-based encryption with salt. This could be done as follows:

turn password and salt into an AES key using a Password-Based Key Derivation function like PBFDF2, Bcrypt, or Scrypt (these are deterministic)
encipher the result using AES in CBC mode with the IV implicit and set to zero, and some standard byte padding.
move the last 16 bytes of the ciphertext in the front, and again encipher the result using AES in CBC mode with the IV implicit and set to zero (no byte padding is needed this time).

For decryption:

turn password and salt into an AES key as in encryption
decipher the ciphertext using AES in CBC mode with the IV implicit and set to zero, and move the first 16 bytes of the deciphered plaintext to the end
decipher the ciphertext using AES in CBC mode with the IV implicit and set to zero, and undo the byte padding.

The double encryption gives some level of insurance that plaintext with the same beginning won't be recognizable as such from the ciphertext.


By the modern definition of a cipher, it must be possible to encipher several messages with the same secret key. That's also a practical necessity, due to the difficulty of securely establishing a shared secret key. That issue is solved with the nonce, which is not secret, and can be transferred as part of the ciphertext (typically: at the beginning).

Without nonce, or if the nonce repeats, the keystream would repeat, and that would allow breaking the cipher, e.g. with a single known plaintext.

Because the nonce is not secret, communicating the nonce is simpler than securely communicating the key. Altering the nonce would alter the deciphered message, but a generic stream cipher is not supposed to allow detection of alterations anyway.


What will be appropriate AES padding characters?

But is it the right way?

There are various padding styles for this. The padding must be removed correctly and uniquely. For example, the all-zero padding may remove your actual information. Some of the padding schemes;

append 1 then all zeros
ciphertext stealing padding.
PKCS#7 padding defined in rfc 2898

  For such algorithms, the method shall be to pad the input at the trailing end with k - (l mod k) octets all having value k - (l mod k), where l is the length of the input.

for example;

  ......01
  ....0202
  ..030303

The right way, indeed using a mode like CTR so that you will not need padding. The paddings have security issues like padding oracle attacks in CBC mode.

  Can somebody crack my key, by sending empty Strings?

What is an empty string, all-zero? Why do you need to send all-zero? What is the Mode of operation? There are lots of questions about this. That really depends on your application. For example, it may reveal that you send it again if you are using ECB mode - don't use it. If you use a semantically secure mode you can be fine, however, keep in mind that each mode has its own problems. For example; in CBC mode the nonce must be unpredictable, In GCM, CTR the IV must be unique.

Use modern encryption modes like Authenticated Encryption (AE). AE will provide you Confidentiality, Integrity, and Authentication. AE examples are AES-GCM and ChaCha20-Poly1305 which are in TLS 1.3. AES-GCM internally uses CTR mode that no need a padding scheme.


Remember when you solved systems of linear equations in school? This is essentially the same. You just swap out $K=\mathbb R$ for $K=\mathbb F_{601}$ which allows you to essentially do the same things as with $\mathbb R$, even if it is a little bit less inttuitive.

First too $\mathbb F_{601}$, as $p=601$ is prime, this is what is called a field. Essentially instead of doing normal addition, you do normal addition first and then reduce the result $\bmod p$ (ie take the remainder after integer division by $p$), same for subtraction and multiplication. Exponentiation works the same (as it is just repeated multiplication) and you can use the identity $1/a:=a^{p-2}\bmod p$. Now you can view your problem to solve the following equation over this field:

$$\begin{pmatrix}
m_1&1\\
m_2&1
\end{pmatrix}
\cdot
\begin{pmatrix}
k_1\\k_2
\end{pmatrix}
=
\begin{pmatrix}
c_1\\c_2
\end{pmatrix}$$

Obviously you will bring the matrix into triangle form (by subtracting the first line from the second) resulting in
$$\begin{pmatrix}
m_1&1\\
m_2-m_1&0
\end{pmatrix}
\cdot
\begin{pmatrix}
k_1\\k_2
\end{pmatrix}
=
\begin{pmatrix}
c_1\\c_2-c_1
\end{pmatrix}$$

Implying that $k_1=\frac{c_2-c_1}{m_2-m_1}$, which is indeed expected if we consider the cipher to be a linear function like those you learned in school. Now it immediately follows that $k_1\cdot m_1+k_2=c_1\iff k_2=c_1-k_1\cdot m_1$ and you have thus successfully recovered the full key $\begin{pmatrix}
k_1\\k_2
\end{pmatrix}$.

I'll leave it as an exercise to plug-in the numbers and recover the concrete values using a calculator or some online tool.


Generating a valid signature on El-Gamal without knowing the private key

First, I think you have a typo in your question since in the original article $s = (M - x y)(r^{-1}) \mod p-1$, and not $s = (M - x^y)(r^{-1}) \mod p-1$.

Knowing that, then we can construct $s_2$ from $s, r, M$ and $M_2$:

$s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}$

A valid signature for $M_2$ is then $(y, s_2)$

It is easy to see that this signature is valid:

$y^{s_2} b^y = (g^r)^{(M_2 - x y)r^{-1}} (g^x)^y = g^{M_2 - x y} g^{x y} = g^{M_2}$


Separate Read and Write Keys in TLS Key Material

Well, whether it would be safe to use the same keys to encrypt and to decrypt depends a great deal on the ciphersuite.  In particular, TLS supports ciphersuites where it would cause a serious security problem; hence TLS was designed to have different keys in two directions (so that it could use those ciphersuites safely).

In particular, the RC4 encryption algorithm would be insecure if the same key was used in both directions.  This is because, if both directions used the same key, then the same keystream would be used to encrypt both sides; that means if the attacker heard both sides of the communication, and exclusive-or'ed the corresponding bytes from both directions, he would get the exclusive-or of the two plaintexts.  This is a serious security problem; at the simplest level, if he could guess one side's half of the communication, he can recover the other side.

For one trivial example, consider a TLS-protected communication where the server sent the fixed string "Enter password:" (or the XML equivalent), and the client then sent the password, well, the attacker could exclusive or the two together, and recover the password.

Obviously, this is not acceptable.  By using two different keys for the two directions, both directions are encrypted using independent keystreams, and so the attacker cannot do this.


Scalar Multiplication for Elliptic Curve

On standard way to compute scalar multiplication is to use Double-and-add algorithm:

The idea is to take the binary representation of your scalar $b = b_0 ... b_m$in your case $b = 3$ gives  $b_0b_1 = 11$.

First you initialize your result $Q$ with $0$.

Then for each increasing bit index $i$, you set $Q = 2Q$ (computed with the doubling formula) and if $b_i = 1$ you set $Q = Q + P$ (computed with the addition formula).

In your example you have:

$Q = 0$
$Q = 2Q = 0$, $b_0 = 1$ then $Q = Q + P = P$
$Q = 2*Q = 2P$, $b_1 = 1$ then $Q = Q + P = 3P$

It is the generalization of user94293 comment. If your implementation is critical, be careful since the algorithm above is not time constant. You may prefer the Montgomery ladder in critical cases.


In this example, which is a premaster secret, and which is a master secret?

The protocol outlined in the question is Diffie-Hellman key exchange with artificially small $p$. Beware that one thing is misleading in this exposition: for $p$ of practical interest, that is of some thousand(s) bits, when computing $g^a\bmod p$, one does not computes $g^a$ then reduce $\bmod p$ as shown, because $g^a$ is too huge. Instead, one reduces $\bmod p$ (at least) after each multiplication. Approximately ${3\over 2}\cdot\log_2a$ modular multiplications are performed in the simplest algorithm used in practice.

Thanks to poncho's comment, we know that the terms premaster secret and master secret are used in TLS, as:

  8.1. Computing the Master Secret

  For all key exchange methods, the same algorithm is used to convert
  the pre_master_secret into the master_secret.  The pre_master_secret
  should be deleted from memory once the master_secret has been
  computed.

  master_secret = PRF(pre_master_secret, "master secret",
                      ClientHello.random + ServerHello.random)
                      [0..47];

  The master secret is always exactly 48 bytes in length.  The length
  of the premaster secret will vary depending on key exchange method.

  8.1.1. RSA

  When RSA is used for server authentication and key exchange, a 48-
  byte pre_master_secret is generated by the client, encrypted under
  the server's public key, and sent to the server.  The server uses its
  private key to decrypt the pre_master_secret.  Both parties then
  convert the pre_master_secret into the master_secret, as specified
  above.

  8.1.2. Diffie-Hellman

  A conventional Diffie-Hellman computation is performed.  The
  negotiated key (Z) is used as the pre_master_secret, and is converted
  into the master_secret, as specified above.  Leading bytes of Z that
  contain all zero bits are stripped before it is used as the
  pre_master_secret.

  Note: Diffie-Hellman parameters are specified by the server and may
  be either ephemeral or contained within the server's certificate.

Thus, in the protocol of the question, which can be seen as a reduced example of Diffie-Hellman as it would be used in TLS, $s$ is the pre_master_secret; the master_secret would be derived from it.


Why we can't implement AES 512 key size?

We can't implement "AES 512 key size" because AES is defined for key sizes $k\in\{128,192,256\}$ bits only¹; much like, by definition, we can't make a bicycle with 3 wheels.
I see no reason why we would want to define an AES variant with 512-bit key size (since AES-128 is safe enough for anything foreseeable most current applications except those that require huge security margins, AES-192 is more than enough for the most demanding ones, and AES-256 more than overkill³). However we could define an AES variant with 512-bit key size. If we stick to the 128-bit block size, the two choices we have to make are:

How many rounds we should use; since the number of rounds in standard AES is $r=k/32+6$, anything even from $r=14$ (for performance and subkeys space comparable to AES-256, at the expense of resistance to related-key attacks much lower than AES-256) to $r=24$ (as a paranoia damper) seems justifiable.
How we would generate the $4(r+1)$ 32-bit words forming the $(r+1)$ 128-bit round subkeys out of the 512-bit key. By analogy with standard AES, the first 16 such words should be right from the key. I won't venture further.

The question seems to have been motivated by a "paper" titled AES Algorithm Using 512 Bit Key Implementation for Secure Communication (I'll charitably not mention the authors) which presents an AES variation with 512-bit key and block size, best summarized as: AES-128 with $8^2$ bytes wherever the original has $4^2$, an idea that at least could be made to work. However the "paper" has blatant issues:

The "paper" present as "drawback" of AES-256 (which uses 14 rounds) that a 9-round variant is vulnerable to a related-key attack with $2^{224}$ works; yet it introduces a 10-round AES variant without the slightest justification that it will resist similar attacks.
The aim is "higher level of security throughput", without attempt of definition; and doing so "without increasing overall design area as compared to the original 128 bit AES", while the state of the proposed algorithm (thus number of D latches in an hardware implementation) is 4 times that of AES-128, for both key and data.
The drawing of the byte substitution step clearly shows a 4x4 grid of bytes holding "an array of 64 bytes".
There is the same issue in the "shift row" step (to be read as ShiftRows), and the drawing gets confusing, since the line with $s_3$ is shown right-rotated by 1 step, when the intend is that it is left-rotated by 3 steps.
Proof that the "Mix Column" step (to be read as MixColumns) is reversible, which is necessary for decryption to be possible, is alluded to only by dumping an alleged inverse of the polynomial used in MixColumns, without derivation.
On closer inspection, the matrix given for MixColumns does not correspond to the polynomial stated for MixColumns per the conventions used in the real AES; and the alleged inverse polynomial can not match either, according to any convention, for it contains too many terms with multiplication by $\{01\}$, so that decryption using it won't work. I conjecture that this would-be inverse polynomial simply has its four terms of even degree taken from the polynomial used for AES's InvMixColumns (within a reflexion); and other terms set to $\{01\}$, because there are a lot of these in the direct polynomial.
The number of rounds in the 512-bit AES variant is set to 10 with the sole justification that there are "ten AES rounds", without reference to which of the three AES ciphers that applies to.
The round index is variably $I$ or $i$ including in the same equation.
The first round constant probably has a typo.
But there's no test vector to settle that.
Performance is compared against AES-128, stated as encrypting "128 bytes" in "30-50 Seconds" on an unspecified platform; which (if we ignore the spurious capital S) is about $2^{26}$ times slower than routinely achieved by a single core of a modern CPU with AES-NI.
The 512-bit AES variant is stated as encrypting the same "128 bytes" in "20-40 Seconds" yet has "230%" the throughput; this creatively redefines benchmarking.
It is stated that the "Processor Required" is "Less" than for regular AES, with no attempt to evaluate the number of operations or memory accesses per byte encrypted; indeed this is about the same as in AES-128 for all steps except MixColumns, where there is significantly more work per byte (twice as many columns, each requiring multiplication by a matrix with twice as many raws and twice as many columns, thus about 8 times more work for 4 times as many bytes, thus about twice more work per byte; admittedly, the proportion of entries in the matrix that hold a $\{01\}$ is higher, but this only partially lowers that increase in work).
Proceedings is spelled "Pro-ceding's".
Several entries in the citations are to equally vacuous papers published in caricatures of scientific journals.
Two citations ([1] and [11]) are to other papers about AES-512, yet are not mentioned in the Existing Work section.
Citation [1] is a 2010 paper strikingly similar to the 2014 paper itself, including having nearly the same title ("Implemented" rather than "Implementation"), yet other authors (and even more mistakes and vacuity).
Citation [11] was published in the proceedings of an IAS 2011 conference with enough relation to the IEEE to be on their website and use their logo (notice that this IAS stands for Information Assurance and Security, not IEEE's Industry Applications Society). A look at this online version shows it is strikingly similar to the 2014 article (including same erroneous polynomials, typo in first round constant, and 230% improvement), with different authors. I vote this 2011 paper as poor (especially on justification of security and misleading benchmark), but the least objectionable of the three.
The numbers for references in the text are often from text cut and pasted from the 2010 paper, rather than related to the numbering of the references given in the end.
The paper is published in the "Best Peer-Reviewed Journal", which also brags being an "ISO 3297:2007 Certified Organization" (when a cursory look at the summary of this standard shows that it is about numbering publications, not review of their content). That journal also boasts an impact factor of 7.488; this is telling of how reliable a measure of seriousness the impact factor is.

¹ Quoting FIPS 197:

This standard specifies the Rijndael² algorithm, a symmetric block cipher that can process data blocks of 128 bits, using cipher keys with lengths of 128, 192, and 256 bits.

² The Rijndael block cipher has the same 256-bit key limitation:

the block length and the key length can be independently specified to any multiple of 32 bits, with a minimum of 128 bits, and a maximum of 256 bits.

³ By most accounts, 256-bit key is safe including against hypothetical quantum computers usable for cryptanalysis. If we also want 256-bit blocks, Rijndael allows that.


which en/decrypt algorithm should use for small byte array that result have same length

result have same length as input array

If you insist on this, then you must lose some security.

At the very least, there's no room for a given value to be encrypted in two different ways. This means that an attacker can at least tell whether two encrypted values are the same, because the encrypted values will be the same if the ciphertexts are the same.
You think that's not really a problem? But consider that in many scenarios, it means that an attacker can make guesses. They guess that the value is AB, arrange for you to encrypt AB and compare the ciphertexts. Repeat for AC, AD, etc. It isn't too bad if the attackers cannot submit plaintext, but that's rare. Most databases containing encrypted data contain some user-supplied input (e.g. names).
It's worse than that: usually, if two values start with the same prefix then their ciphertext will also start with the same prefix (except for the last few characters of the common prefix, depending on the mode). This is because most encryption modes proceed in a single pass, so they encrypt the first few bytes, then the next block and so on. If the first block of plaintext is identical and the ciphertext is the same size as the plaintext then the ciphertext for the first block will be equal if the plaintexts are equal.
Additionally, if the ciphertext is the same size as the plaintext then you may ensure some confidentiality of the data, but you won't be able to guarantee its integrity. There's no way to detect that the data has been modified without adding some redundancy information, and that redundancy information has to go somewhere.

Encryption modes solve this problem by including a unique value at the beginning of each ciphertext, called an IV¹. That's the reason why any sensible encryption mode results in ciphertext that's a little larger.

A second reason why the ciphertext is larger is padding, for modes that work on whole blocks at a time. This an be avoided by using a mode that doesn't have padding. Your library should offer CTR mode, which is fine if used correctly.

For CTR mode, like any other mode, you need a unique IV for each value that's encrypted. For CTR mode, you actually need a bit more than that: the counter value must be unique for each block. The counter value doesn't have to be random, although that's a popular choice, so it's ok to construct the counter value from the array index. If each value is at most $16 \times 2^n$ bytes long then you can use $2^n \times k$ as the IV for block $k$. (Note that the IV is a 16-byte string; be careful not to use a smaller type like 32-bit integers where you risk wraparound in arithmetic operations.)

Do note that this is only safe if the attacker sees a single version of the database. If the attacker sees multiple versions then they will see changed contents in some blocks that are encrypted with the same IV. This gives the attacker some information about the content of the block, possibly revealing both the old value and the new value depending on what partial information the attacker has on the values (data format, content of some guessable fields, …).

The simple option is to accept that storage is cheaper than security breaches, and use a high-level crypto API that doesn't require you to understand all the details.

A few more remarks…

  Rijndael

The modern name is AES. It's perfectly fine: it's the standard symmetric algorithm these days. “AES” only tells part of the story: it only says how to transform a 16-byte block of plaintext into a 16-byte block of ciphertext. To specify the algorithm, you also need to specify the mode which explains how to assemble the blocks together. Two popular modes for encryption only are CTR and CBC. (Some libraries provide a mode called ECB; never use it: this isn't a proper encryption mode, it's a building block for when you want to use a mode that isn't provided by the library.)

  this algorithm will add up to 15 byte to result (if you use block with length equal to 16)

No, actually the algorithm will add 16 bytes at the beginning for the IV. It may additionally pad the last block (CBC does, CTR doesn't).

  I can not afford such a thing (result length should be same as given length)

Scenarios where a few bytes are not possible are extremely rare. Think again.

If you really really really can't do the simple thing and use a proper mode with a proper IV, then I urge you to have someone competent review the code. I'm sorry to say, but if you needed to ask this question then the chances that you'll get it right are small, even after reading a few Stack Overflow and Stack Exchange posts.

¹  “IV” isn't the technically correct term for some modes, but it'll do.


Find plaintext of RSA by solving extended euclidean algorith for two encrptions with two different exponents for same plaintext

If you are able to compute $m^1 \pmod{N}$, then you have (obviously) recovered the message $m$. So, you should be able to use the extended Euclidean algorithm to express $m^1 \pmod{N}$ in terms of $c_A$ and $c_B$.

Hint: It will involve exponentiations and multiplications.


Here's a recent doctoral thesis with a decent literature review.
https://discovery.ucl.ac.uk/id/eprint/10073525/


The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not proved but considered secure against known-plaintext attack, see this question for details.

And, also, key size itself doesn't represent the security. High key sizes are necessary but not sufficient. As an example from history, Enigma was beyond its time as having around $87$ to $88$-bit key size which is greater than the key size of DES. We have already know that Enigma is broken.

Answer to comment: We work in Kerckhoffs's principles and are not accepting security by obscurity. So the attacker knows everything but the key.


How to calculate the time it'll take to crack RSA or DH?

There is an asymptotic formula for the General Number Field Sieve for factoring big integers. This is the most efficient known algorithm for breaking RSA keys which are longer than 400 bits or so (since the current world record is 768 bits, a 400-bit RSA key is quite weak). For discrete logarithm (to break DH), the best known algorithm is also known as "number field sieve" and it is much similar to the one for factorization. In particular, it has the same asymptotic complexity.

However, asymptotic formulas do not capture all the information you want:

An asymptotic formula describes the behaviour of the function which gives the computation time depending on the size of the input, for large enough inputs. It says that "when the input size grows toward infinity, the complexity grows in a way similar to this formula". But that's still an approximation and nothing guarantees that an actual RSA key you are trying to break is large enough for the asymptotic formula to be reasonably accurate. For instance, Multi-Polynomial Quadratic Sieve is asymptotically slower than GNFS; but it is in practice faster than GNFS for 300-bit integers. This means that 300-bit integers are not large enough for asymptotic formulas to accurately rate factorization algorithms against each other.
Even when the formula is accurate, it has an implicit multiplicative constant in front (which you can name "number of operations per second" if you wish). So the formula must be calibrated with an actual experiment. Speaking of which, even though GNFS for factorization and NFS for discrete logarithm share the same asymptotic behaviour, they do not have the same "constant" so, in practice, a 600-bit DH key seems to be substantially harder to break than a 600-bit RSA key (indeed, the current world record for discrete logarithm is "only" 530 bits).
Time complexity formulas talk only about operations, but do not describe space requirements. In GNFS for large numbers, the storage space can become tremendous, especially for the last part of the algorithm (the "linear algebra") which is a conceptually simple operation (Gauss reduction) on a matrix of humungous size; in practice, that step is constrained by the RAM size and speed, and also how fast you can move the data around in a cluster. CPU is not the bottleneck, and the time complexity formula talks only about the CPU.
The whole process is not streamlined. There are several steps in the algorithm (polynomial selection, sieving, linear algebra) and although there is good opensource code for that, it still requires some thinking by smart people at some crucial moments. To beat the world record in factorization, you need horsepower but also computer scientists who know the ins and outs of GNFS, and there are maybe a hundred of those worldwide.

So the practical way of estimating the breaking time for a RSA or DH key is to extrapolate from the published integer factorization records and discrete logarithm records.

There has been quite a lot of work on such "extrapolation", in particular in the search for "equivalences" between symmetric and asymmetric key lengths (as in: "a 1024-bit RSA key is roughly as robust as a 160-bit hash function"). See this site for a comprehensive summary of the resulting recommendations emitted by various organizations (with online calculators and many pointers). Given the points I evoke above, it is not surprising that the published recommendations do not really match each other...

The synthetic advice which is often given in 2011 is: "use 2048-bit RSA/DH/DSA keys, and you will be fine for a looong time."


For elliptic-curve cryptography, does a 256-bit key imply that $x$ and $y$ are each 256-bits or 128-bits?

In ECC, the xxx-bit curve implies the modulus length. Also, this implies the length of each coordinate in $(x,y)$. Therefore, $x$ and $y$ are each 256-bit


If $H(x)$ is a one-way function, is $f(x)=H(x)\cdot x^{-1}$ a one-way function?

Let ${y=x^{-1}}$. if ${f(x)}$ is a bijective function. then we can avoid ${H(x) \cdot y= H(x) \cdot y'}$, where every ${x}$ has unique ${f(x)}$


What is the difference between DROWN and ROBOT vulnerability?

This attacks are quite similar since they both target TLS handshake and exploit a padding oracle on RSA decryption.
However, the way the attacker access this oracle is quite different.

DROWN attack

In this attack, the authors assume that the server uses the same RSA key for both TLS and SSLv2. We can have this situation, for instance, if the server still supports SSLv2 (which is bad but quite common according to the paper), or if the key is shared with another server supporting SSLv2 (sharing keys is never a good idea...).
Since SSLv2 is badly flawed, an attacker can use it to access the oracle and perform an improved Bleichenbacher attack on a message coming from the TLS handshake.

Bottom line: the attacker does not attack TLS per se, but the fact that the same key is used in a weaker protocol. This can be qualified as a cross-protocol attack, induced by poor key management and/or server misconfigurations.

ROBOT

Here, there is no need to assume key sharing or support of weaker protocols.
The authors developed a systematic tool to scan TLS implementations in the wild and see if they can obtain a padding oracle by various means (error codes, no response in case of error, ...). They found out that a lot of widespread implementations provide a padding oracle during the TLS handshake, meaning the Bleichenbacher vulnerability is still present, even in up to date implementations.

All implementations did not provide a "good enough" oracle to exploit the attack in a reasonable time, but still, this vulnerability should have been long gone.

TL;DR: The core attack is quite similar, but DROWN is a cross-protocol attack between TLS and SSLv2, whereas ROBOT point out that TLS by it self is still vulnerable.


Does any problem arise when the order of an elliptic curve is equal to its prime field modulus?

Found an answer: Why Smart's attack doesn't work on this ECDLP?

Smart's attack seems to be what I was looking for.


This can be derived from two simple facts about the $mod$ operation:

$a \bmod b = a + bi$ for some integer $i$ (for any $a, b$)

$a \bmod c = b \bmod c$ if $a - b = ci$ for some integer $i$

With these two facts, we can look at $(g^a \bmod p)^b$; that can be simplified to $(g^a + pi)^b$ (for some integer $i$), and by the binomial expansion, this is $g^{ab} + p(\textit{Other terms})$ (for some integer value of Other terms).

When we look at the difference between that and $(g^a)^b$, we get the value $g^{ab} + p(\textit{Other terms}) - (g^a)^b = p(\textit{Other terms})$, which is $p$ times some integer.

Hence, by our second fact, we immediate get $(g^a \bmod p)^b \bmod p = (g^a)^b \bmod p$, which is what we set out to prove


Semi static ElGamal vulnerability when the secret is not truely random

The answer obviously depends on what $f$ is. However, we can say a few general things.

If $f$ is a "simple" linear function (e.g. $f(r) = kr$ for most constant $k$), you can recover $m'$ easily. You cannot recover $r$ or $r'$.

If $f$ is a more complex function that is bijective or nearly bijective (say SHA-256), then you probably cannot recover $m'$. You cannot recover $r$ or $r'$.

If $f$ is a sufficiently many-to-one function and its inverse image is sufficiently simple (say $f(r) = r \bmod{2^i}$ for a suitable $i$), you may be able to recover $r$ and $r'$.


How does a "Tiger Tree Hash" handle data whose size isn't a power of two?

The Tree Hash EXchange format (THEX) spec (which seems to have dropped off the web, but is still available on archive.org) says, in section 2:

  2.1 Hash Functions

  The strength of the hash tree construct is only as strong as the
  underlying hash algorithm. Thus, it is RECOMMENDED that a secure hash
  algorithm such as SHA-1 be used as the basis of the hash tree.

  In order to protect against collisions between leaf hashes and
  internal hashes, different hash constructs are used to hash the leaf
  nodes and the internal nodes. The same hash algorithm is used as the
  basis of each construct, but a single '1' byte in network byte order,
  or 0x01 is prepended to the input of the internal node hashes, and a
  single '0' byte, or 0x00 is prepended to the input of the leaf node
  hashes.

  Let H() be the secure hash algorithm, for example SHA-1.

internal hash function = IH(X) = H(0x01, X)

leaf hash function = LH(X) = H(0x00, X)

  2.2 Unbalanced Trees

  For trees that are unbalanced -- that is, they have a number of leaves which is not a power of 2 -- interim hash values which do not have a sibling value to which they may be concatenated are promoted, unchanged, up the tree until a sibling is found.

  For example, consider a file made up of 5 segments, S1, S2, S3, S4, and S5.

                     ROOT=IH(H+E)
                      /        \
                     /          \
              H=IH(F+G)          E
              /       \           \
             /         \           \
      F=IH(A+B)       G=IH(C+D)     E
      /     \           /     \      \
     /       \         /       \      \
A=LH(S1)  B=LH(S2) C=LH(S3)  D=LH(S4) E=LH(S5)

  In the above example, E does not have any immediate siblings with which to be combined to calculate the next generation. So, E is promoted up the tree, without being rehashed, until it can be paired with value H. The values H and E are then concatenated, and hashed, to produce the ROOT hash.


Robust cryptosystem for files/chunks protection?

I'm looking at a very similar thing, where I need to encrypt data at rest, and the existing file structure that I'm trying to add encryption to is randomly accessed chunks / blocks of binary records.

The file IO I'm working with is performance sensitive, and the binary structure caters for allocating and freeing record space within these chunks.  It is in an embedded environment, so the desktop storage encryption solutions can't be applied.

I looked at AES-GCM after seeing many recommendations for it.  But the NIST guidelines for its use, which require unique IVs for a given key, make it challenging for storage encryption.  Somewhere I read that AES-GCM is better suited to transport encryption.

I'm currently heading down the path of AES-CBC + AES-CMAC, due to less stringent requirements around key and IV re-use.  Having a file key and chunk IVs from a CRNG seems to be acceptable.  Again, I'm new to this as well, so I'm happy to be told otherwise.  I'm just on here researching the process of deriving keys for encryption vs MAC generation from a common key.

I was tempted by OpenSSL's EVP_aes_256_cbc_hmac_sha256, but then the docs have a warning that it was only intended to be used internally by OpenSSL's SSL/TLS.  It would be nice to find the "shrink wrapped" answer to take care of all this.

Key storage without an HSM can be challenging, especially if there is no user involved.  In a desktop environment, a key derived from a passphrase (KDF) is the traditional solution.  A "logon secured" encryption scheme can also be used (e.g. Microsoft's DSAPI). Without that, I think it becomes a chain of "where to keep the key that encrypts the key...", which I haven't yet seen a good answer for.

Securing keys with another layer of encryption is called key wrapping.  I've seen code that uses AES to encrypt one key with another as a simplified version of this.


What is the point of differential cryptanalysis when the amount of necessary plaintext is unrealistic?

Differential cryptanalysis is a very powerful technique that permitted highly practical attacks on many ciphers that were not designed to resist it (e.g. FEAL-4).  DES, as it turns out, was designed to be pretty resistant to it, which is why it requires an essentially impractical amount of chosen plaintexts to implement a differential attack on DES.

However, I would note that $2^{47}$ is still significantly less plaintext than a generic codebook attack requires, and moreover the attack has a time complexity of only about $2^{37}$ DES calls (which is significantly better than the generic key-guessing attack).  As such, differential cryptanalysis counts as a 'break' of the cipher (anything that is better than generic attacks is a 'break').  It is only an 'academic' break, given the impracticality of so much chosen plaintext (which is why DES wasn't immediately deprecated once Biham and Shamir published their paper).  But it is a break nonetheless.

In general, people 'bother' with cryptanalysis because they want to evaluate the ciphers they use to protect lives and billions of dollars against all known attacks in order to understand how secure they are.  If you can show (for a cipher with sufficiently large parameters like key-size and block-size) that nothing beats generic attacks (i.e. that there are no 'breaks') then that gives people confidence in the security of the cipher.


Would using a one-time pad multiple times with some conditions be safe?

For perfect secrecy of any cryptosystem, it must hold that |key|≥|all messages exchanged|.

Proof by contraposition: assume |key|<|all messages exchanged|, and there exists a deterministic decryption procedure of all ciphertext exchanged and key to all messages exchanged. Knowing all messages exchanged, an infinitely powerful adversary can exclude some value of messages exchanged as impossible, violating perfect secrecy; all s/he has to do is apply said procedure to decipher the given all ciphertext exchanged with all the possible values of key, and rule out as impossible any value of all messages exchanged not obtained for any value of key. The hypothesis |key|<|all messages exchanged| implies there will exist at least one impossible value, by a counting argument.

In the case of the repeated OTP in the question, there exists attacks that can be performed by an adversary with very limited computing ability, and enough knowledge about the plaintext.

For example, assume that all the messages are long, random, and known entirely except for an unknown bit in the middle of the last message. It becomes likely and easy to find most of the key, and the starting point for all messages, and from that the single unknown plaintext bit.

There are more clever attacks that work with less hypothesis on the plaintext (like: it is mostly English words), and remain feasible in practice if there is enough ciphertext.


Is Bouncycastle RSA+OAEP implementation vulnerable to Manger’s attack?

Bouncy Castle Java releases 1.60 and FIPS 1.0.1 (and former) have precisely the issue exploited in Manger's attack: an exception occurs when a ciphertext $c$ is submitted such that $c^d\bmod N$, expressed as a bytetring as wide as $N$, does not start with a 0x00 byte; and then the rest of the decryption process does not occur, leading to markedly faster execution. If an adversary can iteratively submit a few thousands messages for decryption and detect the exception or the faster execution, s/he can decipher a ciphertext, or make a signature. The private key itself does not leak.

Pre-release version 1.61b03 (available here, also on GitHub) has a fix that removes the unwanted exception, and reduces timing variation by orders of magnitude. If it remains vulnerable, that could only be with precise and repeated timing by an attacker.

Manger's attack and countermeasures in later editions of PKCS#1v2

The attack is exposed in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001). It exploits an RSA decryption system that leaks a little information about $y=x^d\bmod N$ for $x$ repeatedly chosen by an attacker.

The applied part of the attack focuses on the leak of if $y<2^{8k-8}$ with $N$ of $8k-7$ to $8k$ bit; or equivalently: does $y$ start with a 0x00 byte when expressed as a big-endian bytestring of $k$ bytes, as it should in RSAES-OAEP padding:

In PKCS#1 v2 7.1.2 (Decryption operation) step 4, that 0x00 is verified thru the use of "length $k-1$" in:

  Convert the message representative $m$ to an encoded message $\text{EM}$ of length $k-1$ octets: $\text{EM}=\text{I2OSP}(m,k-1)$
  If I2OSP outputs "integer too large," then output "decryption error" and stop.

PKCS#1v2 has a note stating that the above "decryption error" must be identical to one that can occur on failure of another redundancy check made after OAEP's masking is undone.

Manger observed that not all implementations do this properly; and those that do as instructed take less time when that test fails (due to the stop, the rest of the rest of the procedure is not performed, saving time), thus timing can reveal the desired bit of information.

This is addressed in PKCS#1 v2.1 (and PKCS#1 v2.2, identical in this regard) by using $\text{I2OSP}(m,k)$ without the $-1$, which outputs an extra additional byte $Y$ and never triggers an error. $Y$ is tested in the end, together with other redundancy criteria applying to the message after OAEP unmasking.

  If there is no octet with hexadecimal value 0x01 to separate $\text{PS}$ from $M$, if $\text{lHash}$ does not equal $\text{lHash’}$, or if $Y$ is nonzero, output "decryption error" and stop.
  Note. Care must be taken to ensure that an opponent cannot distinguish the different error conditions in (the above), whether by error message or timing, or, more generally, learn partial information about the encoded message EM. Otherwise an opponent may be able to obtain useful information about the decryption of the ciphertext, leading to a chosen-ciphertext attack such as the one observed by Manger.

All versions of RSAES-OAEP in PKCS#1v2.0, 2.1 and 2.2 are interoperable, and the procedures described lead to identical results, except that their timing variation is less likely to leak information in 2.1 and later.

Bouncy Castle's code

In Bouncy Castle's version 1.60 (current when the question was asked and this answer first drafted) the code specific to RSAES-OAPEP decryption is decodeBlock in OAEPEncoding.java. That contains

    byte[]  data = engine.processBlock(in, inOff, inLen);
    byte[]  block = new byte[engine.getOutputBlockSize()];
    // as we may have zeros in our leading bytes for the block we produced
    // on encryption, we need to make sure our decrypted block comes back
    // the same size.
    System.arraycopy(data, 0, block, block.length - data.length, data.length);

The definition of engine is such that processBlock returns data with leading zero bytes suppressed, and getOutputBlockSize returns $k-1$ when $N$ is $k$-byte. It follows that block.length - data.length is $-1$ when $(c^d\bmod N)\ge2^{8k-8}$, and then System.arraycopy makes an ArrayIndexOutOfBoundsException not locally caught nor listed in those that the caller is invited to expect, and that the rest of the function is not executed.


Is AES key length a size of the key or entropy?

When they say they are using a 128 bit AES key, they mean the length of the key is 128 bits. Technically a 128 bit AES key could have 0 bits of entropy, 128 bits of entropy, or anywhere in between.

To be secure, however, the 128 bit key should also have high entropy. Ideally, a 128 bit AES key would also have 128 bits of entropy.

A few side notes
Keep in mind that $\log_2N^L$ only computes the entropy in the key if the $L$ characters in the password were chosen randomly.

There is no such thing as a 160 bit AES key. AES supports key lengths of 128, 192, 256 bits.


Why are the ciphertexts of Ansible Vault's AES256-encrypted files disproportionately composed of '3' and '6'?

Is this a peculiarity of the bytes of the underlying AES ciphertext, or of the way Ansible/Python represents the binary ciphertext as a digit string?

It's an artifact of how it represents a binary ciphertext.
What it does it first converts the binary into an ASCII representation of the hex, that is, converting it into the digits '0' through '9' and 'a' through 'f'.  Then, it converts each hex digit into its two digit hex representation, that is, the values '30' through '39' and '61' through '66'.
Back translating the first 16 characters of your quoted string:
6531333066306133

when converted back into ASCII, those are the 8 characters e130f0a3, which is the hex representation of the actual binary value.
As for why the character distribution you saw:

The character 3 is the first digit of 62.5% of the encoded bytes and is the second digit of 12.5% of the encoded bytes; hence it is expected to occur 37.5% of the time in aggregate

The character 6 is the first digit of 37.5% of the encoded bytes and is the second digit of 12.5% of the encoded bytes; hence it is expected to occur 25% of the time.

Any of the characters 1,2,4,5 is the second digit of 12.5% of the encoded bytes, hence it is expected to occur 6.25% of the time.

Any of the characters 0,7,8,9 is the second digit of 6.25% of the encoded bytes, hence they are expected to occur 3.125% of the time.

Those are roughly what you've seen (although the second example doesn't hold that close to these expected statistics; I'm not certain why that would be)


PKCS5 padding is a narrowly defined subset of PKCS7 as per its specification.
PKCS7 padding is identical to PKCS5 when applied to an 8-byte block only.

The PKCS5 specification is actually defined only for DES, not 64-bit block ciphers in general.

However, PKCS5 by specification MUST created an invalid padding string when applied to a block size that is longer than 8 bytes, and where more than 8 bytes of padding are needed, since it explicitly defines the value 8 for the block size and divisor in bytes. If 9 bytes of padding are required, PKCS5 will create only 1 byte of padding with a value of 0x01.

That being said, I would suspect most in the wild implementations of PKCS5 padding actually use the block size of the cipher used rather than the predefined value, and it is certainly possible that application of padding will not cause an error. This is not hard to test.

So yes, it does rule out PKCS5 as a padding option for AES, or for any block cipher with a non 64-bit block (and technically for anything not DES or 3DES), but may sometimes work anyway.


Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme

Block cipher is a concept from symmetric cryptography. Here we're talking about public key cryptography. SIKE is a public key encryption (PKE), and a key encapsulation mechanism (KEM).

Of course Grover's algorithm applies to any public key cryptosystem, but there is not a single system where we don't know a better algorithm than Grover's. SIKE is no exception.

The quantum security of SIKE is (roughly) obtained by dividing the bit-size of the prime p by 6. For example SIKE503 has about 80 qubits of security, but NIST security categories come by large increments (64, 96, 128 qubits), the closest one being 64 qubits.

There is currently debate on whether the divide by 6 rule is too pessimistic.


Key recovery when AES ECB is used for short but repeated messages

If the attacker can make the end device send plenty join-request messages and if the server always responds with a corresponding join-accept message, can the attacker gain knowledge of the AppKey using the flaws in AES ECB?

No. ECB is flawed, but not that flawed.

At worst the attacker can know the encryption of a message if they have already seen the same message encrypted. (Or decrypted, as the case may be - LoRaWAN uses the decryption direction here to avoid having to implement both directions in the end-device.)

That can still lead to attacks, but key recovery is not possible.


Enigma - How many possibilities does the plugboard have?

out of 325 pairs to choose 10 pairs, there are 325C10 possibilities to connect pairs with 10 wires.

This accounts for the fact that we can not choose a pair that has both letters identical to an earlier pair, but misses that we can not choose a pair that has any letter common with an earlier pair.
A correct line of thinking is: imagine that the 20 ends of the 10 wires are numbered, and we assign a letter incrementally to each of them. That's 20 distinct letters to choose among 26, and order matters, giving $26!/(26-20)!$ ways. But the order of the 10 pairs does not matter, thus divide by $10!$. Further, the order for the two letters assigned to any of the 10 wires does not matter, thus divide by $2^{10}$. We end up with $26!/(6!\,10!\,2^{10})=150,738,274,937,250$ distinct ways.


Probabilistic verification of signature schemes like RSA?

Every signature scheme has some nonzero forgery probability: if there are $n$ distinct possible signatures, this forgery probability is always at least $1/n$, because a forger could just try signatures uniformly at random.  But sometimes $n$ is so large that $1/n$ is smaller than it needs to be for confidence, say $1/2^{2048}$ when all you really need is $1/2^{100}$, and we can exploit this to trade off forgery probability for performance.  Here's an example of how, with RSA.

Suppose a signature is not an integer $s$ such that $s^e \equiv H(m) \pmod N$, but rather a pair of integers $(s, k)$ with $s < N$ and $k < N^{e - 1}$ such that $$s^e = H(m) + kN.$$  Then the verifier can verify this equation modulo a secret uniform random $v$-bit prime $r$, $$s^e \equiv H(m) + kN \pmod r.$$  There are $\pi(2^v) - \pi(2^{v-1})$ such primes, and $s^e - h - kN$ has at most $\lceil(\log_2 N^e)/v\rceil$ $v$-bit prime factors, so the probability that $r \mid s^e - h - kN$ is at most $$\frac{\lceil(\log_2 N^e)/v\rceil}{\pi(2^v) - \pi(2^{v-1})}$$ for any fixed $(s, k)$, $h$, and $N$ unless $s^e = h + kN$.  Of course, while the forger can try about $t$ messages to find one whose hash $h$ has a desired property occurring with probability $1/t$, only about $1/2^{2048}$ of them satisfy $s^e = h + kN$ if $N \approx 2^{2048}$, so the forger has no hope of finding those.

For $v = 128$, we have $$\pi(2^v) - \pi(2^{v - 1}) \approx \frac{2^{128}}{\log 2^{128}} - \frac{2^{127}}{\log 2^{127}} \approx 2^{120},$$ and for $e = 3$ and $N \approx 2^{2048}$, we have $\lceil(\log_2 N^e)/v\rceil = 48$, so the forgery probability is at most about $1/2^{114}$.

Obviously, the verifier can choose independent primes $r_1, r_2, r_3, \dots$ to lower the forgery probability further; the verifier can also reuse the primes for multiple verifications to save effort, as long as they remain secret.

This scheme is not particularly attractive unless $e$ is very small: even for $e = 3$, it triples the size of the signature.  It is most attractive for Rabin-type signatures with $e = 2$, which are, of course, qualitatively different from RSA-type signatures (and largely better all around except in being deployed anywhere!).

To my knowledge, this idea was first published by Bernstein in 1997, and is mentioned in his summary paper on modular root signature schemes discussing many variations on the themes of RSA and Rabin–Williams signatures.


How to prove membership of a list without disclosing the list members?

Have a look at Zero Knowledge sets and paragraph 4.3 from here


Building a hard to factor number without knowing its factorization

The zerocoin paper mentions such a technique:

  implementers can use the
  technique of Sander for generating so-called RSA UFOs
  for accumulator parameters without a trapdoor

and refers to:

  T. Sander, “Efficient accumulators without trapdoor extended
  abstract,” in Information and Communication Security, vol.
  1726 of LNCS, 1999, pp. 252–262.

I can't access it since it's behind a paywall, but according to a comment by Hal Finney they're rather large:

  As far as the Sander paper, trust can be minimized by seeding a random number generator from a public headline. The real problem with this approach is that it generates ridiculously large RSA moduli. One example they give in their paper is 40,000 bits!


0: you have the wrong CipherValue. The one you show is in MACMethod/MACKey and is the encryption
of the MAC key, see 6.1.1. The encryption of the subject key is in Key/Data/Secret/EncryptedValue
and is AAECAwQFBgcICQoLDA0OD+cIHItlB3Wra1DUpxVvOx2lef1VmNPCMl8jwZqIUqGv.

1: openssl enc in most cases, including the one you used, does password-based encryption.
This does not encrypt or decrypt with the "key" you specify, instead it considers that a password
and runs it through a "stretching" or "derivation" function to produce the actual key.
See https://stackoverflow.com/questions/22085107/perl-cbc-des-equivalent-in-java
and https://stackoverflow.com/questions/11783062/how-to-decrypt-an-encrypted-file-in-java-with-openssl-with-aes .
For "direct" encryption and decryption you must use -K (uppercase) with the key in hex.

2: the example data in the RFC is in hex, although it doesn't say so.
For the key and IV this is okay because enc -K -iv take hex, but the data must be binary.
Hex 313233...30 is ASCII 12345678901234567890 but with no terminating newline
which echo automatically adds; preventing this varies depending on your system and/or shell, which
you don't specify, so I use perl instead.

3: XMLenc data for block/CBC contains the (actual binary) IV concatenated with
the ciphertext, with the combined result encoded in base64.

Thus (with binmode because I tested partly on Windows):

  echo $k
  12345678901234567890123456789012
  echo $i
  000102030405060708090a0b0c0d0e0f
  echo $i |\
  perl -ne "open O,'>temp';binmode O;print O map{pack('H2',$_)} ($_=~/(..)/g)"
  # that puts the binary IV at the beginning of temp
  perl -e "print '12345678901234567890'" |\
  openssl enc -aes-128-cbc -K $k -iv $i >>temp
  # that APPENDS the encryption of the data to temp
  openssl base64 <temp
  AAECAwQFBgcICQoLDA0OD+cIHItlB3Wra1DUpxVvOx2lef1VmNPCMl8jwZqIUqGv

4: MAC is computed on the encrypted value; also dgst -hmac takes the key as actual bytes (not hex)
in a C string, but the MAC key in this example contains a null byte which is impossible in a C string.
If you really want, you can do the HMAC as two hashes with tweaks of the key:

  echo $h |\
  perl -ne "open O,'>pad1';binmode O;$_=~s/[[:space:]]//g;\
  $_.='0'x(128-length($_));print O map{pack 'C',hex($_)^0x36}($_=~/(..)/g)"
  echo $h |\
  perl -ne "open O,'>pad2';binmode O;$_=~s/[[:space:]]//g;\
  $_.='0'x(128-length($_));print O map{pack 'C',hex($_)^0x5C}($_=~/(..)/g)"
  cat pad1 temp |openssl sha1 -binary -out tmp1
  cat pad2 tmp1 |openssl sha1 -binary -out tmp2
  openssl base64 <out2
  Su+NvtQfmvfJzF6bmQiJqoLRExc=

And there you are.