Are there any signatures based on matrix multiplication with noise?

There are two major families of signature schemes that bear some resemblance what you described.

Code-based signatures: Courtois–Finiasz–Sendrier, or CFS

The CFS family of signature schemes is based on code-based cryptography first introduced by Robert McEliece in 1978 and dualized by Niederreiter.  We work with binary linear codes, of length $n$ and rank $k$ correcting up to $t$ errors.

In the error-correcting code scenario, a sender with a $k$-bit message $m$ redundantly encodes it as an $n$-bit codeword $c$ from a $k$-dimensional subspace of all $n$-bit strings, and sends it along a noisy channel; the receiver, on receiving a possibly modified message $c' = c + e$, can uniquely recover $c$ as the codeword nearest to $c'$ as long as the error pattern $e$ has no more than $t$ bits set, i.e. as long as the Hamming weight of $e$ is at most $t$.

The generator matrix of a linear code is a $k$-by-$n$ matrix $G$ that that transforms $k$-bit messages to $n$-bit codewords: $c = G m$.  The parity-check matrix of a linear code is an $n$-by-$(n-k)$ matrix $K$ that transforms $n$-bit strings to $(n-k)$-bit syndromes.  An $n$-bit string is a codeword in the code if and only if its syndrome is zero: $K c = 0$, and $H c' = K\cdot(c + e) = K c + K e = K e$.  The syndrome decoding problem is to find $e$ given $K e$.  The premise of CFS signatures is that finding the noise given a syndrome given only the parity-check matrix $K$ seems to be difficult without additional information about the structure of the linear code.

Parameters.
Bit sizes $n$, $k$, $t$ for a family of binary linear codes, usually binary Goppa codes (other proposals like Reed–Solomon codes have been broken, although there are new candidates, e.g. Reed–Muller codes in the pqsigRM submission to NIST PQCRYPTO), and a random function $H\colon \{0,1\}^* \to \mathbb F_2^{n-k}$ from messages to syndromes.

Public keys.
Alice's public key is the parity-check matrix $K$ of a binary linear code of length $n$ and rank $k$ correcting up to $t$ errors.

Signatures.
A signature by Alice on a message $m$ is an error pattern $e \in \mathbb F_2^n$ such that $K e = H(m)$.  That is, a signature is the noise whose multiplication by a parity-check matrix yields a syndrome that is the hash of a message.

Private keys and signing.
Too complicated to fit in the margins of this crypto.se post; see McBits for a modern implementation strategy of CFS signatures and Niederreiter KEM, and Classic McEliece for a NIST PQCRYPTO submission based on it (but KEM-only, no signatures), which also have concrete parameter suggestions for reasonable post-quantum security levels.  (The pqsigRM submission to NIST PQCRYPTO may have some implementation ideas too, but its supporting documentation makes no mention of side channel attacks or constant-time algorithms, and a brief look at the code makes me suspicious.)

Lattice-based signatures

Let $q$ be a prime, and let $F$ be the field $\mathbb Z/q\mathbb Z$.  Fix a secret vector $s \in F^n$, a sample of uniform random vectors $a_i \in F^n$, and a sample of errors $e_i \in \mathbb Z$ with some distribution $\chi$

The computational learning with errors problem, introduced by Regev in 2005, is to find $s$ given the sample $(a_i, \langle a_i, s\rangle + e_i) \in F^n \times F$ with nonnegligible probability.

The decisional learning with errors problem is to distinguish it from $(a_i, v_i)$ for uniform random $v_i \in F$.  There are a few variants on the theme: for example, in the ring learning with errors problem, we replace the vector space $F^n$ by the ring $F/(x^n + 1)$ when $n$ is a power of two, or $F/(\Phi(x))$ for some polynomial $\Phi(x) \in F[x]$, which was introduced by Lyubashevsky, Peikert, and Regev in 2010 to admit much smaller parameters.

This is a sketch of the Lyubahsevsky's learning with errors signature scheme, derived from the same Fiat–Shamir transform used to derive Schnorr signatures, and on which newer systems such as the NIST PQCRYPTO submission qTESLA are based.

Parameters.
Field $F$; dimensions $n$, $m$, and $k$; bound $d$; bounded distribution $\chi$ on $\mathbb Z^m$; a standard $n$-by-$m$ matrix $A$ in $F$; and a random function $H\colon \{0,1\}^* \to \{-1,0,+1\}^k$ such that $\lVert H(M)\rVert_1$ is bounded.

Public keys.
Alice's public key is an $n$-by-$k$ matrix $T$ in $F$.

Signatures.
A signature by Alice on a message $\mu$ is a pair of $z \in \mathbb Z^m$ and $c \in \mathbb Z^k$ such that

$\lVert z\rVert^2 = \sum_i {z_i}^2$ is small, and
$c = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$, where $z_q$ and $c_q$ are the componentwise projections of $z$ and $c$ onto $F = \mathbb Z/q\mathbb Z$, and the underline is some canonical bit string encoding of $F$.

(For the technical details of what ‘small’ means, see the paper.)

Private key and signing.
Alice's private key is a secret $m$-by-$k$ matrix $S$ in $\mathbb Z$ whose elements are chosen uniformly at random from integers at most $d$ in absolute value.  Let $S_q$ be the componentwise projection of the matrix $S$ onto $F$.  Alice computes her public key by $T = A S_q$.  (With an appropriate transformation of $A$, this is not far from the form of the learning-with-errors problem.)

To sign a message $\mu$, Alice draws $y \in \mathbb Z^m$ from $\chi$,  computes $c = H(\underline{A y_q} \mathbin\Vert \mu)$ and $z = S c + y$, and, with some rejection sampling on $z$, reveals $(c, z)$.

This satisfies criterion (1) of signatures because of the bounds on $S$, $c = H(\cdots)$, and $y \sim \chi$.

This satisfies criterion (2) of signatures because $A z_q - T c_q = A S_q c_q + A y_q - A S_q c_q = A y_q$, so $c = H(\underline{A y_q} \mathbin\Vert \mu) = H(\underline{A z_q - T c_q} \mathbin\Vert \mu)$.

Filling in details is left as an exercise for a less tired ossifrage than this one, preferably when day is not breaking.


Difference between AES CMAC and AES HMAC?

A similar question as been asked before: Use cases for CMAC vs. HMAC?

To resume it, AES-CMAC is a MAC function. It can be seen as a special case of One-Key CBC MAC1 (OMAC1) which also a MAC function that relies on a block cipher (so AES in the present case).

HMAC is also a MAC function but which relies on a hash function (SHA256 for HMAC-SHA256 for example).

So the term AES-HMAC isn't really appropriate. If you read it somewhere, it could signify the process of computing a HMAC on the message you want to encrypt to ensure the integrity property (AES$[message ||$ HMAC$(message)]$ for example).

Note that there exists authenticated ciphers that simultaneously ensure confidentiality, integrity and authenticity.

  Also, does openSSL libs support AES CMAC and AES HMAC?

OpenSSL supports HMAC primitive and also the AES-CMAC one (see How to calculate AES CMAC using OpenSSL?)


AES, CMAC and "3 pass authentication protocol" Explained

AES is a block cipher. It permutes (maps) input blocks to output blocks of 16 bytes. The permutation that is used depends on the key. AES must be used in a mode of operation such as CBC to be able to be offer confidentiality of dynamically sized messages. CBC is commonly used in Smart Card environments. CBC offers confidentiality against (passive) eavesdroppers.

AES-CMAC is a MAC based on AES-CBC. It offers data integrity and authenticity. It is an alteration on CBC-MAC to make it secure for dynamically sized messages. Reusing CBC is of course a good idea for embedded environments (rather than relying on HMAC where the hash is commonly implemented in software).

Sometimes you may only need a MAC when communicating with a Smart Card or tag (e.g. when sending commands without confidential data). In that case you may directly perform MAC over the plaintext (command). If the data needs to be confidential then usually encrypt-than-mac is used instead of mac-then-encrypt. This is especially important when it comes to avoiding CBC padding oracle attacks.

Usually the message protection is performed by session keys, derived from the master key.

3-pass mutual authentication may also use encryption or MAC. There is not a single 3-pass protocol, there are multiple protocols that either use the master key or derived (session) authentication key, encryption or MAC. This protocol is used for entity authentication rather than message security. The (random) values used within this protocol that precedes message exchange may be used to derive the other session key(s).

Per session there may be as much as 6 session keys per pair of entities (e.g. card and reader). One key may be used for entity authentication, one for encryption and one for MAC. These 3 keys can have two sets: one for sending and one for receiving (authentication) messages. These may be generated directly or indirectly from one master key. Quite often the master key is however used directly for entity authentication, removing two keys from the list of session keys.


Information-theoretic security is a cryptosystem

Nitpick: information-theoretic security is a property that a cryptosystem can have against a particular attack model. AES is a cryptosystem, but doesn't have this property against any of the usual models; the one-time pad is a cryptosystem that does against passive attackers (but not active ones).

Other systems that have information-theoretic security, off the top of my head:

The one-time pad, against passive attackers.
Pedersen commitments, against the opener (but not against the committer).
ElGamal encryption used as a commitment, against the committer (but not the opener).
A bunch of OT systems of the Chu-Tzeng style, against either the sender or the recevier (against both at once is impossible - same goes for commitments).

Some of the above schemes are very much commercially used.

QKD is a very specific form of quantum cryptography, the two terms are not equivalent.


Breaking variations of Linear Congruential Generators

This generator has a state defined by $s_1$ and $s_2$, and can take just below $2^{62}$ states. This can't be cryptographically secure by today's standards, which call for more than 80-bit security, but is still quite too much for fast cryptanalysis by pure brute force using a single CPU. We need at least one serious speedup.

The most obvious is: enumerate the (less than $2^{31}$) states $s_1$, and for each deduce $s_2$ from one output (giving us $(s_1-s_2)\bmod m_1$ ) and $s_1$ (or, in rare case, that $s_1$ can't have that value); then check these $s_1$ and $s_2$ with a few more outputs.

The devil is in the details, and in particular the error we have on $(s_1-s_2)\bmod m_1$ as reverse-computed from actual output. If $r$ is given with 6 decimal figures on the right of the decimal point, we only get about 20 out of 31 bits (but if $r$ is given with 6 significant digits, we'll get more for small $r$). This is however enough to reconstruct $s_2$ from two consecutive outputs and values of $s_1$ without enumerating all the possible values of $(s_1-s_2)\bmod m_1$ (that would only be a last resort).

The above is crude, but will get the job done in seconds with a careful implementation on a modern CPU. And (quoting Bruce Schneier, attributing the saying to the NSA):

  Attacks always get better; they never get worse.

Note: since Pierre l’Écuyer's generator has been around for nearly 3 decades, is quite usable for non-cryptographic purposes like simulations, portable, relatively efficient given that constraint, and apparently often used, I would not be surprised if it had been studied in depth, and a much better attack found.

Assuming we have an $r$ (like 4.833936e-5) that let us walk back to $(s_1-s_2)\bmod m_1\ =d$ exactly, the unoptimized algorithm goes:

for $s_1$ from $1$ to $m_1-1$

$s_2\gets(s_1-d)\bmod m_1$
if $0<s_2<m_2$

$s_{1.1}\gets s_1\cdot a_1\bmod m_1$
$s_{2.1}\gets s_2\cdot a_2\bmod m_2$
if $(s_{1.1}-s_{2.1})\bmod m_1$ matches output well enough

$s_{1.2}\gets s_{1.1}\cdot a_1\bmod m_1$
$s_{2.2}\gets s_{2.1}\cdot a_2\bmod m_2$
if $(s_{1.2}-s_{2.2})\bmod m_1$ matches output well enough

success, output $(s_1,s_2)$ and stop.

Failure, refine.

A possible improvement is that most of the time $s_{1.1}−s_{2.1}$ varies by $a_1-a_2$ from one step to the other of the outer loop, and that's small, which allows to fast-forward $s_1$ considerably. I believe that alone will reduces the attack to a mere fraction of a second (c.f. saying).


Relation between encryption algorithms and (password) hash functions

This is just a sketch of the idea but I think the reasoning is as follows:

The output of a good block cipher looks random so you can think of a block cipher as a PRF.
If you have a PRF you can do simple things like throwing away half of the output to turn it into a compression function.
Hash functions are traditionally built from such compression functions. Usually in a Merkle-Damgård construction.

Clearly the security of the Hash function depends on the security of all these building block and the precise steps taken in between.

Even if blowfish may have weaknesses it is possible that the output still has sufficient entropy that it can be turned into a good compression function. Note that according to Wikipedia the problem with blowfish is its small block size which doesn't affect the PRF property.

EksBlowfish is a step of bcrypt. As described in the publication.


In CBC, can I use a zero IV and prepend my actual IV to the plaintext?

I can think of one security risk, though it can be mitigated:

If the attacker can guess your IV, then you are giving them an avenue to recover your key. Ie if they know the IV, then they can do a known-plaintext attack on the first block. If you use a cryptographically-secure random number for the IV, then it's probably fine.

As @AgentMe points out, this has already been discussed here:

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

More importantly, there are some efficiency losses by doing this:

You do an extra encryption round. This is probably not a big deal for most applications.
You inflate the size of the cyphertext by one block. This can be a big deal where the plaintext and cyphertext are required to be the same size - for example if the caller is expecting it to be encrypted in place in the same memory block.


If I allow arbitrary initial hash values for SHA-256, what would be the weaknesses?

Would it be easier to find collisions, preimages, etc?

First note that if you can find preimages for a compressing function (like a hash) you can also find collisions. This means if we can't find collisions, then we also can't find preimages and thelike.

Now, the scenario you are describing is called a "freestart collision attack". Freestart collisions are one of the first signs that a hash functions has a serious flaw, e.g. a freestart collision was found for SHA-1 a couple of years before the full collision. Such a collision would utterly destroy our current faith in SHA-256 and is thus unlikely to be found.

Also note that the quoted passage talks about a variant of SHA-256 that removes the length padding to describe an attack. This attack is prevented by the length padding (and is the main reason why it's there).


Having two messages and a result ciphertext, is it possible to know which one was encrypted using One Time Pad?

No, not if the messages $m_1$ and $m_2$ have an identical length.
A one-time pad can produce any ciphertext from a message, so you wouldn't know which message was used.
If the messages differ in length than you would know, because the resulting ciphertext from a one-time pad has the same length as the original message.
This is of course assuming that you don't extend the shorter message with additional information to match it's length to the longer message or vice versa, somehow shorten the longer message.


How does one calculate the scalar multiplication on elliptic curves?

$\def\dbl{\mathrm{dbl}}$Okay, let's give the missing step between mikeazo's and poncho's answers.

I assume you've read mikeazo's answer to know how to add and double points.

Now, how do we get a scalar multiple of a point?

A simple algorithm is called "double-and-add", as it just does this.

In a simple example, we have $5 = 4 + 1 = 2·2 + 1$, and thus $5·P = (2·2+1)·P = 2·2·P + P$. So we calculate $P → \dbl(P) = 2·P → \dbl(\dbl(P)) = 4·P → 4·P + P=5·P$.

For your example of $200$, we have $200 = 128 + 64 + 8 = 2^7 +2^6+2^3$, and thus $200·P = 2^7·P + 2^6·P + 2^3·P$, which can be calculated as $\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P))))))) + \dbl(\dbl(\dbl(\dbl(\dbl(\dbl(P)))))) + \dbl(\dbl(\dbl(P)))$. (Of course, you would calculate the common sub-terms only once.)

Alternatively, we can use the distributive law to write it this way: $200·P = 2·2·(2·2·2·(2·P + P) + P)$.

(Note that we used the binary form of the scalar factor here to decide when to add and when not to add.)

Here are two general forms of this algorithm to calculate $d·P$, when $d$ has the binary form $d_kd_{k-1}\dots d_1d_0$ (assuming d_k = 1):

Starting from the small-endian bits:

Q := 0
R := P
for i = 0 .. k:
   if(d_i = 1)
      Q = add(Q, R)
   R = double(R)
return Q

Starting from the big-endian bits:

Q := 0
for i = k ... 0:
   Q := double(Q)
   if(d_i = 1)
      Q := add(Q, P)
return Q

Note that this is actually the same algorithm you are using for modular (or other) exponentiation, just with the operations square and multiply instead (and then usually named square-and-multiply).

Also, this trivial implementation is quite vulnerable to a power analysis attack, if implemented on a smart card, as doubling and adding doesn't use quite the same amount of power, and the adding is only done when a bit in the (usually secret) exponent is set. There are measures against this, and also a bit more efficient point multiplication algorithms – any book about elliptic curves should mention some of them.


How to implement GSW13 using Helib or SEAL?

A good resource for FHE implementations is found on Micciancio's website. Searching GSW on it points to FHEW/TFHE, although they are quite different than "standard FHE" schemes (they bootstrap after each gate in the circuit). They are implemented though.

Besides those, there are various libraries for lattice crypto (Palisade, Lol, NFLlib, all on the linked webpage) which may be useful to use in any given implementation as a starting point.


Protocol Design for IoT devices having PSK using AES-GCM

Would it be OK if the iv used in handshake gets repeated considering the plain text is a random number?

No, it would definitely not be OK.  Reusing the IV will allow the attacker to recover the internal GCM H value - this will allow the attacker to make arbitrary modifications to encrypted messages.

For static keying (or anywhere else where it's difficult to avoid repeating the IV), GCM might not be the correct solution.  Perhaps AES-SIV would work better?


With what I understood, key iterations can be used only with symmetric encryption. If a file/text is encrypted using passphrase, HASH is calculated and encrypted with AES for 'n' number of times. If iterations selected is 100 then this is done 100 times. This is done to defend against brute-force attack.

First things first: PBKDF2 (and comparable schemes) are called password hashing schemes (PHSs) (or more popularly password-based key derivation functions). All they do is take a password, preferably some randomness (aka a salt) and return a uniformly random-looking bitstring which can only be derived using the previously mentioned inputs and is suitable as a symmetric key. The special thing about PHSs compared to normal key derivation functions (KDFs) is that they also take one or more cost parameters. Usually at least one of them allows you to linearly scale execution time which is the case with the iteration count in PBKDF2.
Now the usual flow for using PHS is the following:

Gather password and salt
Run both through the PHS with some specified iteration count - AES is usually not involved in this step
Use the derived key to key some symmetric operation
Use the keyed symmetric operation for whatever it is that you need to do, e.g. encrypt / decrypt data

Indeed the key idea of the above is the observation that if you invest effort $E$ into deriving your password an attacker not knowing your password will have to invest $2^{H(P)}\cdot E$ effort where $H(P)$ is the (min-)entropy of your password. This then allows you to derive your password in say 1 second and an adversary to spend a lot of ressources to brute-force it - even if it is only moderately complex.

(2) Key iterations have no use with public-key encryption.

Well, you could feed the output of your PHS into a private key generator allowing you to immediately recover it from the password. In fact this is what BIP-39 does. Alternatively you could use a PHS to generate a symmetric key to encrypt / decrypt you private keys - which is what GPG does.

(3) Some apps. by default take 100 iterations. Few apps by default takes 2000 iterations when using AES. How many iterations are considered secure with AES-128 and AES-256?

The usual advice is "use as many as you can afford" where "afford" is a time(-memory) budget that you specify and then measure out the relevant parameter set. However if you prefer cold, hard standards, NIST SP800-63B is the relevant one and recommends at least 10,000.


Zero-knowledge identification of the majority commitment

Here is one difficultly such a protocol can have: say we do have a joint computation protocol that takes $N+1$ parties (Alice and her $n$ people); at the end of the protocol, Alice gets a list of the parties in the majority without learning their secret.

Here is how Alice can attempt to cheat: extend the protocol to $N+3$ parties, and have the extra two parties be two artifical votes controlled by Alice; thing0 will submit a 0 vote, and thing1 will submit a 1 vote; other than that, the protocol continues as is.  thing0 and thing1's vote will not change which bit was in the majority; however, when Alice gets a list of the majority party; either thing0 or thing1 will be in the list; by that, Alice will learn the secret bit.

Any such protocol will need to avoid this somehow; either by simply not being extensible to N+3 parties, or having each party get a count of how many people are participating (so that they'll know that there are two extra ringers)


There are two inputs to PBKDF2, and key derivation functions in general: the password and a salt. Assuming the attacker knows the salt, all the password hash can do is slow down a brute force or dictionary search (i.e. 1000x the complexity of HMAC with PBKDF2 default iterations), as well as force the attacker to search for each user's password individually. In that case "123456" is an insecure password with any realistic password hash.

If you for some reason could assume that the salt is a strong secret random number of sufficient size, then the keys produced from all of those passwords would be equivalently unknowable. However, in that case you could just use a fast key derivation function. It's not the problem PBKDF2 is meant to solve.

TL;DR: PBKDF2 does not make poor passwords secure, just mediocre ones somewhat less mediocre.


Let $P = (x,y)$ be a point on the curve $E$ with the $y^2 = x^3 + ax + b$ with Weierstrass equation over the prime field $\operatorname{GF}(p)$1, i.e. it satisfies the curve equation.
The consecutive $x$-coordinate point can be found with the below algorithm.
for i from 1 to number_of_poinst_on_the_curve
    temp = x + i mod p
    if  (temp, y) satisfies the curve equation
       return (temp,y')
    else
       continue
throw no_consecutive_element

The $\bmod p$ is necessary since we don't want our $x$ has value out of the possible space.

$y'$ is one of the two possible solitons to the $y^2$, except when $y=\mathcal{O}$, the point at the infinity. The educative details of finding the square root in modular arithmetic can be found on Fgrieu's latest answer;
Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate

The algorithm will terminate since the EC has a finite number of points. The number of points can be

limited by Hasse's Theorem: $N - (q+1)| \le 2 \sqrt{q}$ over finite field with $q$ elements.
Or, exactly found by Schoof's algorithm, In the paper Counting Points on Elliptic Curves over Finite Fields, published in 1985,
Or, the improved version Schoof–Elkies–Atkin algorithm

1 This is used to simplify the algorithm. EC doesn't need to be defined over a prime finite field. In Cryptography, we use the general case of Finite Fields $\operatorname{GF}(q=p^m), m \in \mathbb{Z}, m\geq 1$. Expect the prime field, the other fields have different representation for the elements.

For $y^2 = x^3 + x^2 + x$ over $GF(131)$

E = EllipticCurve(GF(131),[0,1,0,1,0])

P=E.lift_x(0) #lift can throw an error if there is no point with the given input
              #tested before that there is a point with x=0

plotE = E.plot()

for t in srange(1,129):
    try:
        R =  E.lift_x(t)
        plotE += line([P.xy(),R.xy()],color='red')
        P = R
    except ValueError:
        pass
plotE

update
Though I don't see the direct effect on Cryptography, there are academic works on this;

Integral Points in Arithmetic Progression on $y^2=x(x^2-n^2)$, by Bremner, Silverman, and Tzanakis, 2000.


To share a vector using Shamir's secret sharing, you can just share each element of the vector independently.  It really is that simple.

To save some space, you can assign all the shareholders a distinct fixed non-zero $x$ coordinate and reuse those same $x$ coordinates for all elements of the vector being shared.  The $x$ coordinates only need to be distinct; they don't have to be random or secret in any way.

(If your shareholders already have some unique ID that can be encoded as an element of the field you're using for Shamir's scheme, you could just use those as the $x$ coordinates.  Or, if you're working in a sufficiently large field to make collisions unlikely — say, ${\rm GF}(2^{128})$ or larger — you could even derive the $x$ coordinate of each participant by hashing some arbitrary pre-existing public ID, like, say, an e-mail address.  Just make sure not to allow $x = 0$ in any case, since that directly leaks the secret.)

In fact, the only reason we don't just interpret all secrets as vectors of bits and run Shamir's scheme over ${\rm GF}(2)$ is the fact that the field size limits the number of shareholders (and, in particular, a two-element field allows only one shareholder, which is kind of useless).  However, it is quite common to e.g. interpret arbitrary strings as vectors of 8-bit bytes, and share them with Shamir's scheme over ${\rm GF}(2^8)$, which works for up to 255 shareholders.


What is the advantage of adversary if the random number repeats?

Thanks to @fgrieu I've got the point I've missed.
The point is the adversary doesn't want to find the keyed function, of course, s/he would be happy if knew it, but s/he wants information and wins some game.
So Let's think like an adversary and we have asked $z$ queries $m_1, \cdots, m_z$ and got $\langle r_1, F_k(r_1)\oplus m_1\rangle, \cdots , \langle r_z, F_k(r_z)\oplus m_z\rangle$. We can have the following information from the queries' answers.
$F_k(r_1) = F_k(r_1) \oplus m_1 \oplus m_1$
$\vdots$
$F_k(r_z) = F_k(r_z) \oplus m_z \oplus m_z$
Then we choose $m'$ and $m''$ and get one more ciphertext $F_k(r')\oplus m_b$. If random number r repeats, for example r'= r_i, then we can do the following computation
$F_k(r_i)\oplus m_i \oplus m_i \oplus F_k(r') \oplus m_b = m_b$
And we exactly know which message was encrypted just by checking whether $m_b = m'$ or $m_b=m''$.
Even the adversary still doesn't know the $F_k$ we used he win CPA-game.


Why does Skein use an output transform, but other similar hashes don't?

The main reason for designing a cryptographic hash function using an
output transformation is flexibility. In the following, I try to
motivate the need for an output transformation.

For example, SHA-256 has no output transformation and a fixed
output size of 256-bit. What happens if you truncate a SHA-256 hash
value? In this case, there are no security claims at all. If something
goes wrong it is YOUR fault, since you have used SHA-256 in an
unspecified mode.

However, the designers of Skein claim the following levels of security
against standard attacks: preimage $2^m$, collision resistance
$2^{m/2}$, where m is the minimum of state and output size.  It is
safe to claim this, as long as the compression and output
transformation are secure. It is hard to claim such a level of
security without an output transformation.

Another problem is the full domain hash (FDH). Assume you are using an
FDH based on RSA-2048. You want to sign messages of arbitrary
length. For the sake of performance, you first have to hash and then
sign the hash values. If your hash value is smaller then 2048-bit you
need a secure padding.  To avoid this, Skein allows to invoke the
output transformation multiple times. In our case you will
call the output transformation -- over and over again -- until you have
an 2048-bit hash value.


So, I'll answer the theoretical part of your question, since we need a key to address the practical part.

Why is padding used in CBC?

Blockcipher such as AES are encrypting blocks of a fixed given size only, we call it the "blocksize". So, what if your data is smaller than the blocksize ? An easy solution is to add what we call "padding" to your plaintext in order to have its size match the block size.
So, padding is there to allow you to encrypt data smaller than the blocksize... But what if you want to encrypt something bigger than your blocksize?

That's where the mode of operations, such as CBC, come into play. Modes of operations are there to allow you to encrypt more data than the blocksize of your symmetric blockcipher.

But since those modes of operation are still using the underlying blockcipher to encrypt data, it means that they can only encrypt a multiple of the blocksize. So, if you have $4\ell$ bits of data to encrypt, for $\ell$ the block size of your cipher, then you're fine.
But what if you have $4\ell+5$ bits of data? (I am assuming the blocksize does not divide 5.) Then you need to pad the data with $\ell-5$ bits of padding in order to end up with a multiple of the blocksize of data ready for encryption with your mode of operation.

There are multiple methods to pad data, which can completely undermine the compatibility of a given encryption program with others. The most used padding method in symmetric ciphers and mode of operation is certainly PKCS#7.

Worth noting

There exists methods to avoid padding, in order to avoid padding completely so the ciphertext is the same size as the plaintext, the most common of those methods is certainly the one called ciphertext stealing.

There also exists modes of operation, such as CTR, which do not need any padding.

Now, contrarily to RSA encryption for instance, padding in symmetric encryption does not add security.

Checking the padding upon decryption can allow to catch errors in the transmitted ciphertext, because of the avalanche effect, (depending on the mode of operation used), but can also lead to terrific padding oracle attacks.

As explained in that question, it is better to use a cryptographic MAC to protect your ciphertext, and verify it first before performing decryption or even padding checks. I also refer you to that legendary question, regarding the way one should MAC its data when using encryption.

About ECB

Actually ECB also encrypts only multiples of the blocksize, so you will also need padding or another method to have enough data to encrypt. However, you should not use ECB for the reasons pointed out there.

Regarding your practical problem

So, I've tried your values:

from Crypto.Cipher import AES
import binascii

key = binascii.unhexlify("10a58869d74be5a374cf867cfb473859")
iv = binascii.unhexlify(16*"00")

plaintext = binascii.unhexlify(16*"00")
ciphertext = binascii.unhexlify("6d251e9044b051e04eaa6fb4dbf78465")

ciph = AES.new(key, AES.MODE_CBC, iv)

test1 = ciph.encrypt(plaintext)
print("The ciphertext is what we expected:", test1==ciphertext)

#We need to reset the cipher to get the correct IV
ciph = AES.new(key, AES.MODE_CBC, iv)

test2 = ciph.decrypt(ciphertext)
print("The recovered plaintext is what we expected:", test2 == plaintext)

and as you can see if you try it with Python and PyCrypto, it works but your ciphertext strangely differ from the actual value at offset 4, as pointed in the comment by fgrieu. The actual value is 69, not 90.

This error at offset 4 explains why you couldn't get the correct recovered plaintext, because of the avalanche effect, the whole AES block was being impacted by that little mistake.


What's a cryptographic primitive, really?

As others have pointed out in the comments, "cryptographic primitives" are generic building blocks. What exactly this means depends on your point of view and the level of abstraction.

The most basic primitives are those, where a function is considered secure, but either you can't break it down any further or there is no security argument for its individual parts. Examples:

Modular exponentiation in prime fields can't be broken down any more, and we can use this with the inherent discrete log problem to crete public key cryptography.
Symmetric encryption - we consider symmetric encryption like AES secure, with clearly defined security properties. But its individual parts, e.g. single rounds or single steps in rounds, don't have any meaningful security properties. Sure, they bring certain amounts of confusion and diffusion. However, the strength of the cipher is also a result of the entire construction - as e.g. attacks on AES with reduced rounds are known.

And then there are primitives, which are not specified any further. For example if you assume a public key encryption scheme and just need its generic algorithms (Enc, Dec), then that encryption scheme is your building block. It isn't the underlying trapdoor one-way function, because you don't care which one is actually used.

To answer your questions:

No, actually quite differently. Primitives are defined by their security properties. Some have heuristical security properties, namely withstood cryptanalysis for years (e.g. cryptographic hash functions and symmetric encryption). Others have provable security properties - with or without assumptions. Examples with assumptions are public key cryptography, an example without assumption is Shamir's secret sharing - its security is unconditional.
Well, the primitive is defined by its security property. I am not sure what you mean with "form of security arguments". But everything with a provable security argument (and some heuristic ones for only the most basic things like symmetric encryption) can be a primitive for a higher level of abstraction.
Yes, it can.
(and 5., 6.) Hash functions in general can be considered primitives. Compression functions in general are not cryptographic primitives, because they have no security property. But surely you could call it primitive - without cryptographic. This is just like hash functions: In general, a hash function is not cryptographic. If you talk about a cryptographic hash function, you should actually call it a cryptographic hash function - unless the context is absolutely clear.
But whenever you talk about a specific function and not the general one, then the term primitive is a bad choice.


Finding IV for forgery of AES CBC-MAC with non-fixed IV

This is a demonstration of MAC forgery. This is not the CBC-MAC where the IV is always set to zero and there is also, ECBC-MAC as encrypt the last block which doesn't need the length of the message beforehand to be secure.
Given a MAC, its plaintext $P_1$, and the $IV_1$ on this simple CBC-MAC
$$MAC_1 = E(P_1\oplus IV_1)$$
We want to forge a signature based on this;
$$MAC_2 = E(P_2\oplus IV_2)$$
and we want a forgery without even knowing the key. Since the IV is not fixed, we can play around with it.
Set an IV so that the resulting X-or with the plaintext will be equal to the giving message and its IV. The plaintext will be different, however, the MAC value will be the same; a forgery!
Take $P_2$ be the target message to be forged into the signature.
Take
$$IV_2 = \underbrace{P_1\oplus IV_1}_{\text{cancel part}} \oplus \underbrace{P_2}_{\text{target message}}$$
check  $$P_2 \oplus IV_2 = P_2 \oplus P_1\oplus IV_1 \oplus P_2$$
simplify
$$P_2 \oplus IV_2 = P_1\oplus IV_1 $$
and, this is a forgery since we have a different message and IV that it's x-or equal to the given MAC. This can happen since the attacker can choose the IV. To mitigate take the IV fixed as in the CBC-MAC.

As CBC mode might do several rounds, how it could be possible to find another IV for forgery attack?

The above example was for messages of one block. For multiple blocks, just set the first block as above, and keep the remaining blocks are the same. This will be multiple block messages forgery on this signature scheme.


There is a very simple way using proofs of discrete logarithms equality and ElGamal encryption. Let me first recall the following sigma proof of equality of to discret logarithms:

Let $G$ be a prime order group, and let $(a,b,c,d)\in G^4$ be such that there exists $x$ such that $a^x=c$ and $b^x=d$. Let a prover that knows $x$ and that want to prove to a verifier that $\log_a(c) = \log_b(d)$

The prover chooses $r$ and computes $A=a^r$ and $B=b^r$, then he sends $(A,B)$ to the verifier.
The verifier chooses a random $e$ and sends it to the prover. In order to turn it into a non-interactive proof, $e$ can be generated from the hash $H(a||b||c||d||A||B)$ in the random oracle model.
The prover returns $z= r + xe$ to the verifier.
The verifier checks that $a^z=Ac^e$ and $b^z=Bd^e$.

Well, we then show how to use this proof to prove that some ciphertext $c'$ is the randomization of $c$.

We denote by $g$ the generator of a prime order group $G$, by ${\sf pk} \in G$ the public key, and by $m\in G$ the plaintext message.

We parse $c$ as $(c_1,c_2)=(g^r,{\sf pk}^r m)$.

To randomize $c$, Bob chooses $s$ at random and computes $c'=(c'_1,c'_2)=(c_1 g^s , c_2 {\sf pk} ^s) = (g^{r+s},{\sf pk}^{r+s} m)$.

To prove that $c'$ is the randomization of $c$, he proves that $\log_g(\frac{c'_1}{c_1}) = \log_{\sf pk}(\frac{c'_2}{c_2})$ using the secret $s$.

Note that this works because $\frac{c'_1}{c_1}=g^s$ and $\frac{c'_2}{c_2}={\sf pk}^s$ have the same discrete logarithm $s$ iff the ciphertext is correctly randomized.


Corner cases of addition on short Weierstrass elliptic curves

The Group Law on Affine Coordinates

Arithmetical rules are derived from the line intersection and tangent equations. The formulas are;
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$

I have is with doubling of the point $(5,0)$ ... Is x or y equal to 0 even allowed when doing math for short Weierstrass elliptic curves?

When doubling we look at the tangent line. We have two cases;

$y_1 \neq 0$ for $P$, then
$$x_3 = m^2 - 2x_1, \quad y_3 = m(x_1 -x_3) - y_1,\quad \text{ where } m = \dfrac{3x_p^2 + a}{2y_p}$$

$y_1 = 0$ for $P$ then $P + P = [2]P = \mathcal{O}$

$(5,0)$ is the special case that the tangent line is vertical, the 4th case in the top figure. This means that $P+P = \mathcal{O}$ and $P$ has order 2. It also can be seen from the formulas, case 2.

update

This is about the implementation issue that people can forget the checks;

Maybe the implementor instead has "+" check for its inputs being equal. But this is less likely as an implementation strategy: it produces a slower and more complicated implementation. Furthermore, it does not catch all the failure cases. For example, the standard Weierstrass addition formulas fail if Q happens to match -P. This will not be caught by random tests.

and

2007 Bernstein–Lange showed that the Edwards addition law is complete for every complete Edwards curve E. This means that, for every rational point P on E, and for every rational point Q on E, the Edwards addition law for inputs P and Q produces as output exactly P+Q. There are no exceptional cases. The Edwards addition law can be used for complete single-scalar multiplication, complete double-scalar multiplication, etc.

So, one addition law for all!


Why won't a BFT protocol using simple signing/voting work?

The purpose of a BFT is to achieve Byzantine Fault Tolerance rather than to be cryptographically secure. In fact, some BFT papers have no cryptography in them at all. You could devise a secure voting scheme but that doesn't automatically make it tolerant to byzantine failures.

Generally these algorithms seek to achieve liveness (eventual consistency of the data) and safety up to a certain number of faults, neither of these premises are present in your voting example. If you can guarantee through your protocol that even in the presence of a certain number of byzantine nodes (t < n) the protocol reaches consensus on a consistent state, then you have just created a BFT protocol.


What information about the ciphertext can an attacker discern if a key is used too many times?

If you are sending a single message, then you are basically fine. Of course, there is a very small amount of bias that can be leaked (for example, if two ciphertext blocks have the same value - and there's actually a very good chance that this is the case - then since you are using a permutation this leaks the fact that those two plaintext blocks are different).

However, the situation is very different if you encrypt many plaintext. This is because if there is a collision on the input, then the attacker will be able to get the XOR of the plaintexts (in which case it learns everything). Thus, this reduces to the question of whether or not a random counter repeats.
If you are sending many small messages, then there is a good chance that this will happen, so this is disastrous. If you are sending two messages, each of length $2^{32}$ blocks and you use a fully random CTR, then the question becomes what the probability is that the counters used in the two messages will "overlap". This is equivalent to the question of what the probability is that the two messages are of distance at least $2^{32}$ apart. This is actually very easy to compute for 2 messages: fix the first counter $CTR_1$ and then note that the next counter can be anywhere except for in the range of $CTR_1-2^{32}$ and $CTR_2+2^{32}$ (where addition is modulo $2^{64}$). This probability is easily computed at $2^{31}$. However, it is important to be aware that the probability degrades fast when you have more messages.

For the above reason, a better strategy for CTR mode is to break the counter up into two parts: the first part is chosen at random, and the second part is then what is incremented. This is often what is done for AES with the first part being 96 bits and the second part being 32 bits. This means that you can only encrypt message of length $2^{32}$ at maximum (otherwise, you break them into two and use a new counter). However, with a 64-bit block you still get very weak bounds. However, if you KNOW that you are encrypting only a few very long messages, then you can do something like this. If you KNOW that you are encrypting many short messages then you are in trouble.

Bottom line, 64-bit blocks these days are a problem...


First, and I know this isn't exactly the answer you're seeking, but I'd mull over it for a while. Hopefully you have read Schneier's Memo to the Amateur Cipher Designer; it speaks the truth.

In short, before you try to go the route of publishing your algorithm, here are some things you should consider:

What makes your scheme compelling to study? Is it more secure or more efficient than already-existing schemes like AES, Salsa20, Sosemanuk, ...? Is it interesting from a theoretical point of view? Does it solve some heretofore difficult problem? If none of these things, you might have difficulty generating interest in it.
What analyses have you done already? Does your scheme exhibit proper diffusion, e.g. does it possess a good avalanche effect? Do you have some proof of security contingent on the difficulty of another cipher/problem? (This is often not the case for encryption schemes, but it could have such a thing.) Have you verified that your scheme resists common cryptanalytic techniques like differential and linear cryptanalysis?
Are you prepared to justify everything in your design? And I do mean everything: cryptographers want to know details. Why did you do this, why did you do that, how did you generate those constants, could the constants be better? Why not improve on your design in such-and-such maybe-or-maybe-not-obvious way? How's your scheme's efficiency? Good, bad? Does the security level it provides justify its efficiency?
Who else has looked at your scheme? What are their credentials? Like Schneier says, anyone can make a cipher they themselves cannot break; the real test is having others try.

That said, you might already have considered all of these things and more, in which case I apologize profusely. Supposing you have, where can you publish it?

If you're more amateurish and looking for general community input, I'd pick somewhere like the /r/crypto subreddit and maybe try to hang around some other crypto-related spots on the web. If you're related with a university in some way, you might be able to track down cryptology researchers at yours, depending on your position and so forth.

If you're talking about more prestigious academia-related spots, I'd go with one of the IACR publications, where a great deal of cryptography papers are published. For general preprint hosting, almost all papers are submitted (at some point or another) to the Cryptology ePrint Archive, also ran by IACR. If you're familiar with academia, this is an arXiv-esque site for cryptology specifically.


He is talking about the original version of the Caesar Cipher where the substitution was just a +3:
A -> D
B -> E
C -> F
D -> G
E -> H
F -> I
G -> K
H -> L
...
X -> A
Y -> B
Z -> C

Because the shift is fixed, it does not have a key (but you could say it is a substitution cipher with a key equal to +3).
However it is common usage to call a substitution cipher as a Caesar Cipher because the idea the same but where you change the value of the shift.

The Caesar cipher is named after Julius Caesar, who, according to Suetonius, used it with a shift of three to protect messages of military significance. While Caesar's was the first recorded use of this scheme, other substitution ciphers are known to have been used earlier.
If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.
— Suetonius, Life of Julius Caesar 56 [source]


A well-known result is $gcd(t+i, n)$ over Gaussian numbers where $t$ is a square root of (-1) modulo $n$. The reason is $t^2 = -1 \pmod{n}$ equivalent to $n | (t+i)(t-i)$ over $Z[i]$. Real and img components of this $gcd()$ are the squares.


How to derive a hash function from another hash function?

The main conceptual trick here is the one used over and over in cryptography proofs, known as "reduction". Suppose that you have a problem $A$, which is assumed to be a "hard problem". You want to show that another problem $B$ is also a "hard problem". To do that, you imagine that you have some machine or system that can solve $B$; and from that machine or system, you build a solver for problem $A$; that new solver uses the solver for $B$ as an elementary block box. If you can do that, i.e. solve $A$ as long as you have access to a solver for $B$, then this shows that solving $B$ must be hard: an easy solver for $B$, used in your construction, will become an easy solver for $A$, which contradicts the hypothesis of $A$ being a hard problem.

I'll take an example with square roots modulo a big non-prime integer. This is an example meant to explain how a problem $A$ is reduced into a problem $B$, and vice versa. To follow this example, you don't need to fully understand the details of the involved algebra; what matters here is that we make solvers for some problems based on solvers for other problems.

Suppose that you have $n = pq$, where $p$ and $q$ are two unknown and big prime integers; you only have their product $n$. Finding $p$ and $q$ from $n$ is a hard problem; it is called integer factorization, and mathematicians have looked for efficient ways to do that for more than 2500 years, and they still don't know how to do it for large integers (current record is for a 768-bit integer $n$). This integer factorization is the problem $A$. We assume that it is hard.

Now consider the problem $B$: from an integer $x$ such that $1 < x < n$, find an integer $y$ such that $y^2 = x \bmod n$. This is basically finding a square root of $x$ modulo $n$; about 1/4th of integers $x$ in the $1..n-1$ range admit square roots, and if $x$ has a square root, then it will (usually) have four distinct square roots. We want to show that, in all generality, $B$ is a hard problem.

Suppose, then, that you have some system $S$ that can find a square root for any input $x$ (for any $x$ that has square roots, that is). We can then build a new system, that uses $S$, and can be used to factor $n$. It works in the following way:

Generate a random value $k$ in the $q$ to $n-1$ range.
Compute $t = k^2 \bmod n$.
Invoke the system $S$ on $t$. We build that $t$ as a square, thus it has square roots, and we already know two of them, which are $k$ and $n-k$. The system $S$ will return one of the four square roots of $t$; let's call it $u$.
If $u = k$ or $u = n-k$, we were unlucky. This happens half of the time. Start again with a new random $k$.
Otherwise, compute the Greatest Common Divisor of $n$ and $u+k$. This GCD will be either $p$ or $q$ with very high probability.

This algorithm shows how to factor a big integer $n$, provided that a square root extractor (system $S$) modulo $n$ is made available. Since integer factorization is hard, this should not be feasible.

The same concept works in the other direction in that case. What the algorithm above shows is that extracting square roots modulo $n$ cannot be easier than factorizing $n$. In the other direction, we can show that factorizing $n$ cannot be easier than extracting square roots modulo $n$: suppose that you have a machine or system $F$ that can factor big integers. Now, given an integer $n$ and an input $x$ for which you are challenged with finding a square root, you can do the following:

Call $F$ on the integer $n$ to get its factors $p$ and $q$.
Compute the square roots $y_p$ and $y_q$ of $x$ modulo $p$ and $q$, respectively. Modulo a prime, square root extraction is easily done with the Tonelli-Shanks algorithm.
Recombine $y_p$ and $y_q$ into a square root $y$ for $x$ modulo $n$, using the Chinese Remainder Theorem.

Thus, if you can factor integers, you can extract square roots. Therefore, integer factorization cannot be easier to do than extracting square roots: whenever you find an efficient way to factor integers, the algorithm above can be used to turn that into an equally efficient way to extract square roots.

Since integer factorization is not harder than extracting square roots, and extracting square roots is not harder than integer factorization, then both problems are equivalent. In particular, they must be either both hard, or both easy (in practice, as far as we know, they are both hard).

Now back you your problem of hash functions. You have a given hash function $H$, and it is assumed to be collision-resistant. This means that the "problem $A$" is about finding a collision for $H$: find $m$ and $m'$ such that $m \neq m'$ but $H(m) = H(m')$. The exercise supposes that problem $A$ is hard.

Now, problem $B$ is about the collision resistance of $G$: you are challenged with finding $m$ and $m'$ such that $m \neq m'$, but $G(m) = G(m')$. The goal of the exercise is to show that $G$ is collision-resistant, i.e. that problem $B$ is hard.

Therefore, the way to do it is to make a reduction: you first suppose that you have a solver for $B$, i.e. a way to make a collision for the hash function $G$. You want to show how you can use such a solver in order to make a solution for problem $A$, i.e. finding a collision for the hash function $H$. By describing such a method, you show that finding a collision for $G$ cannot be easier than finding a collision for $H$. Since $H$ was supposed to be collision-resistant, it follows that $G$ is also collision-resistant.

All you have to do, therefore, is to find out how a collision for $G$ can be turned into a collision for $H$ (and that I leave as an exercise, because the whole point is to have you find it by yourself).


No, an attacker listening to the SSL connection is unable to get a copy of the keys.

This is actually a fairly fundamental property of SSL (or any other protocol that encrypts traffic); we're encrypting the traffic because someone might be listening in, and we want to prevent them from being able to understand the traffic.  We do this by having the two side share keys, and using those keys to encrypt the traffic.  If the guy in the middle could recover the keys, they could listen in.  Hence, any encryption protocol must have some story why someone in the middle cannot recover the keys.

Actually, SSL can do it a number of ways, depending how what the two sides agree on (the "ciphersuite").  I'll describe the most common method.

This method (which I believe is used when, say, you're doing a connection with Amazon) depends on the magic of Public Key Cryptography.  What this allows us to do is have one side (the Server) generate two related keys, the "public key" and the "private key".  Someone can encrypt a message with the "public key"; however the public key does not allow you to decrypt; in essence, it acts as a "one-way" box.  However, someone with the private key can decrypt messages.

So, here is a simplified summary of it works: you (the client) ask the Server for a copy of its public key; it gives it to you.  Then, you pick a random value (the "premaster secret"; at your level, you can think of it as the session key), and encrypt that with the servers public key, and send that.  The server then receives the encrypted value, and then decrypts it.  At this point, both sides share the same premaster secret (the client because it originally picked it, the server because he just decrypted it), and so can use that value to come up with the session keys.

Now, here is what someone in the middle hears:

The Server's public key.
The random value encrypted with the public key.

Now, the Server's public key does not allow him to decrypt the random value (remember, the public key allows only encryption), and so he cannot learn the value that was shared.

Now, if you think about this, one thing may occur to you: how does the client know that the public key he got was actually the Server's public key; couldn't someone who can modify messages in the middle substitute his own public key and pretend to be the server?  Well, SSL does have defenses against that; however, that involves more Public Key Cryptography, and so I'll leave that out for another day.


Can we build two messages with same MD5 but different size?

This answer was moved following closing of the question.


Recover elliptic curve order from ECDSA signatures

Actually, you can recover $n$ from ECDSA signatures (assuming that you can obtain several signatures with the same $k$ value, which means that the ECDSA signature implementation is broken); however it would require 3 such signatures (if you don't mind factoring a value circa $n^2$), or 4 such signatures (if you don't have that many resources conveniently at hand).

Each ECDSA signature has:

$$s_i = k^{-1}(h_i + rd) + m_i n$$

where:

$k^{-1}$ is the inverse of the (unknown) common $k$ value
$h_i$ is the known hash of the $i$th message signed
$rd$ is the common unknown product of the value $r$ (which we do know, and is constant if $k$ is constant), and the secret key $d$.
$n$ is the unknown curve order we're trying we're trying to recover
$m_i$ is the unknown value that is added as a part of the $\bmod n$ operation (it is selected to make sure $0 \le s_i < n$, however we don't care about that.

Now, if we compute $(H_3 - H_2)(s_1 - s_2) - (H_1 - H_2)(s_3 - s_2)$, you'll see that the $k^{-1}(H_i + rd)$ portions cancel out; leaving us with $m \cdot n$, with the size of $m$ approximately the same as $n$.  If we can factor $mn$, we can do so and this will immediately give us $n$ (and possibly a false hit).

If $mn$ is too large for us to factor conveniently, we can then take a fourth such signature, and compute $(H_4 - H_3)(s_2 - s_3) - (H_2 - H_3)(s_4 - s_3)$; this gives us $m' \cdot n$ (for an $m'$ likely unrelated to $m$); computing $\gcd( mn, m'n )$ immediately gives us $\gcd(m, m')n$; even if $\gcd(m, m')>1$, it is likely small, and so easy to remove.


Estimated entropy per bit given P-value of a statistical test, and number of bits tested?

Firstly, the way (if at all) the "$P$-value" depends on $H$ depends (of course) on the statistical test that is being used. For each test, the result will be different and I cannot really give a meaningful general discussion here because different tests consider completely different aspects of the stochastic process of output bits.

In general, indeed, the $P$-value doesn't have to depend on $H$.
Originally I (probably incorrectly) thought you were referring only to a particular test (the monobit frequency test), which is what my comment was referring to.
I'll use this particular test in my answer to illustrate that the $P$-value can depend on $H$ and hopefully you'll be able to generalize my approach to other tests that are of interest to you. The analysis will be the same for many tests, but it will often be impossible to get any closed-form expressions relating the $P$-value and $H$.

Before I start with the analysis of the monobit frequency test, I'll also answer your question about the truth of the sentence

  For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%.

A $P$ value larger than 0.001 means that we cannot reject the hypothesis that the sequence is random at a significance level of 0.001. In this sense the sentence is imprecise: it is not because our test would have produced our observation with high probability that the observation was produced by a TRNG. At all times one should remember that the formula for computing the $P$-value is derived under the assumption that the hypothesis is true.

Analysis of the monobit frequency test

I'll now discuss the monobit frequency test, which is defined in NIST SP 800-22 (section 2.1). My notation is a little different sometimes, but I think it should be clear enough (if not, please comment).

In the most general sense, even this analysis would be difficult: at most one can say that the probability distribution of the $P$-value depends on the entropy $H$, but you should probably forget about getting a simple relation (formula of some kind) in the general case.

The following part of your question (applied to the monobit frequency test) has a reasonably "nice" answer though:

  If that's not answerable as it, does it remain so when we add
  some very general hypothesis on the structure of the RNG under test,
  like: it outputs independent bits with some unknown constant bias?
  Refine this additional hypothesis as needed to obtain some relation
  between $P$, $n$ and $H$!

So we've already made the assumption of working with a particular statistical test, because we can't answer the question otherwise. Now I'll make the following assumptions about the RNG:

There is no dependence whatsoever between the output bits of the random number generator.
The RNG is outputs a $1$ with a fixed probability $q$ and a zero with probability $1-q$. To get a a nice formula, I'll assume $q = 1/2 + \epsilon$ with $\epsilon$ sufficiently small such that $\epsilon^4 \approx 0$. I'll refer to $\epsilon$ as the bias.
$n$ is sufficiently large, but this assumption is implicit in the test anyway.

What I will show is that, under these assumptions, the probability distribution of $P_n$ (this is just $P$ for a specific value of $n$) depends on the entropy $H$. Note that I'm going to use $P_n$ as a random variable and $p_n$ for an instantiation of this test statistic. Once the distribution of $P_n$ is known, we can answer the following question:

  What is the probability that the source entropy is $H$ given that the observed value of the $P$-statistic is $p_n$?

To obtain an answer to this question, we need to take the following steps

Write the bias $\epsilon$ in terms of the entropy $H$.
Compute the probability distribution of the test statistic for the biased RNG.
Compute the probability distribution of the $P$-value for the biased RNG.

Entropy and bias

The entropy $H$ of one bit of the RNG is given by

$$
H
= q \log_2\left(\frac{1}{q}\right) + (1-q)\log_2\left(\frac{1}{1 - q}\right)
= 1 - \frac{2\epsilon^2}{\log 2} + \mathcal{O}(\epsilon^4),
$$
where $\log$ is the natural logarithm.
Hence, we have approximately:

$$\epsilon \approx \pm\sqrt{\frac{\log 2}{2}(1 - H)}.$$

It shouldn't be surprising that there are two biases corresponding to the same entropy. For convenience, I'll use the positive value in the remainder of this answer. This means I assume that it is known that the RNG is positively biased.

Test-statistic

Let's call our sequence of output bits $X_i$. We're looking for the distribution of the following sum:

$$S_n = \sum_{i = 1}^n (-1) ^ {X_i} = 2\left[\sum_{i = 1}^n X_i\right] - n$$

Since the $X_i$ are assumed to be i.i.d. we have, asymptotically as $n \to \infty$:

$$S_n \sim \mathcal{N}\left(\epsilon \, n, 4p(1 - p) \, n\right).$$

Both the mean and the variance can then be rewritten in terms of the entropy $H$ (recall that for the mean, there are actually two possibilities). To express the variance in terms of $H$, note that

$$p(1 - p) = 1/4 - \epsilon^2 \approx 1/4 - \frac{\log 2}{2} (1 - H).$$

$P$-value

The $P_n$-value for our test can be computed as

$$P_n = 2\Phi\left(\frac{-S_n}{\sqrt{n}}\right).$$

So we can compute the probability that $P_n \le p_n$ for some value $p_n$:

$$
\Pr[P_n \le p_n]
= \Pr\left[2\Phi\left(\frac{-S_n}{\sqrt{n}}\right) \le p_n\right]
= \Pr\left[S_n \ge -\sqrt{n}\Phi^{-1}(p_n/2)\right].
$$

Now we can use the distribution of $S_n$ which we derived earlier:

$$\Pr[S_n \le s_n] = \Phi\left(\frac{s_n/\sqrt{n} - \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H)\log 2}}\right).$$

So we get

$$
\Pr[P_n \le p_n]
= \Phi\left(\frac{\Phi^{-1}(p_n/2) + \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H) \log 2}}\right)
$$

(in the somewhat unlikely case that my calculations contain no errors, I'll check them later).

Note that as $n \to \infty$, the above probability goes to $1$ (for $H \neq 1$) so given enough sample bits we'll eventually conclude that the sequence isn't random.
So that should also answer your question

  How can we refine this, given $P$-values $P_i$ for that experiment repeated
  $k$ times?

(at least in this specific case)


Can I use a differential that can be traced through the whole cipher with 100% probability?

Usually differential cryptanalysis relies on something called the "wrong key randomization hypothesis", which is the assumption that decryption of the last round with the wrong key results in a random difference at the beginning of the last round, while decryption with the correct key will result in the expected difference with the probability of the differential (which hopefully is sufficiently high or low as to be distinguishable from a random difference).  However, if there is a probability one differential going through the entire cipher then by definition that means that decryption with any key will lead to the same difference.

You might try linear cryptanalysis instead.  A probability 1 linear characteristic through the entire cipher will give you 1 bit of the key with just a single known plaintext (Edit to add: poncho adds a good clarification - the probability 1 linear characteristic must involve at least one key bit to be useful for Matsui's algorithm one).  If for some reason there is no linear characteristic through the entire cipher, then you could try differential-linear cryptanalysis using that probability 1 differential through most of the cipher and a short linear characteristic at the end.


Correctness in Multi-party Computation: Real/Ideal Paradigm in Malicious case

1- $\:$ I believe correctness does not have an exact meaning in this context.

It would certainly involve not letting the distinguisher see the transcript,

and might involve not letting the distinguisher see the adversary's randomness,

and possibly involved not even letting the distinguisher see the auxiliary input.

2- $\:$ [Computational/Statistical/Perfect] correctness is implied by

[computational/statistical/perfect] indistinguishability of the Real and Ideal cases,

since the distinguisher gets to see the honest parties' outputs.


Is there a proof for showing any cryptogram is crackable?

Not all ciphers can be broken, even by infinitely powerful adversaries.

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need at least as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (e.g. by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.

To illustrate this, consider what happens if one tries to brute force OTP:
 Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the corresponding plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to every possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0, 1, 2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.

Most cryptographic methods we use now are computationally secure. There are lots of different ways to show this, and I'll just sketch two of them below:

We might come up with a reduction to a problem conjectured to be hard (e.g. the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve Some-Hard-Problem".
Meaning our problem is at least a difficult to solve as Some-Hard-Problem. So, if the problem is indeed hard to solve, then so must be cracking our encryption.
Another method used is that you might be able to prove a lower bound on the effort required to break a cipher, in terms of some security parameter. Then, the security parameter can be set such that this lower bound is higher than the strength of any computer that could possibly be built. Notice, the infinitely strong computer described in the question could still break such a scheme, but we could fix the parameter so high that it would be impossible to make a computer that could break it.

Possibly of interest: wikipedia:provable security


What is the difference between computational complexity and time complexity?

There are many different cost models for computation, of which time (measured by some clock) is only one.

How many seconds must we wait to run this algorithm? [time, measured in seconds]
How many CPU cycles does it cost run this algorithm? [time, measured in CPU cycles]
How many bits of memory does this algorithm use? [space]
How many NAND gates does it take to represent this algorithm as a logic circuit? [NAND metric]
How many bits are in the description of the program, how many bits of memory does it use, and how long does it take to run assuming a bit operation and a memory reference each take one unit of time? [RAM metric]
How large a silicon die does it take to run this algorithm, and for how long must we power it? [AT metric]
How many joules of energy will it cost to run this algorithm? [energy]
How many yen does it cost to run this algorithm? [pocketbook]

The answer to each of these questions may be a complicated function of the size of the input, or of the input itself.  For example, the worst-case RAM cost of quicksort is a quadratic polynomial function of the input size, $an^2 + bn + c$, for some coefficients $a$, $b$, and $c$ that depend on exactly how we write it, while on optimal inputs the RAM cost is $u n + v$.

Complexity theory is usually not concerned with the coefficients $a$, $b$, and $c$ but with the degree of the polynomial, $O(n^2)$ vs. $O(n)$, or other qualitatively different shapes of growth curves like $O(2^n)$, $O(\log n)$, $O(A^{-1}(n))$ where $A(n)$ is the Ackermann function, etc., in whichever cost model you're considering.

Computational complexity may refer to any of the cost models; time complexity usually just refers to the time-based ones—for example, the time complexity of heap sort is $O(n \log n)$ while the space complexity is $O(n)$, assuming memory access cost is constant, yet in the more realistic AT metric the best-known cost of sorting a length-$n$ array of $n$-bit numbers is $n^{1.5 + o(1)} = (n\sqrt n)^{o(1)}$ owing in part to communication costs on a silicon mesh.

The last three cost models are the really important ones for studying cryptanalytic attacks, because they are connected to real-world economic costs of attacks: the AT metric, which is easy to formalize and study for algorithms, is a good proxy for the energy cost, and energy cost essentially determines pocketbook cost.


Why does nobody use (or break) the Camellia Cipher?

There are a variety of reasons why AES is more widely used:

AES is a standard.
AES has been vetted by cryptanalysts more extensively than Camellia.  As a result, we can have greater confidence in the security of AES than in Camellia.  Therefore, on the merits, there may be good reasons to choose AES over Camellia.
AES is a government standard (FIPS).  Government procurements may be required to comply with applicable government standards.  Therefore, when selling to the government, AES may be required; if so, Camellia isn't an acceptable substitute.
AES is a industry standard.  No one will get fired for using AES. If (say) Apple uses AES, and AES gets broken, the newspaper headline won't be about Apple; it'll be about flaws in something everyone is using. On the other hand, if Apple uses Camellia and Camellia gets broken, the newspaper headline will be about why Apple took it upon themselves to deviate from industry standard practice and how that led to a security breach in their systems.  Therefore, aside from its merits, there's an incentive to choose the industry standard.
Camellia is patented.  AES is unpatented and free for all to use, without patent encumbrances.  Regardless of what licenses might be available, many people are a bit wary about any patented algorithm, due to uncertainty, IP risks, etc.  If the unencumbered version is every bit as good, it's easier to use the unencumbered version.  Also, it is possible that some open source crypto library developers may be less likely to implement Camellia, because of the potential patent situation or because of the reduced demand to the above factors, so standard crypto libraries are less likely to Camellia.  Similarly, many standards bodies have a bias against patent-encumbered algorithms, when there are alternatives that are every bit as good; therefore, some standards bodies may be less likely to use Camellia when they standardize on network protocols that require crypto.
AES is entrenched.  AES is a brand name that is widely known and recognized.  Also, AES is good enough.  Camellia is newer, and the benefits of Camellia are unclear or not as well known.  (In many contexts, Camellia has no obvious advantages, so a developer might not see any reason to adopt it instead of AES, if they already know and trust AES and consider AES adequate for their needs.)  There's no shortage of other block ciphers out there that could be considered, but if AES is good enough, there's not much incentive to use them.


Recovery of RC4 key when S-box 0 stage or 1st stage known

I have some RC4 ciphertext which I know it's plaintext and I would like to extract the key just from cipher and plaintext.

That turns out to be a hard problem; the only practical way known is to brute force the key, and see if you can find a key that generates a keystream that is consistent with the known plaintext/ciphertext.

That is infeasble if the key is large; however it's the only known method that has much of a chance at all of working.

  While reading through "RC4 Stream Cipher and it's variants" by Goutam Paul I came a cross (4.1.1) PRGAreverse algorithm on p.65 (Chapter 4.1) providing candidates for S by supplying to it a state of S and state number

If what you have is the plaintext and the ciphertext (and nothing else), this algorithm doesn't help you.  The reason it doesn't is that it assumes that you know the state of the internal permutation S at some point; the plaintext/ciphertext doesn't give you that.  The best known algorithm for recovering the permutation given what you have turn out to be totally infeasible for standard RC4; you'd be better off attempting a brute force of the key.


AES Message Authentication Vulnerability

If this is simply the AES permutation on a single block, it's hard to find such a pair.

If it's AES-ECB with multiple blocks, you can pick each block from either (x1,y1) or (x2,y2), producing a new message that contains parts from each of them.

With other modes it depends on that mode, but with many modes there will be a similar mixing attack as for ECB.


How can we generate a shared key from two key pairs for an ECC implementation?

The diagram leaves out something (rather assumes it implicitly), which is that you and the recipient have agreed upon curve parameters / a standardized curve with which to perform key exchange. We can derive the shared key as follows once we agree upon parameters (this method is basically elliptic curve Diffie Hellman):

Use the RNG to generate an integer $d \in \mathbb{Z}_q$ where $q$ is the order of the generator point $G$ of the curve (technically $d$ can be arbitrarily large but there's no advantage to this).
Your ECC key pair is then $(d, Q)$ where $Q = d*G$. $d$ is the private key, $Q$ is the public key. Note that $Q$ is a point on the curve.
Given the recipients public key $R$ (also a point on the curve) compute $S = d * R$. $S$ is the shared secret. (Note that if $e$ is the recipients private key that means $R = e * G$, and thus $S = d * e * G$, meaning if we send the recipient our public key $Q$ they can also derive the secret $S = e * Q = e * d * G$).

Now we have shared key material we can pass into a KDF to derive symmetric keys.


Is this commutative encryption protocol secure?

Yes it is possible for a passive eavesdropper to recover the secret $P$.

Here's how:

The attacker observes $C_1,C_2,C_3$ and formes the XOR of all those values. That's it, the result of $C_1\oplus C_2 \oplus C_3=P\oplus F(K_1,IV_1)\oplus P \oplus F(K_1,IV_1) \oplus F(K_2,IV_2) \oplus P \oplus F(K_2,IV_2)=P$ yields the desired plaintext.


Security guarantees of Shamir's secret sharing when some co-efficients are zero

The coefficients must be uniformly chosen. If you do not choose your coefficients uniformly, then by Kerckhoff's principle, the attacker knows this, and that makes it easier than normal to reconstruct the polynomial, and thus to obtain the secret.


To understand what a pseudo-collision attack is, we first need to understand how a hash function internally works:

Most hash functions are basically composed out of four functions:

An initialization function that just sets a bunch of start values for the state: $I:\emptyset\rightarrow \{0,1\}^k$
An input pre-processing function that computes some values based on the message and possibly hidden context: $P:\{0,1\}^l\rightarrow \{0,1\}^q$
A state-update function, sometimes also called "compression function" that takes the current message block, the associated pre-processing and the current state and outputs a new state: $U:\{0,1\}^l\times\{0,1\}^q\times \{0,1\}^k\rightarrow \{0,1\}^k$
An output function that takes the state and outputs the hash digest: $O:\{0,1\}^k\rightarrow \{0,1\}^o$

Now a normal collision attack takes the standard composition of these functions and tries to find a collision.
A pseudo-collision attack on the other hand just tries to find a collision on the state-update function. So an attacker is interested in finding two triples $x=(m,p,h),x'=(m',p',h')$ such that $U(x)=U(x')$ with $x\neq x'$.

The application of this is more or less clear: To show weaknesses in the core update function and give insights into possible paths to full collision attacks.
For additional discussion also see these slides (PDF).

When I originally wrote this answer I screwed the concepts up, so here you have the definition and use of a "near-collision-attack" as well as a bonus:
The term "near-collision-attack" and the associated term "near-collision" aren't as "strictly" defined as "collision-attack" and "collision" however I'd define a nearcollision-attack as follows:

  Given a hash function $H:\{0,1\}^*\rightarrow \{0,1\}^n$ find $x_1,x_2$ with $x_1\neq x_2$ such that $\Delta(H(x_1),H(x_2))$ is low but not zero. Here $\Delta(x,y)$ denotes the Hamming distance between the two input strings, i.e. the number of set bits of $x\oplus y$.

The application of these attacks is clear: Suppose you authenticate files by providing a hash for human verification over a secure channel. As humans are lazy they probably won't spot the difference (if it is small as it is here) between the computed hash and the transmitted hash in case of a pseudo-collision.
As a real-life example ask yourself: When you verify an MD5 / SHA1 hash of a file, do you actually look at all the hex digits or only at the first few and the last few?


You aren't telling us exactly what you plan to do, but plenty enough that we can tell you: no, just no.  The first mistake you're making is that you're talking about "files" in a way that's worrisome in the context of cryptography.  In modern programming parlance, cryptography by default deals with immutable values, not with mutable objects.  But when you talk about "files" in this question it is evident that at least on some occasions you mean a mutable object, one into which different values are written and overwritten at different points in time.

So the cryptographic requirement that you never use the same key+IV pair to encrypt more than one value then applies not to the file as a unit, but to each operation that encrypts a value to be written into the file.

  Is it safe to use the same IV and Key on only one file.

Generally, no.  There are special cases where it's safe, if for example you're using files in a strict write-once never-modify manner, where you're only ever writing to a file at the time you create it.  But that's not what you're proposing to do:

  Is it safe to use the same IV each time I access and add data to the file. Each time this happens, there will only be one encrypted file so multiple files with same IV and Key will not happen.

No.  Each time you wrote to this file you'd be encrypting a different value with the same key and IV, and that violates the IV reuse condition.  Note that the likely practical consequence of this is that your file format will need to be structured to support encryption—for example, you might need to build some notion of "data block" within the file format, so that each data block can be encrypted with a different IV, and the metadata necessary to identify block boundaries and their IVs is present.

  The program using the file will just add data to the end of the file. From what I could find, this will not change the encryption of the first sections of the file, as the IV is changed based on what was done in the previous block. Is that correct?

It sounds like you're looking at some materials that describe CBC mode encryption.  This idea that the IV changes based on what was done in the previous block is likely not something that happens automatically, it'd be something you'd have to understand and implement—which is an error-prone and risky undertaking.  CBC also doesn't provide authenticated encryption, which means that you likely would need to add some sort of message authentication, which makes the whole thing even harder to get right—for example, the recent Efail vulnerability on GPG and email clients hinges on this.

Whatever you're thinking of doing is likely a minefield.


How to do Hexadecimal multiplication in GF(2^8)

You cannot use (just) a bit shift to multiply by $7$.  Not in ${\rm GF}(2^n)$, and not in normal arithmetic either.

Shifting a number left by one bit always multiplies it by two, and shifting a number left by multiple bits is just equivalent to shifting it left by one bit several times.  So shifting a number left (by one or more bits) always multiplies it by a power of two.

To multiply a number by a factor that is not a power of two, you need both shifting and addition (which in ${\rm GF}(2^n)$ is actually bitwise XOR).  For example, $7 = 111_2 = 4 + 2 + 1$, so $7a = 4a + 2a + a$ for any $a$.  So, to multiply some number $a$ by $7$, you can first calculate $2a$ and $4a$ by shifting $a$ left, and then add those together with $a$ itself (always remembering that, in ${\rm GF}(2^n)$, addition is actually XOR and that any results with more than $n$ bits will need to be reduced modulo the field polynomial).

More generally, we can do general multiplication in ${\rm GF}(2^n)$ by splitting one of the numbers being multiplied into a sum of powers of two (which is really easy if we're working on a binary computer), use bit shifting (and modular reduction) to multiply the other number by those powers of two, and then add the results together.  Here's some pseudo-C code to illustrate this:

const int overflow = 0x100, modulus = 0x11B;  // AES GF(2^8) representation

int gf2n_multiply(int a, int b) {
    int sum = 0;
    while (b > 0) {
        if (b & 1) sum = sum ^ a;             // if last bit of b is 1, add a to the sum
        b = b >> 1;                           // divide b by 2, discarding the last bit
        a = a << 1;                           // multiply a by 2
        if (a & overflow) a = a ^ modulus;    // reduce a modulo the AES polynomial
    }
    return sum;
}

Note that you could easily turn the code above into a normal integer multiplication routine by replacing sum ^ a with sum + a and removing the last line in the while loop that reduces a modulo the AES polynomial after it has been shifted left.  Those are the only ways in which Galois field arithmetic, as used in this code, differs from normal integer arithmetic.

Also note that, while the code above should work (in the sense of producing the correct results), it's probably not something you should use in production crypto code.  Not only is it not particularly well optimized, but its running time depends on the value of b, which is generally not desirable if b might contain sensitive data that you don't want to leak.

(BTW, at this point you might be wondering if it wouldn't be more efficient, for example, to calculate $7a$ as $8a - a$ instead.  Unfortunately, while that would work fine in normal integer arithmetic, addition and subtraction in ${\rm GF}(2^n)$ work differently, and we actually have $8 - 1 = 8 + 1 = 9 \ne 7$.  But adding together distinct powers of two still works the same way in ${\rm GF}(2^n)$ as it does with normal integers, so we can still usefully work with the binary representation of numbers.)


What is the purpose of pre master secret in SSL/TLS?

The point of a premaster secret is to provide greater consistency between TLS cipher suites. While RSA cipher suites involve the client sending a random 48-byte premaster secret directly to the server, other suites do more complex things to generate the secret, and end up with a secret that might have some structure to it. For instance, (EC)DH suites use (elliptic curve) Diffie-Hellman to negotiate the secret; the output of this can be longer or shorter than 48 bytes, and it might potentially be poorly distributed (which could be bad). For PSKs, it's even worse - the premaster secret basically is the PSK. For various reasons, it's nice to have the master secret be some consistent format; it lets you separate the key-exchange side from the encryption side. Likewise, it's nice to have the master key be pseudorandom.

While you could require key exchange mechanisms to output the master secret directly meeting specific requirements, just about every key exchange system would do it the same way anyway (i.e. pass the negotiated value through the TLS PRF). Since most key exchange methods result in a shared secret that needs some transformation, and that transformation works well for basically every key exchange method, they just put it in the TLS spec for all methods to use.


Computing youngest person among 3 while keeping ages private

There might be better ways to do this, but I wanted to do it with only primitives found in VIFF (why? because it is the MPC framework I am most familiar with). There could be specialized protocols which are better.

In VIFF, we have access a primitive >= which returns 0 or 1 (false or true). We can do the comparison you seek using that plus some simple arithmetic on secret shared values. I think these are all passive protocols and do not guarantee fairness (if fairness even makes sense in the passive world).

Let the three parties be alice, bob and charlie. They have each secret shared their ages with the others. We'll let a,b,c be the variables that represent the secret shared ages.

We can compute who is the youngest as follows:

ab = (b&gt=a) # is a younger than b?
ba = 1-ab # is b younger than a?
ac = (c&gt=a) # is a younger than c?
ca = 1-ac # is c younger than a?
bc = (c&gt=b) # is b younger than c?
cb = 1-bc # is c younger than b?

a_score = ab + ac
b_score = ba + bc
c_score = ca + cb

# At this point we are guaranteed to have a score of 2, a score of 1, and a score of 0.
# Whoever has the score of 2 is the youngest.
reveal(a_score&gt=2) # if this is 1, then Alice is youngest
reveal(b_score&gt=2) # if this is 1, then Bob is youngest
reveal(c_score&gt=2) # if this is 1, then Charlie is youngest

This computation only reveals who is the youngest. It does not reveal ages or the overall order. It requires 6 calls to >=. This will also only return 1 person as youngest. To get all of the youngest, you would replace the 2nd, 4th, and 6th lines with another >= instead of a 1-XX.


Figure out algorithm to numeric key generator with one known input and output

Ideally there would be some utility or a formula that I could apply or tweak here.

I have to say there is no such utility, no such formula. This problem has no solution.

There is 10000! = factorial(10000) different transformations of 4-digit numbers to 4-digit numbers. For instance, your input 7153 and result 9533 can be produced by any of the following functions:

f(x)=(2x+5227) MOD 10000

f(x)=(3x+8074) MOD 10000

f(x)=(x^3+8956) MOD 10000

Knowing a single pair is not sufficient to find out what transformation was used. If they use some simple function, then having more pairs might give (without guarantee) an insight about this function.


Running time of Shamir's secret sharing scheme

Is the running times of corresponding steps true?

No.

Step 3 of the dealer has to be executed $n$ times (once for each party) with each execution taking $O(t)$ time. So it must be $O(t\cdot n)$.
Step 4 of the dealer needs $O(n)$ to distribute each share to every party.

I count $O(t\cdot n)$ as the overall time complexity for the dealer. Of course, you can make it more specific, because the time of all calculations depends on the size of $p$.


Discrete log problem exponential runtime

wouldn't that just be quadratic time?

No.

TLDR: modular arithmetic.

You may have an impression that it should be easy and takes a small number of steps. But the complexity comes from the fact that we use modular. In a normal arithmetic you know for instance that if $a < b$, then $g^a < g^b$ (for N). But in the modular arithmetic there are no such rule.

Example:

Let's take $g = 2099$, modulo $M = 2179$ and compare 1787, 39 and 1279,
What is greater, $g^{1787}$, $g^{39}$ or $g^{1279}$?

$g^{1787} = 999$

$g^{39} = 1000$

$g^{1279} = 1001$

We see that $g^{1787} < g^{39}$.

Other view on the same numbers. The equation $g^x = 1000$ has solution $x = 39$. Knowing this, can we guess what is solution of the equation $g^x = 999$? Is it close to $39$? No, it is not close. The solution of $g^x = 999$ is $x = 1787$.
There is no simple correlation.

That's why in the modular arithmetic to solve an equation like $g^x = 999$ we have to check every number. If $G = \{1, 2, ..., 10 000\}$, we have to check all these numbers. And if $G = \{1, 2, ..., 2^{512}\}$, we have to check all these $2^{512}$ numbers. In the reality some mathematical properties allow us to skip some groups of numbers and thus to reduce needed calculations. Nevertheless, even if the optimization would reduce that to $2^{256}$, still this would be pretty much work to do. The whole computer power on the Earth will not be sufficient to check all relevant numbers in trillions of years.


It is $O(1)$ time and space because the Blowfish block cipher has a constant bound on the key size (≤448 bits) and a constant block size (64 bits) and those are the only inputs—there are no variable-size inputs.

If you apply Blowfish in a composition like CBC then it is expanded to work on $n$ blocks by applying the Blowfish block cipher $n$ times, so it costs $O(n)$ time and $O(1)$ space.

P.S.  FYI, Blowfish is obsolete, and has been for decades since the standardization of AES in the late '90s.  There is no reason to use it today, and strong reasons not to use it or any other 64-bit block cipher.


What is the purpose of salting when integrating PBKDF2 with AES?

One reason is to mitigate from the Rainbow tables which is the work of  Oechslin. If everybody uses the same salt, one can build a Rainbow table for cracking everybody's passwords. There are even commercial tables for sale (I'm not advertising them just providing the existence). Using the salt for key derivation and passwords simply kills the usage of Rainbow tables. Rainbow tables are still useful if there is a multi-target attack, especially for block-ciphers.
The other not good reason is deriving two different keys by just one password. For example, if you want to encrypt with AES and then HMAC, you will need two keys. By using two salts you can get two keys. The below is from Crypto module of Python.

$$\operatorname{PBKDF2}(password, salt, count, dkLen, prf)$$

The iteration (count) should be larger than 16 to make harder the job of passwords crackers like hashcat. 65536 or depending on the user experience, waiting more than 1 seconds may not be a good experience so you can adjust it according to the system.
dkLen is the derived key length with default. It can be increased upto $2^{31}-1$ times the output size of the hash function. You can increase it to derive AES and HMAC key with one salt or you can use domain separation with two salts.
Actually, for deriving Multiple Keys can be risky with PBDKF2, once your password is found the two keys are gone. You can use PBKDF2 to generate a key and then use KDF like HKDF, rfc5869
$$key = \operatorname{PBKDF2}(password, salt, 65536, dkLen, \operatorname{SHA256})$$then use the key with HKF for different contexts with context

$$\operatorname{AES-KEY} = \operatorname{HKDF-Expand}(key, \text{"aes-key"}, 128)$$
$$\operatorname{HMAC-KEY} = \operatorname{HKDF-Expand}(key, \text{"hmac-key"}, 256)$$
In this case, you don't need the Extract mechanisms of HKDF, PBKDF2 does it.

If you want to send an encrypted message to someone then the generated key must be sent. For this kind of problem, we have a better alternative like DHKE, libsodium crypto box, or RSA-KEM which are based on public-key cryptography. In RSA-KEM we don't use PBKDF2 to derive a key we use KDF like KDF1 or HDKF.
PBKDF2 can be used in the protection of passwords in the login systems or key generation like in Veracypt, disk encryption utility. Veracypt can use the PBKDF2 with RIPEMD160 hash function to derive a Key Encryption Key to decrypt the actual encryption key. The iteration is 327661 for system partitions and 655331 for other containers. In order to, access the files again yo need to use not only your password but also the same parameters; salt, and iteration count. Otherwise, you cannot access the encrypted files. The Veracrypt handles the parameters for you, they are not kept as secret!

The new alternative for PBKDF2 is the Argon2 which is the Winner of the passwords hashing competition, in 2015. Argon2 can increase the used memory during calculations that can prevent the massive parallel hash calculations with GPUs. Hashcat can calculate

1173.1 kH/s for PBKDF2-HMAC-SHA1 and
277.0 kH/s for TrueCrypt PBKDF2-HMAC-RipeMD160 + XTS 512 bit

based on Nvidia GTX 1080 hashcat performance. *

note that the salt is not secret, only your password is secret here. Once you use a proper system then the attacker's ability is guessing your password. Therefore you must use strong passwords.

* Unfortunately there is not Argon2 to compare


Is there a checksum that gives the same checksum when in a text file?

For a checksum such as CRC16 or CRC32 it is very much possible to have a value over a text that contains the same CRC value (in whatever format, be it binary, hexadecimals or base 64). The proof of this is simple: you can simply put e.g. 32-48 bits counter at the end of the text and wait until you find a CRC. But in practice you can just calculate the value you need to prefix, append or anything in between and get the right CRC - if it is included or not. Checksums such as CRC are not secure.

For secure hash functions this is not possible. It is even computationally not possible to find any message $m$ where the hash value is $h$, for any chosen $h$ (that is not a known hash value). This is a much stronger presumption than the one you are proposing. It is not possible to find $x = \operatorname{H}(a | \operatorname{encode}(x) | b)$ even if you can chose any special value of $a$ and $b$, and any $\operatorname{encode}$ operation.

It is not possible to prove above completely for the simple fact that the security of hash functions cannot be proven. SHA-1 was thought to be secure for a long time, but by now it might be possible to create a text where the hash value is included.


Does it necessarily mean that an RSA moduli generated with poor randomness is not random?

If each key was generated by selecting two random primes of the desired length then the chance of two keys with a common prime would be incredibly small. If i'm reading How are primes generated for RSA? correctly there are about 2^502 possible 512 bit primes (prime length is half modulus length, so a 1024 bit RSA key would use 512 bit primes).

Since keys have been found which share a prime and the chance of that happening with randomly selected primes is so incredibly small the only reasonable conclusion is that the primes were not selected randomly.


Encryting data with password for local storage using libsodium

A nonce ensures that the same plaintext will always be mapped to different ciphertexts using the same key. Schemes requiring a nonce should always get a nonce, even for file-encryption you can't guarantee that your users won't encrypt the very same file twice, for reasons only known to them.

Now to answer your questions:

Authenticated encryption (AE) is always the mode of choice, except for full-disk encryption (FDE), where you'd have a severe penalty. But as you don't do FDE, AE is the right choice for you.
Regarding the nonce, you have several possibilities.

You can store it in plain before your file.
You can use your password based key derivation function (PBKDF) to derive the nonce in the same call as you derive the key.
(not recommended) You could hold it constant, assuming the key is different each time.
(not recommended) You could increment it always, but generating at random is easier concerning management I'd say.

Using a different salt each time won't hurt you, but reusing the salt may hurt you, so don't reuse salts. Using always the same salt may end up in same keys (as soon as a user supplies the same password twice) and salting is used to prevent "known-hash" attacks, which in fact fails it purpose if you reuse the salt and an attacker can simply try pre-calculated values. So use a different (unpredictable) salt in each case.
Where should you store the salt? The salt don't need to be secret, so you can store it in plain at the beginning of the file.


Often I hear the key expansion is the weakest part of AES, but conflictingly that it was designed to prevent the use of "weak keys" which its precedent suffered from.

The terms "weak" here mean different things.

Some of the best attacks on AES have been oriented at attacking the key schedule. When these attacks were released the cryptographic community was not too surprised because the key schedule had seemed like one of the easier attack vectors from as far back as the original AES competition. If you consider the AES algorithm as a whole, the key schedule is an easier component to craft attacks against, making it a weak point of the algorithm.

However, "weak keys" as a phrase has a specific meaning. It refers to keys that, for their respective algorithms, provide abnormally poor encryption properties relative to the other keys. For example a DES key of all 0s or all 1s is considered weak. AES does not have any such weak keys, all keys are expected to perform equally securely.