Public key cryptography - public key encrypts and cannot decrypt?

How it works depends on the cipher, but the basic idea is that of a trapdoor function.

  A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

Many number theoretic problems have been used in the past successfully to build such functions, and the wikipedia article is fairly good.

Let's take one as an example, lets say the problem of factoring a number into it's prime factors. Every number can be uniquely broken up into a product of primes. It turns out though, that breaking a number up into its prime factors is difficult if the number is large enough and the factors are large enough, but give me a few large prime numbers and I can easily compute the composite that those numbers make up.

So, how can this be leveraged with cryptography? I choose say two large prime numbers called $p,q$ and set $n=p\cdot q$. I then set $e=65567$ and give you $e,n$. I then use my extra information ($p,q$) to compute $d$ such that $ed\equiv 1\pmod{\phi(n)}$. This can only be efficiently computed if you know $p$ and $q$.

You have $e,n$, so to send me a message $m$ you compute $c=m^e\bmod{n}$ and send $c$ to me. For me to get $m$ back, I must know $d$, I can only know $d$ if I know $p,q$ and you knowing only $n$ and $e$ cannot compute $d$.

To get $m$ back I compute $c^d\equiv (m^e)^d \equiv m^{ed} \equiv m^1 \equiv m\pmod{n}$, so I have successfully used my extra information to recover $m$, something you cannot do without the extra information.

The public key can encrypt (it is the forward direction of the "one-way function"), but cannot decrypt because it does not know the trapdoor information to go in the reverse direction.

The cipher described here is RSA. There are others, but RSA is pretty simplistic.


There is no need to do that manually. A TLS tunnel is not only encrypting the data, it is also guaranteeing the authenticity (and thus integrity) of the data it transmits. This used to be done by a seperate MAC (HMAC, usually), but these days (TLS $\geq 1.2$ and with modern cipher suites) you rather use an AEAD mode for encryption like AES-GCM or ChaCha20-Poly1305.


Is this password migration strategy secure?

The overall idea is a sound migration strategy. The nice thing is that security for all users is upgraded in a one-shot operation, rather than at the hypothetic next login of each user. Of course, original salt and new_secure_salt shall be stored, or perhaps for some portion derivable exactly from material keyed-in by the user, e.g. user name lowercased.

Using bcrypt(MD5(salt + password), new_secure_salt) is a huge improvement over MD5(salt + password): the risk of password cracking for a given password entropy is greatly increased by the many iterations (and some use of memory) in bcrypt. Using MD5(salt + password) rather than password discard negligibly little password entropy for typical passwords (who chooses 20 random characters among 68 as password?)

However I would recommend scrypt over bcrypt. Scrypt uses the memory available during legitimate use of the password in order to further increase security; have a look at this table from the paper defining scrypt:

The single weakness I can think of relates to MD5 collisions on salt. If it was possible for an adversary to choose salt and get the resulting authentication token with the same new_secure_salt a few times, it would become possible to recover the first few characters of the password, following the line of thought in Gaëtan Leurent's Practical key-recovery attack against APOP, an MD5 based challenge-response authentication (in  IJACT, 2008).
That's likely mostly theoretical in the context, where salt turns out to be non-malleable. To rule out any possibility of that attack, it would be enough that salt be included in new_secure_salt.

The above theoretical attack exploits that it is feasible to find two 63-byte 127-byte salt0 and salt1 such that MD5(salt0 + 'e') = MD5(salt1 + 'e') with collision in the first two 64-byte MD5 blocks. Now assume we could get the authentication tokens for these salt0 and salt1; if the password starts with e, then these tokens match! And the converse is true with near certainty. This allows to construct a test for the first character of the password, and recover it in a moderate number of queries, then proceed with the second, and perhaps third character; after that, finding the collisions seem to become quite difficult.


When is factoring semi-primes thought to be hard?

There are many different special-case factoring algorithms for when $(p,q)$ have some special structure.
  Which of these attacks on semi-primes with special structure are devastating enough such that proper generation of $(p,q)$ should explicitly check that they don't have that structure?

TLDR: None in modern practice. Except when there's a regulatory requirement for such explicit precautions.

There is now a large consensus that for semi-primes of cryptographic interest (say at least 512 or is it 1024 bits), we need to consider no special-case factoring algorithm when we care about the expected cost of factoring (using classical computers/hardware) one particular semi-prime generated per a process where both factors $p$ and $q$ are primes each picked independently and roughly uniformly at random in the same interval $[a,b]$, when $a>b^{0.9}$ and $a<0.99\,b$. A common choice is $a=2^{(n-1)/2}$ and $b=2^{n/2}$, which is guaranteed to give an exactly $n$-bit semi-prime.

There's a lot of headroom in both fudge factors $0.9$ and $0.99$, which are out of my head. The condition  $a>b^{0.9}$ ensures that the bit size of $p$ and $q$ is never too far apart, which optimizes resistance to ECM. $a<0.99\,b$ ensures that the interval is not overly restricted.

It is often added further range restrictions, and that's OK especially for large $n$. For example it can be added that $p$ and $q$ are $n/2$-bit primes with their respective top 4 bits set to 1110 and 1100, which gives absolute (rather than statistical) certainty that FIPS 186-4's requirement $\lvert p-q\rvert\;>\;2^{n/2-100}$ and required ranges are met for endorsed $n$, and complies to ETSI TS 102 176-1's suggestion $0.1<\lvert\log_2p-\log_2q\rvert<30$.
Note: The fudge factor 0.1 in ETSI's suggestion used to be 0.5, which was incompatible with FIPS 186. The whole suggestion seems obsolete.

The same selection rules is usually fine when we care about small (but still palatable) residual odds that the semi-prime is factored for a given effort. This is a significantly different metric though, and it can matter. E.g., it might be considered unacceptable that an adversary has 0.1% chance to succeed with \$1M cost in electricity, even though certain success for \$500M is acceptable. ECM's probability of success grows linearly with the computational effort, when that of GNFS remains essentially at zero until the necessary effort is spent. GNFS might thus be less a concern when considering residual odds.

The argument for the above choice of interval $[a,b]$ is that at the size $n$ considered, all known factorization algorithms worth consideration have their expected cost larger (and their residual odds of success for limited work lower) than GNFS or ECM:

we know how to improve resistance to ECM, and did that by random choice in an interval $[a,b]$ with $a>b^{0.9}$
we don't know how to improve resistance to GNFS for a given size $n$, other than by avoiding semi-primes amenable to SNFS, which is kept to negligible probability thanks to random choice in an interval with $a<0.99\,b$
MPQS, variations (PPMPQS, PPSIQS..) and ancestors (QS, CFRAC..), as well a the rational sieve, require more work than GNFS, and the gap increases when $n$ grows
Pollard's p−1 and William's p+1 have larger expected work than ECM for sizable fixed probability of success, given the order of magnitude of the factors and the fact they are randomly seeded.
Note: that does not quite hold for extremely small probability of success (more on that later).
Pollard's rho is outclassed by ECM on all counts, given the order of magnitude of the factors.
Whatever improvement of Fermat's method or trial division requires knowledge of the order of magnitude of one of the factor, and random choice in an interval $[a,b]$ with $a<0.99\,b$ give a wide margin against that.

Things are more muddy when we care about factoring $k$ semi-primes of size $n$, for large $k$ and $n$ not too large, especially any one among those semi-primes (rather than all). The later consideration matters to a system designer who wants assurance that no semi-prime among $k$ used will be factored (perhaps because there is no way to detect rogue use of a factored semi-prime, or no revocation list, which is common in Smart Card applications; or just because the excuse "that's only for one in 100 million devices issued" would be untenable from a public relations perspective, even if it makes perfect sense economically).

This "batch factorization" problem is much less studied, especially in the "any one among" variant. Daniel J. Bernstein and Tanja Lange's Batch NFS, in proceedings of SAC 2014, conclude that increasing $k$ allows asymptotic savings on the expected cost per factorization. However, that does not require a different method of choosing $p$ and $q$; and it tells nothing useful about the "any one among" variant.

We can't state with confidence that increasing $k$ leaves the expected effort for factoring any one among $k$ semi-primes unchanged, even if we additionally discount attacks with an overall negligible probability of success (which makes sense). We even have a hint of the contrary: when $k$ increases, the expected effort using Pollard's p-1 lowers; and there's a threshold when it beats ECM with random curves, which expected effort is independent of $k$.
Pollard's p-1 can be viewed as ECM on a special curve amenable to lots of optimizations. In practice, the strategy maximizing probability to factor a semi-prime (with randomly selected factors of about equal size) using the popular GMP-ECM program and some maximum amount of CPU time involves spending some sizable fraction of the effort with its built-in Pollard's p-1. The lower the CPU allowance (and the probability of success), the larger that fraction is. When we switch to factoring any one among $k$ such semi-primes for the same maximum amount of CPU time, the optimal proportion spent on Pollard's p-1 grows markedly with $k$. That's because we can afford to use less random curves. At some point ECM on general curves is not used at all.

In order to reach a situation where Pollard's p-1 is worth considerations, we would need to

somewhat discount NFS and QS algorithms so that ECM and friend are back into competition (perhaps because moduli have more than two factors as in multi-prime RSA, or/and one of the factor is small as in unbalanced RSA, or we are trying to lower residual odds of success for adversaries that will not manage to reach the work threshold or RAM requirement necessary for NFS),
and consider that an adversary is content factoring any one among many moduli.

Under such hypothesis, adding precautions in the generation of the semi-primes that block Pollard's p-1 could be beneficial to some degree (I wish I could make that quantitative). The same applies, to a lesser degree, for William's p+1. This may be why such precautions remain mandated by FIPS 186-4 section B.3 for 1024-bit semi-primes.

Notice that for Pollard's p−1 and William's p+1, such precautions are not implemented as checks (that would be too computationally intensive), but rather are built into the method by which the prime factors are derived.


It does, but it's practically impossible to evaluate how much: just a tiny little bit, or enough for security?
A PC is an extremely complex thing, and it's practically impossible to know its exact state at a precise moment in time, even having observed its external behavior (user actions, network packets…) very precisely. Even knowing the exact state of the CPU alone is very difficult: it's very difficult to build a cycle-accurate simulator for the CPU of a modern PC or smartphone, much more difficult than building a simulator that implements all the operations but not their precise timing. Furthermore such complex chips have multiple clocks, and there is some unavoidable manufacturing imprecision that causes a drift between those clocks (CPU jitter), which is the basis of HAVEGE.
The problem with relying solely on the entropy from jitter (within the CPU and between peripherals) is that it's unreliable. Depending on the system configuration, on how much activity there is, on the ambient temperature, there may be more or less jitter. The entropy from user input is unreliable because the user may be somewhat predictable and may be observable. The entropy from network input is suspect because an adversary may be able to obtain it (e.g. if they control your Internet access because you're in a cybercafé or because they breached your router's 5-year old unpatched firmware).
All of these methods have the problem that shortly after boot, no or little entropy has had time to accumulate; a way to counter this is to save entropy from past runs in a file, and load that at boot time. This way, there may be a lack of entropy during the system installation, but as soon as the system has accumulated enough entropy for security, it keeps that entropy forever.
Operating systems like Linux and Windows mix all the entropy sources inside the kernel and expose it through system calls or similar methods (modern interfaces: getrandom(), BCryptGenRandom(); deprecated interfaces: /dev/urandom, CryptGenRandom()). The entropy you get from those system interfaces is more reliable than anything you could cobble up on your own, and is at least as trustworthy since it's coming from the operating system kernel which you have to trust anyway.
Fortunately modern systems, at least in the PC/smartphone range, have a built-in hardware random generator that is actually designed to produce entropy. The system mixes in all the entropy from various sources, which (barring bugs in the entropy mixing) gives you entropy that's at least as strong as the strongest source. While sources such as user activity and disk jitter are mixed in, it doesn't matter if they don't provide enough entropy, since the hardware RNG is sufficient on its own.


Demonstrating the insecurity of an RSA signature encoding scheme

An RSA signature scheme with public key $(n,e)$, private exponent $d$, and encoding function $enc$ (including but not limited to the question's $enc$), signs message $m$ as $$Sign(m) = enc(m)^d\bmod n$$

Such scheme is insecure if an adversary can figure out $k>0$ distinct messages $m_i$, and integers $u_i$, $r$, $s$ verifying
$$s^e \cdot enc(m_0) \cdot \prod_{0\lt i\lt k} enc(m_i)^{u_i} \equiv r^e \pmod n$$
because this implies (by raising to the power $d$)
$$ Sign(m_0) \equiv r \cdot s^{-1} \cdot\prod_{0\lt i\lt k}Sign(m_i)^{-u_i} \pmod n$$
which allows computing the signature of $m_0$ (if $k\gt 1$, it is also necessary that the attacker obtain the signatures of the other messages $m_i$; that becomes an existential forgery, or chosen-message attack). Although dated, Jean-Francois Misarsky's How (Not) to Design RSA Signature Schemes is an interesting and relatively easy reading on that topic.

In fact, every known attack on an RSA signature scheme is either of the above kind (with more or less involved computations to exhibit $m_i$, $u_i$, $r$, $s$); or amounts to factorization of $n$ (which includes anything recovering $d$, perhaps by side-channel attack); or is some implementation error, perhaps widespread.

In order to mount an attack of the above kind, a relation of the form $enc(m_0)=r^e$ is ideal. It gives the signature of $m_0$ without any consideration on $n$ or known signature. When $e$ is low enough, this can be done with the encoding $enc$ in the question, by considering $r=2^t$ for some appropriate $t$. That's because by definition (and assimilating bit strings to integers using big-endian convention), $enc(m)=m\cdot2^{L/10}$ with $L/10$ an integer; hence $enc(m_0)=r^e$ with $r=2^t$ holds if and only if $m_0$ has a single bit set and $\log_2(m_0)+L/10=e\cdot t$; for all $m$ that $enc$ aims at handling, $\log_2(m)<9L/10$, hence $enc(m_0)=r^e$ can hold only if $e\cdot t<L$; there are no solutions for $e\ge L$, and about $9L\over10e$ solutions for small $e$; the lower $e$, the more solutions. When we extend that with $r=v\cdot2^t$ for odd $v$, the trend for more solutions for low $e$ remains, with no solution when $e\ge L$.

Similarly, $enc(m_0) = r^e\cdot enc(m_1)$ gives the signature of one message from the signature of the other, without any consideration on $n$. This can be done with the encoding $enc$ in the question, for a wider choice of $e$.

Similarly, $enc(m_0) \cdot enc(m_1) = enc(m_2) \cdot enc(m_3)$ gives the signature of one message from the signature of the other three, for any public key $(n,e)$. With the encoding $enc$ in the question, there is ample choice (the equation simplifies to $m_0\cdot m_1=m_2\cdot m_3$, and all messages which left bit is 0 or which integer representation is composite are vulnerable). The ISO/IEC 9796:1991 signature encoding scheme (section 11.3.5 of the Handbook of Applied Cryptography), now withdrawn, turned out to be vulnerable to that, of course if the adversary can obtain the signature of three chosen messages, and is content with the signature of the fourth.

Even the hash-based ISO/IEC 9796-2:1997 (now known as ISO/IEC 9796-2:2010 scheme 1), still in wide use, is vulnerable if the adversary can obtain the signature of many weird chosen messages and is content with the signature of another, which fortunately is seldom the case in practice.

Some require $e>2^{16}$ (FIPS 186-3 appendix B3.1, RGS Annex B1 section 2.2.1.1, and I have seen suggestions for much wider random $e$), because some attacks on weak encoding schemes or implementations of RSA signature/encryption have been easiest for $e=3$ or other small $e$, as is the case for the scheme in the question. I will not condone a course of action that will lead us to loose the main appeal of RSA (or Rabin) signature schemes: fast and simple verification with modest hardware.


Epsilon Perfect Secrecy: Size of Key Space

Choose a uniform distribution over the message space $M$. Suppose we observe a ciphertext $c$. Let $M_c = \{ m | \exists k. dec_k(c) = m \}$ be a set of all messages that could have been encrypted to $c$.
Choose a message $m \in M_c$ for which $\Pr[m|c] \geq \frac{1}{|K|}$ (such message exists, because the set $M_c$ has at most $|K|$ elements). Without knowing $c$, the probability of $m$ being chosen is $\Pr[m] = \frac{1}{|M|}$. Thus, we conclude that $\frac{1}{|K|} \leq \Pr[m|c] \leq (1+\epsilon)\Pr[m] = (1+\epsilon)\frac{1}{|M|}$, from which your desired inequality follows.


In order to have a successful fault attack on RSA-CRT, you need to work with known values of $e, N$ and of the message $m$, but you should be knowing them already, since you cannot verify the signature without knowing these values.

So, at first you should be knowing the public key of the signer: $(e,N)$. Then the signer signs a message $m$, which you should know in order to verify it. But if the signer instead issues a faulty signature, you can try and recover its private key as you said using the following method.

You can first recover the value $p$ as you mentioned using
 $$p = \operatorname{gcd}(\text{faultySignature}^{e} - m, N)$$
once this is done, you can get the second prime $q$ by dividing $N$ by $p$:
$$q=\frac{N}{p}$$
and you can finally compute the value $d$ by computing $\phi(N)=(p-1)(q-1)$ (assuming we are working with a 2 prime factors RSA modulus) and by finally computing $$d=e^{-1}\mod{\phi(N)}$$

Now, when using RSASSA-PKCS1-v1_5, what you are signing is not directly the message, to avoid the malleability issues and such, but instead the padded hash thereof. You can see the exact process of deriving the signed hash from the message in RFC3447 section 8.2.1 and following. But basically, what you need to do is to:

Convert the message M into its encoded form of length k octets EM = EMSA-PKCS1-V1_5-ENCODE (M, k).
Convert the encoded message EM to an integer which can be used with RSA: m = OS2IP (EM)
Use this integer value m as being your value $m$ in your computations.


For Diffie-Hellman, must g be a generator?

First, we are talking about multiplications, so we work in $\mathbb{Z}_p^*$, not $\mathbb{Z}_p$.

By definition, any integer $g \in \mathbb{Z}_p^*$ is the generator for... the subgroup generated by $g$, i.e. the set of $g^k \mod p$ for all integer values $k$. The order of $g$ is the smallest $k \geq 1$ such that $g^k = 1 \mod p$.

For soundness (Alice and Bob end up with the same shared key), any $g$ will do.

For security, we need the order of $g$ to be a multiple of a large enough prime value, usually denoted $q$. It is not necessary that $g$ generates the whole of $\mathbb{Z}_p^*$. It is not necessary that the order of $g$ is exactly $q$.

If the targeted security level for Diffie-Hellman is "$t$ bits" (i.e. the system will resist attacks up to at least computational effort $2^t$), then $p$ must be big enough (see this site for estimates, but, roughly speaking, you need a 1024-bit integer for $t = 80$) and the size of $q$ must be at least $2t$ bits. Also, the DH private keys ($a$ and $b$) must be randomly and uniformly generated integers of size at least $2t$ bits. It is not necessary that $a$ and $b$ are generated uniformly among integers modulo $q$, only that they are generated among a large enough range (this differs from DSA, in which we need a random $k$ which MUST be generated uniformly in the $[1, q-1]$ range).


Do you need both client and server side support for TLS 1.3 record padding?

When you enable record padding for a client, does a server need a specific option to support this?

It shouldn't; record padding is a part of the RFC which is not listed as optional; I don't see anyone could claim to support TLS 1.3 without understanding record padding on decryption.


First, download OpenSSL for Windows from a reputable source. Here is a good place to start: https://wiki.openssl.org/index.php/Binaries

After installing OpenSSL, open a command prompt. You can chose among the many algorithms, but if you dont know what you want, going with AES-256 in CBC mode is a good start.

C:\Users\admin>openssl aes-256-cbc -a -salt -in file.txt -out encrypted-file.txt.enc
enter aes-256-cbc encryption password:
Verifying - enter aes-256-cbc encryption password:

C:\Users\admin>type encrypted-file.txt.enc
U2FsdGVkX19v2JTUzRF/BRwy7egsmi+4A1KXyJfQmBF70cg0Go+EvroxvXd8ugiI

C:\Users\admin>openssl aes-256-cbc -d -a -in encrypted-file.txt.enc -out decrypted-file.txt
enter aes-256-cbc decryption password:

Here is a screenshot of what it looks like on Windows 10. Note, you can't see the password being typed, but you will have to type a password to encrypt the file, and the same to decrypt it.

I hope this helps you get started.


What is the order of the Identity point on prime order elliptic curve groups?

For something to be a group, it must have an identity. This is a definition.
The order of an element, $g$, in a group is defined to be the smallest positive number $n$ such that $g^n = 1$, where $1$ is the identity of the group.
By this definition, the order of the identity in any group is $1$.


Why do we need extra hashing if we could use simpler scheme?

This scheme is totally insecure. If an attacker modifies any part of the ciphertext except the last block before the ciphertext corresponding to H, your scheme won't catch it.

CBC decryption of a block only depends on the ciphertext of the previous and current block.

(Based on Cbc decryption.png from Wikipedia)

The red parts are left totally unprotected by your MAC scheme. The green parts affect your MAC, but even on them there are some attacks.


Proving impossibility for a stronger primitive

This seems like a logic question: $B$ implies $A$, therefore not $A$ implies not $B$

Proving $B$ would prove $A$, so if it is impossible to prove $A$ it must be impossible to prove $B$ in the same setup.

Alternatively lets assume $B$ is proven, since $B$ implies $A$, $A$ is proven. Yet $A$ is unproveable: a contradiction.


If I understood the description correctly, with a 4-block (512-bit) hash output $H_0\ldots H_3$, message $M_0\ldots M_3$ of the same size, a fixed public value of the AES key, and all-zero IVs and initializations (because comments allow that), the steps are

$C_0\gets E(M_0)$
$C_1\gets E(M_1\oplus C_0)$
$C_2\gets E(M_2\oplus C_1)$
$C_3\gets E(M_3\oplus C_2)$
$C'_0\gets E(C_0\oplus C_3)$
$C'_1\gets E(C_1\oplus C'_0)$
$C'_2\gets E(C_2\oplus C'_1)$
$C'_3\gets E(C_3\oplus C'_2)$
$H_0\gets C_0\oplus C'_0$
$H_1\gets C_1\oplus C'_1$
$H_2\gets C_2\oplus C'_2$
$H_3\gets C_3\oplus C'_3$

I have noted AES block encryption and decryption with the key $X\mapsto Y=E(X)$, and $Y\mapsto X=D(Y)$.

I'll show that knowing $H_0$, $M_0$, $M_1$, $M_3$, we can find $M_2$, which counts as a break of a model of the hash as a Random Oracle, and is tantamount to a first-preimage attack.

$C_0\gets E(M_0)$, per 1.
$C_1\gets E(M_1\oplus C_0)$, per 2.
$C'_0\gets C_0\oplus H_0$, by inverting 9.
$C_3\gets D(C'_0)\oplus C_0$, by inverting 5.
$C_2\gets D(C_3)\oplus M_3$, by inverting 4.
$M_2\gets D(C_2)\oplus C_1$, by inverting 3.

$H_1\ldots H_3$ can be recomputed trivially since we have $M_0\ldots M_3$.

That hash truncated to its first 256-bits is insecure against collision. That's contrary to a good 512-bit hash like SHA-512, which we can truncate to 256-bit and still get collision-resistance with work for the best known attack about $2^{128}$ compression functions. Sketch of that partial collision: we start from an arbitrary message, change $M_2$, then $M_3$ so that $C_3$ is restored to what it was. These message changes leave $C_0$, $C_1$, $C'_0$, $C'_1$ unchanged, therefore $H_0$ and $H_1$ unchanged.

That attack can be extended to work with the padding and hash size described in comment, to obtain a collision in the first 3712 bits of a 4096-bit hash. Sketch: message and hash are 32-block, we alter $M_{29}$, and $M_{30}$ to return $C_{30}$ to what it was. That leave $H_0\ldots H_{28}$ unchanged.

What's the point of making a wide hash, if most of it is insecure against collision?

Another issue with the construction is that it requires memory size about as the message size in order to keep the result of the first pass. Something requiring about as much memory as the hash size is desirable in many applications.

Making the message a few times the hash size gives more freedom, and I'll walk back from speculating what it might allow.


Distributed key generation + signature scheme?

If I understand you correctly, you want a system designed such that

A group of $n+1$ people -- Alice, Bob, Eve, Trent, and James -- each have their own private key, and each one knows who is in the group and all of the corresponding public keys of everyone in the group.
Alice can sign a message and package the message and the signature, and then transmit the packaged message publicly in such a way that:
Any one person in the group, such as Eve -- using only the information in the packaged message itself and her own list of people in the group and their corresponding public keys -- does not have enough information to figure out who the message came from, without the cooperation of anyone else in the group
If people in the group cooperate -- all $n$ people cooperate, or some specific threshold of people $1<t \leq n$ -- they can verify that the packaged message was signed with Alice's private key.

Off the top of my head (warning: untested protocol), perhaps something like this would fulfil those requirements:

Alice takes the original plaintext message, and signs it with her private key to generate a detached signature file.
Alice uses any secret splitting technique to divide a signing message -- something like "My name is Alice, and I sign Manifesto X thus:" concatenated to the detached signature file -- into $n+1$ share files.
Alice uses each one of the $n+1$ public keys in her list of group members to encrypt one of the share files.
Alice packages up all $n+1$ encrypted share files and (optionally) tags each encrypted file with the name of someone in the group and (optionally) the original plaintext message file, in one big packaged message.
Alice securely erases the detached signature file and the (unencrypted) share files, and then broadcasts the packaged message.
Eve attempts to decrypt all the share files in the packaged message, but her private key is only able to decrypt one of them (the one tagged "Eve"). Also, the decrypted contents of that file are a share file, which alone is not enough to recover any information about the signing message.
If enough people in the group cooperate, they can combine (decrypted) share files to reveal the signing message.
Once a person has the original plaintext message and the signing message and Alice's public key, that person can extract the detached signature and use it to verify that Alice's private key was used to sign that message. (If the signing message includes only the detached signature file, without any additional identification, then repeat this step with every public key of everyone in the group to find one that verifies).

I suspect there may be a group signature scheme or ring signature that may be a better solution than the above untested protocol.


Parameter $f(x)$ in binary ECDH exchange protocol

This Wikipedia article is simply not complete. They refer to the NIST Special Publication 800-56A (http://csrc.nist.gov/publications/nistpubs/800-56A/SP800-56A_Revision1_Mar08-2007.pdf), which is now replaced by a new version (http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf).

It seems the Wikipedia article refers to the domain parameters as indicated on page 41 for ECC CDH, of the form $\left(q,FR,a,b,G,n,h\right)$. The explanation of $FR$ is stated on page 10 of the same document:

"Field Representation indicator (an ECC domain parameter); an indication of the basis used for representing field elements. FR is NULL if the field has odd prime order or if a Gaussian normal basis is used. If a polynomial basis representation is used for a field of order $2^m$, then FR indicates the reduction polynomial (a trinomial or a pentanomial)."

As SEJPM commented, this is the polynomial which defines the field $GF(q)$. Note that up to isomorphism there is only one field $GF(q)$, but there are many ways to represent it (by choosing different $FR$). Hence it is important to specify which $FR$ was chosen for compatibility.


Notice that the result says 67 mod 257.
All calculations here are being done modulo 257. So, $101^{-1}$ is actually the modular inverse of $101 \bmod 257$, which is 28. Similarly, $85 \cdot 28$ is also done modulo 257.


Key exchange protocols non-reducible to groups

Is there an intrinsic reason, why most key exchange protocols use
  group-based approaches apart from it being a well-studied area?

No. It just so happens that

Diffie-Hellman was first and heavily used multiplication modulo a prime, which was later generalized to groups. So groups are important for historic reasons.
Groups are easy to understand and "even the average software developer" can probably get a grasp of why this is secure somewhat quickly.
We know efficient ways to create groups which yield fast, small and secure key exchanges, so they are a natural choice.

Beyond that you can build a secure key exchange from any encryption scheme, including e.g. McEliece (by simply encryptingt the shared secret and sending it over).

  Given a key exchange protocol does there always need to be some group
  or a particular algebraic structure involved?

In some sense yes. You can't avoid fields / groups because computer arithmetic fundamentally is working with these, so if you want to actually compute / execute the protcol you'll at some point involve fields and groups.

On a higher level, to agree on a secret over a public channel we need some structure that allows us to publicly show values and blocks passive adversaries from learning the corresponding secrets. Chances are you can always find a relevant mathematical concept / basic idea out of any key exchange. Additionally sometimes these protocols start from things we know how to quickly compute as honest users but know to be hard to break from other fields, so why make an effort to come up with something new (that may be broken in a few days - years) when you can build on a large amount of existing research?

  What about key-exchange with a requirement for perfect forward
  secrecy?

Just about any protocol can be modified / extended to provide forward secrecy, so there's nothing special about this property and groups. It just so happens that with groups the property can be achieved somewhat cheaply.

  What would be the least constrained algebraic structure involved for a secure key exchange?

On an abstract level probably the semi-group which is usually enough for the "group-based" key exchanges we are using, because these don't actually make use of the ability to invert every element nor do they make use of the availability of a neutral element.

Note though that not every semi-group (eg the natural numbers with addition) actually provide cryptographic security. If you are looking for examples of secure semi-group based key exchange look no further than standard ECDH and DH, which use $(E(\mathbb F_p),+_{\text{EC}})$ and $(\mathbb F_p^*,\cdot)$ as their semigroups.

  If not can you give some examples of perfect forward secure key
  exchange protocols not involving group operations?

See above on avoiding groups and using McEliece. You get forward secrecy by throwing the encryption scheme's private / public key away after each key exchange.


What is the difference between a Stream cipher and a Symmetric Encryption algorithm?

There are multiple ways to do symmetric encryption. The two most popular ones are block ciphers and stream ciphers. So stream ciphers are a subset of symmetric ciphers.

AES and 3DES are block ciphers, not stream ciphers. But if you use them (or any other block cipher) in CTR mode, you can create a stream cipher out of them.

ChaCha20 is a stream cipher, Poly1305 is a MAC (message authentication code) algorithm. Together, ChaCha20-Poly1305 form an authenticated encryption scheme.


The question as stated has some serious issues:

The alternating step generator works with 3 LFSRs. If the output of R1 is 1, then R3 is clocked, otherwise R2 is clocked, so at each clock period exactly one of those two is clocked. The output of R2 and R3 is added modulo 2 to form the keystream. The initial loadings of the 3 LFSRs is essentially the key.

The example in the question is quite strange. The LFSRs should be maximum length (i.e., primitive). You can have a primmitive LFSR of cycle length 7, e.g., and instead nonprimitive LFSR with cycle lengths 5 and 6 are used--this would have statistical properties worse than a primitive LFSR and lead to problems.

Even ignoring this, the nonstandard notation $<4, 1+D, D^3>$ is used for R1. I have no idea what this means.

In particular, in the figure from part (b), a constant bit of $0$ is AND'ed to one of the registers which might as well be removed, since the output is always zero! Thus, the LFSR is defective in that it is only sampling two bits, and not at the two ends.


PBKDF security if all but one keys are exposed

In case 3, one must consider that the knowledge of $salt_2$ and $k_2$ (or/and other ones) allows to test a guess of $pwd$ with about $c$ evaluations of $H$. The "brute force" attack becomes doing this with a dictionary of passwords with the most common first. Password crackers using GPUs or ASICs reach astonishingly high hash rates, and for $c$ in the thousands, if a password is memorable, it is best to consider that it is not safe form a well-funded attacker. That's why state of the art is memory-intensive password hashes, e.g. Scrypt, Argon2, Balloon, which make a large difference.

In a multi-target attack (where several $pwd$ each with their associated $salt_2$ and $k_2$ can be attacked, and finding any is a success for the attacker), the attacker should try the most likely $pwd$s on all available instances of the problem s/he's trying to attack before moving to less likely ones. Practical chances of success grow very fast with the number of different users having chosen $pwd$ !

I'm unaware of another weakness of PBKDF1 / $H^{(c)}(pwd\mathbin\|salt)$ that would be exploitable in the situation, and leak any info about $k_1$ without a successful guess of the full $pwd$ (if we leave a aside implementation issues like side-channels).

Note: in theory, the many iterated hashes of PBKDF1 reduce the possible values for the outcome as $c$ increases (see this). A wild guess of $k_1$ with a sizably better than random chance to match is plausible. However, for any hash at least as wide and remotely secure in the ROM as SHA-1, the probability of success remains so low that this is never a practical issue; and truncating the final result of PBKDF1 (which dramatically increases the probability of success of a wild guess) reduces to almost nothing the advantage that could be obtained by exploiting said effect of many iterations.

PBKDF1 successor's PBKDF2 fixes the above theoretical weakness, and allows producing large output, which can come handy. Neither comes with a security argument that it is a strong PRF (as HMAC does). However the main reason to discourage using PBKDF1 or PBKDF2 is that they are among what gives the least resistance to brute-force password crackers for a given level of effort by the legitimate user (number of iterations $c$).


Mapping between subgroups and the integers

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$:

Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$.
If $x$ is a non-zero quadratic residue ($x = y^2 \mod p$ for some value $y$) then $x^q = y^{2q} = y^{p-1} = 1 \mod p$. Thus, every non-zero quadratic residue is a $q$-th root of $1$, therefore an element of $\mathbb{G}_q$.
Since $q$ is a big prime, it is odd, therefore $p = 3 \mod 4$. This implies that if $x$ is a quadratic residue, then $-x$ is not, and vice versa. Thus, there are $(p-1)/2 = q$ non-zero quadratic residues.

This yields the following mapping:

If $x \in \mathbb{G}_q$ then it is a square and has two square roots, $y$ and $-y$ for a value $y$. Computing the square root modulo $p$ is easy: $y = x^{(p+1)/4} \mod p$. $y$ can be viewed as an integer between $1$ and $p-1$. Set $z = y - 1$ if $y \leq q$, or $z = p - y - 1$ otherwise. This always yields a value such that $0 \leq z \lt q$, i.e. a value in $\mathbb{Z}_q$.
For the inverse mapping, just compute $(z+1)^2 \mod p$.


If $H$ is secure in the random oracle model and of width at least $n$, then $x\mapsto P(H(x),n)$ is also secure, inasmuch as an $n$-bit hash can be (proof sketch: any attack that distinguishes $x\mapsto P(H(x),n)$ from a random oracle is trivially turned into a distinguisher for $H$). The converse is not true.

Finding a collision requires $O(2^{n/2})$ queries to the oracle (or evaluations of the inner function of $H$). More precisely it is expected to require $o(\sqrt{\pi/2}\cdot2^{n/2})$ distinct queries, and odds of success reach 50% after $o(\sqrt{\ln 4}\cdot2^{n/2})$ such queries (that's the generalized birthday problem). The standard paper on how to exhibit such collisions is Parallel Collision Search with Cryptanalytic Applications.

Finding a preimage is expected to require about $2^n$ queries to the oracle (I plan to dig out the right formulas someday). It is possible to speed-up an attack by pre-computation, e.g. with rainbow tables, in particular if the set of possible messages is known, or if $n$ is small enough.

Now we restrict to MD5, thus $n\le 128$.

The difficulty of finding collisions is about as for a good hash ($\approx 1.3\cdot2^{n/2}$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function (e.g. random messages or words from a dictionary). Without constraints on the message, finding collisions among messages of at least 1024-bit has been possible for any $n$ since that breakthrough, works even with some constraints, now has little cost, and was recently made possible with 512-bit messages. The lower $n$ is, the easier it gets. AFAIK there is no shortcut for heavily constrained messages, e.g. passwords of less than 10 ASCII characters.

The difficulty of finding a preimage is about as for a good hash (about $2^n$ MD5 inner rounds) when the messages are tried without consideration of the inner structure of the MD5 round function, nor knowledge on the origin of the target value. I am not aware of a practical method better than that, except when the message is in a known set smaller than $2^n$, which is when rainbow tables shine; in that case, I do not see that lowering $n$ changes the cost.


A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$.  Another key of looking at it is that if we consider the sequence $g,\ \  g \cdot g,\ \  g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence.

Now, when it comes to Diffie-Hellman, generator is used in two slightly different meanings (and that may be what is confusing you).

In the first meaning, a "generator" is defined to be an element that generates the entire group.  That is, when we talk about DH (and thus the group $\mathbb{Z}_p^*$), we say that $g$ generates the entire group means $g^k \bmod p$ can take on any value between 1 and $p-1$.

In the second meaning, we say that an element $g$ "generates" a subgroup.  That is, when we consider all the possible values $g^k \bmod p$, those possible values also form a group (which may be $\mathbb{Z}_p^*$, and may be a strictly smaller group), and it makes sense to consider the Diffie-Hellman operation over this subgroup.  In this case, we may call $g$ the "generator" (even if it doesn't generate the full group).  Now, this doesn't denote anything special about $g$ (because all elements generate some subgroup by this meaning), instead we call $g$ the generator to denote that it's the element we have chosen to use.

As I pointed out in my answer to the cited question, using a "generator" for the entire group is often not wise; it often makes more sense to deliberately use an element that generates a prime-sized subgroup.

As to whether $g$ itself is prime or not, well, that's actually not very relevant.  After all, $g$ is actually a member of $\mathbb{Z}_p^*$; whether it corresponds to a prime when it is mapped into $\mathbb{Z}$ using the obvious mapping is not that important.


Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing?

You can do it with two machines. https://www.iacr.org/archive/crypto2001/21390136.pdf (this paper is for DSA; it's easy to adapt for ECDSA).

Here's an open-source JavaScript implementation of two-party ECDSA signing, using Bitcoin parameters: http://www.jpaulgossip.com/demo/split-key.html

Unfortunately the protocol requires at least three rounds of interactive communication so it is probably not suitable for what you call progressive signing.

I believe splitting a key among more than two machines remains an open problem. ECDSA is not well suited for split signatures. I assume your application is something like Bitcoin which requires ECDSA. If only Bitcoin had used BLS signatures, then it would be easy to implement multiparty signing.

Update (4/5/15): A group of researchers at Princeton have solved the problem of multiparty (more than two parties) Bitcoin signatures: https://freedom-to-tinker.com/blog/stevenag/threshold-signatures-for-bitcoin-wallets-are-finally-here/


The term for the parameter to AES-GCM that must be unique from message to message for any single key is sometimes called ‘nonce’ and sometimes called ‘IV’.

The security contract for AES-GCM requires that only that this never be repeated, and so it is appropriate to call it a nonce, meaning number used once.
In contrast, for, e.g., AES-CBC, there is a parameter for a 128-bit string that must be unpredictable in advance to an adversary, and which is usually called an initialization vector.

That's the distinction that PyCryptodome is getting at when it distinguishes the ‘nonce’ and the ‘IV’—although it says ‘IV’ for AES-CFB and AES-OFB too when really they just take a nonce.  However, in some other APIs, the corresponding parameter is always just called IV.  To be confident, you should draft some code using two different libraries—like one of the C++ libraries you have in mind—and make sure they can interoperate, and include known-answer tests with fixed keys, nonces, and messages, as test cases in your code.

Caveat: AES-GCM is best with a 96-bit (12-byte) nonce chosen sequentially as a message sequence number.  If you use a 128-bit (16-byte) nonce—as the PyCryptodome documentation wrongly recommends—it is as if you had chosen a 96-bit nonce at random, which means, because of the danger of a nonce collision, that there is a much smaller limit on the number of messages than if you had chosen a 96-bit nonce sequentially.


Compute $d$ such that $ed\equiv 1\bmod{\varphi(n)}$ using extended euclidean algorithm. Then compute $g = i^d\bmod{n}$.

This is basically RSA decryption.


Is there any asymmetric encryption algorithm for eliptic curve(secp256k1) without AES?

You can encrypt with secp256k1 (or any elliptic curve) by using ECIES (Elliptc Curve Integrated Encryption Scheme). However, inside ECIES a symmetric key is generated and the message is encrypted using it.

This is in contrast with RSA, which can encrypt data directly; though most of the time it is also used to encrypt a symmetric key and then encrypt data with that key.

If you really want to avoid AES, then you can use the secret derived inside ECIES and simply XOR with your message. Check the SEC 1 standard, section 5.1.3.


How to generate safe primes in a verifiable way?

Here's a very simple method: Find the largest number below $2^n$ that is a safe prime.  Use standard primality tests for $p$ and $q = (p - 1)/2$.  For example, $2^{2048} - 1942289$ is the largest safe prime below $2^{2048}$.

But you didn't specify what you want this for.  If you want to use this with Diffie–Hellman to resist discrete logarithms, then that won't be a good option.  The bit lengths you describe are designed for DSA, which has different security requirements.

For an $n$-bit safe prime to use with Diffie–Hellman, you want few small subgroups and you want to destroy the structure that the SNFS exploits, so you can pick the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$$ is a safe prime and congruent to 7 modulo 8.  The latter condition ensures that 2 generates the subgroup of quadratic residues in $(\mathbb Z/p\mathbb Z)^\times$, of prime order $(p - 1)/2$.  This is the technique used by RFC 3526 to pick standard groups at sizes from 1536 to 8192; the technique is described in RFC 2412, Appendix E.

This technique is sometimes called NUMS, for nothing-up-my-sleeves, because it uses the conventional transcendental constant $\pi$ instead of some inexplicable string of 1920 bits.  There's no security significance to $\pi$ except that it destroys some structure the SNFS could exploit—you could use $e$ instead, or $e^\pi$, or $\cos 1$, or all manner of other options to get a result you want if you knew of a small, say one in a million, fraction of primes that admitted a back door.  For this reason, may I interest you in doing Diffie–Hellman over rigidly selected elliptic-curve groups free of magic constants instead?  As a bonus, you get higher performance, smaller keys, easier defense against timing side channels, a number of high-quality implementations, and cooler names like X25519.

I'm not sure offhand what all the security requirements for Elgamal encryption: approximately nobody uses Elgamal encryption these days.  Naively, if the recipient given $(c, d)$ yields $d \cdot c^{-x}$ where $x$ is the secret exponent, then the adversary can apply the Lim–Lee active small-subgroup attack by supplying $d = 1$ and $c$ of small orders $n_0$, $n_1$, $n_2$, etc., to learn points ${g_0}^x$, ${g_1}^x$, etc., to which they can apply discrete logarithms in small subgroups to recover $x \bmod n_0$, $x \bmod n_1$, etc., and reconstruct $x$ with the Chinese remainder theorem.

Could I interest you in replacing your use of Elgamal encryption by X25519 in a NaCl crypto_box or libsodium crypto_box_seal, which have none of these finicky considerations and run much faster with fewer side channels and have smaller ciphertext expansion and are widely implemented and understood?


Create broken chain certificates for testing

Personally I wrote a generic ASN.1 decoder/encoder tool. It is called DDer. It transforms a DER-encoded object into a structured text representation (with parenthesis, somewhat reminiscent of Lisp). The interesting part is that it comes with a companion tool, MDer, which performs the reverse transform. Thus, you can edit certificate contents with a text editor, and MDer will work out the encoding subtleties.

Now a tricky remaining part is the signatures. Certificates are signed, and changing any bit in a certificate invalidates the signature, so this calls for a signing tool. I happen to have written my own crypto library (in C#, not published yet) that can apply a signature on an arbitrary DER-encoded object, even patching the inner SignatureAlgorithm in the to-be-signed structure of a certificate.

In a hurry, though, a RSA signature can be computed "by hand" with the help of the dc utility which is standard issue in Unix-like systems. That calculator can use hexadecimal input and output, process arbitrarily long integers, and compute modular exponentiations with the integrated | operator. Workflow would be:

Create the to-be-signed structure in the text representation of DDer, and use MDer to convert it to DER. When dabbling with certificates, you usually start with an existing certificate, so DDer-ize that.
Use sha256sum (another standard command-line tool on Linux) to compute the SHA-256 hash of the to-be-signed.
Assemble the hash value in a properly padded structure as befits RSA. You want to make it in hexadecimal, in a text editor. Make sure that all your hexadecimal is uppercase with no extra spaces, because that's what dc feeds on.
Use DDer on the private key file to obtain the key elements, specifically the modulus (first big integer) and the private exponent (third big integer in the structure)(the second big integer is the public exponent and is usually not that big).
Use dc to compute the modular exponentiation. You switch dc to hexadecimal input and output with 16 i 10 o (which reads as "set input radix to 16, then set output radix to 10"; that "10" is interpreted in hexadecimal, since you just switched the input radix to 16!). You then copy&paste the operands (padded hash, private exponent, modulus, in that order), and compute the modular exponentiation (|). You use p to print the result, which will be in hexadecimal.
Back to the DDer text representation of the to-be-signed, you write the wrapping structure, which is a SEQUENCE that contains the to-be-signed, an AlgorithmIdentifier that identifies the signature algorithm, and a BIT STRING whose contents are the signature value. MDer will expect the BIT STRING contents to be in hexadecimal, just like what you just obtained from dc, so it's a matter of copy&paste (again).
And a final MDer to produce the final certificate, DER-encoded.
If you need the new certificate in PEM format, convert with with openssl, or directly with the base64 tool (again a usual command-line tool in Linux) and add the -----BEGIN CERTIFICATE----- and -----END CERTIFICATE----- lines manually (this may be necessary in case you purposefully made an incorrectly encoded certificate, that openssl won't accept to convert).

If you can go through all these steps in due order, then you know enough about RSA and ASN.1 to write your own tools to apply signatures. If using C#, you can reuse the ASN.1 library from DDer, as well as the big-integer class (ZInt) for some very basic and perfunctory RSA implementation (not secure enough for use in production, but usable for making test cases).


Can DH_anon really be exploited by an attacker?

Ensuring that you're talking to the correct server is the client's duty. They need to verify the certificate and reject anonymous DH.

A client that accepts anon DH or doesn't verify the server's certificate is always vulnerable to MitM, even if the server disables anon DH.

Thus disabling anonymous DH on the server has little effect on security, beyond encouraging clients to choose proper ciphersuites. In the context of web applications, all popular browsers do not support anon DH to "secure" https.


security in the standard model → random oracle model?

As correctly pointed out by Ricky Demer it is not necessarily true. However, this implication does not hold for very specific cases. In the case of random oracle gates the existence of the RO changes the functionality of the "scheme", since with RO there are RO-Gates and without there aren't.

In most cases the existence of the RO does not affect the functionality of the scheme, meaning that with and without RO you have the exact same functionality. In these cases this implication holds I think.
The ROM, in comparison to the standard model, provides you with an additional oracle that realizes a truly random function, i.e. a function where the input and output are absolutely unrelated.
If you have proven something secure in the standard model, then you didn't need this additional oracle. The exact same proof will so to speak also hold in the ROM but will not use the oracle.

Even though an adversary might use the RO too, I don't see how this would help him if it doesn't affect the functionality of the scheme, since in this case the scheme and the proof are completely unrelated to the RO.


AES-GCM: What can be done if 'H' is known by an attacker

If the authentication key $H$ is known to an attacker, he could authenticate forged ciphertext and make the receiver believe that it is authentic.

This is very problematic, since the encryption part of the GCM mode is standard CTR mode encryption, which is actually a stream cipher. And like any other stream cipher, it is susceptible to a bit flip attack, where the attacker can alter any bit in the plaintext without actually knowing it.


Yes.  Any public random permutation should suffice.  (A public random permutation is like a random oracle, except it is a random permutation rather than a random function.)  A public random permutation is automatically length-preserving, and it meets the requirements for an all-or-nothing transform.

And, a public random permutation can be constructed in a number of ways.  The best construction depends upon whether we care more about theoretical concern or engineering concerns.

Theoretical perspective

From a theoretical perspective, the question of how to build a public random permutation has been answered by the following paper, at least for sufficiently long messages:

The Random Oracle Model and the Ideal Cipher Model are Equivalent.   Jean-Sebastien Coron and Jacques Patarin and Yannick Seurin.  CRYPTO 2008.  IACR ePrint 2008/246.

That paper shows that one can construct a public random permutation by using 6 rounds of a Feistel network, using a random oracle for the F function in each round.  They prove that this is secure in the random oracle model.  Replacing the random oracle with a cryptographic hash function then gives a reasonable construction.

Their construction will work as long as the message length is not too short.  If we want a public random permutation on $n$-bit messages, then their construction yields $k$-bit security as long as $n \ge 48 + 34k$.  For instance, if you want a 80-bit security level, their construction is proven secure for $n$-bit messages, as long as $n \ge 2768$ bits (i.e., $\ge 346$ bytes).  Thus, their construction is not useful in practice for short messages, but it is useful for long messages.  Their proof might be conservative, and it is possible that the actual security level is better than what their proof promises (so the scheme can actually be used securely on shorter messages than what I list here), but that's just speculation.

In summary, their construction yields a public random permutation on $n$-bit blocks, which in turn provides a length-preserving all-or-nothing transform on $n$-bit messages.

Engineering perspective

From a practical/engineering perspective, if we don't care about provable security, we can probably take any block cipher $E$ of the desired block width, choose a random key $K_0$, make $K_0$ public, and use $E_{K_0}(\cdot)$ as the all-or-nothing transform.  This is likely secure for typical block cipher constructions, though there is no proof.

From a theoretical perspective this can be shown secure assuming the block cipher can be modelled as an ideal cipher (e.g., it is free of related-key attacks, etc.), though that is a strong assumption that not all block ciphers may satisfy.

If the length $n$ of the message is very short, then we may need to use a special short-block cipher (e.g., with techniques for format-preserving encryption) as our block cipher.


Split 32-bit LFSR into two 16-bit LFSR which xor to same sequence

If a given 64-bit sequence is known to be the bit-by-bit XOR sum of
the outputs of two 16-bit LFSRs, then the degree-32 LFSR feedback polynomial
found by the Berlekamp-Massey algorithm is indeed the product of the
(16-bit) feedback polynomials of the two 16-bit LFSRs, and as @poncho said,
you need to factor the degree-32 polynomial into two 16-degree polynomials.
But, be aware that while this is guaranteed to work when the two 16-degree
polynomials are irreducible, there can be issues if the two 16-degree
polynomials are not irreducible or are not relatively prime. For example,
it might be that the Berlekamp-Massey algorithm (which finds the shortest
LFSR that will generate a given sequence) might give you an LFSR of length
less than 32 when the algorithm is applied to the 64-bit sequence.


TLS - self encrypting to avoid tls setup, secure?

It depends!

Any of the two alternatives TLS or directly symmetric encryption with a pre-shared key will of course require the sender (him/herself) to encrypt the data.

From a cryptographic perspective any statement about security/"being secure" even relative often requires specifity and not much about the actual ciphers are stated. that is why the answer is that it depends.

As much as it depends there are some points which might have some more general application.

TLS will be a stepwise procedure and use first asymmetric encryption (that with public and private keypair) to establish a secure channel. In another step it will then use this rather expensive/slow channel (because it takes more calculation power per transmitted data) to exchange a session key that is used for symmetric encryption. At this point you are at the point at which I assume your suggestion starts and that is that, you have a key only known to the legitimate sender and receiver.

Given that the symmetric encryption following a TLS initial handshake/sessionkey exchange is having the same attributes as the one you suggest with the "self"encrypted setup than there is no reason to see any difference in "security".

Indeed if you know were able to have a shared key for symmetric communication available on both ends of your communication, then this means no need to exchange a session key via asymmetric pub/pri-key encryption in the first place. At best with directly using symmetric encryption any vulnerabilities in the asymmetric part of the TLS can be avoided.


LFSR Output Sampling for Berlekamp-Massey

Berlekamp-Massey is designed for the situation where you have observed $2n$ consecutive output bits from a $n$-bit LFSR.  It doesn't work if the observed bits are scattered randomly, at random non-contiguous offsets in the stream.

Information-theoretically, a minimum of $2n$ bits of output are needed to reconstruct the LFSR.  Intuitively, this is because there are $2n$ bits of unknowns: the unknown $n$-bit state of the LFSR, and the unknown $n$ bits on the taps (the feedback polynomial).  Therefore, Berlekamp-Massey exactly meets the known lower bounds, in the case where you get to observe consecutive output bits.

Of course, you could also have used linear algebra to solve for these $2n$ unknowns, but Berlekamp-Massey is faster than solving a system of linear equations ($O(n^2)$ instead of $O(n^3)$, or something like that).

The number of observations you need depends only on the size of the LFSR, not on the output bits.  If you do know the size of the LFSR, you don't need to see any output bits to predict how much output will be needed.  If you don't know the size of the LFSR, seeing a few output bits doesn't help you predict the size of the LFSR and doesn't help you  predict how much output will be needed.

One cool thing about Berlekamp-Massey, though, is that you don't need to know in advance what the size of the LFSR is (what $n$ is).  You can just start running Berlekamp-Massey on the output stream, and it will generate candidates for the LFSR initial-state and feedback polynomial.  After each bit of output, it will update its candidate.  Once you've observed $2n$ bits of output, you are guaranteed that its candidate is correct.  If you don't know what $n$ is, you can take each candidate and test it against the next few output bits; this will let you recognize when Berlekamp-Massey has finally found the right candidate, i.e., when you've observed enough output stream (it'll let you recognize when you've hit the $2n$ limit, even though you don't know $n$ a priori).


How to obtain a one-value share in Shamir's secret sharing

Well, Shamir Secret Sharing is done using a field $GF(p^k)$, for some prime $p$ and some integer $k$.  A share consists of two integers $(x, y)$, where $0 \le x, y < p^k$.

So, the obvious way to express a single share $(x, y)$ as a single value would be to use the value $x p^k + y$ (using integer arithmetic, not field operations); each potential share would map to a distinct value, and during reconstruction, each value can easily be mapped by to the $(x, y)$ format.

Yes, this is just another way of doing concatination; you might find this somewhat more elegant.


Switching between AES and a highly performant algorithm

Yes, AES-128 is intended to be the standard block cipher for building a secure and efficient symmetric cryptosystem using some block cipher operating mode, like CTR for encryption or GCM for authenticated encryption; efficiency can be particularly good when there is hardware support for AES and GCM.

There might be better choices in the case at hand, like for a 32-bit CPU ChaCha (perhaps combined with Poly1305 for authenticated encryption), or one of a plethora of  lightweight block ciphers. If the device is 8-bit, and speed/efficiency paramount, one might even consider the deprecated and partially broken RC4, although its security is questionable even when discarding the beginning of the keystream.

Notice that keeping secret the key of either of these algorithm is hard in a non-security CPU assumed in the hands of an adversary, to the point of being best considered impossible facing a competent and determined adversary. And in a modern security CPU, you might have AES in hardware (thought often, optimized for security rather than speed).


Will publishing two or more public keys of the same RSA private key cause a security risk?

You can't have two different public keys for the same RSA private key.  That's just not how RSA works.

Well, almost.  There's a minor technical loophole, and it's the fact that RSA has equivalent keys.  In particular, the public keys $(n, e)$ and $(n, e + \lambda(n))$ are equivalent, in the sense of producing the same ciphertext for the same (padded) plaintext.  But there are two reasons why you never want to publish two such equivalent keys:

It's useless, since they're literally equivalent.  You might as well just send the same public key to both peers.  Encrypting a message (or verifying a signature) using a large public exponent is slower anyway, so it's best to just do things the usual way and use one of the standard small public exponents like $e=3$ or $e=2^{16}+1=65537$.
It completely breaks the security of the system.  Knowing two equivalent public keys with different exponents $e$ and $e'$ lets anyone learn their difference $\delta_e = |e - e'|$, which must be a multiple of $\lambda(n)$.  Knowing a non-zero multiple of $\lambda(n)$ is enough to solve the modular congruence $ed \equiv 1 \pmod{\delta_e}$ and obtain the private decryption exponent $d$ (or something equivalent to it — RSA private keys can also be equivalent but not identical in exactly the same way as public keys).

So, you know, don't do that.  Just generate your RSA key pairs the usual way, with one public key for each private key and vice versa.  And remember that the public key is supposed to be public, so you can always share the same public key with any number of people.

Ps. While copyediting your question, I noticed that you mentioned signing messages.  With RSA signatures (and digital signatures in general), you cannot (usefully) sign messages with public keys, but only with the private key.  So e.g. if Bob wants to send a message to Alice, he should sign the message with his private key, and then encrypt the signed message with Alice's public key (and make sure before signing that the message says it's for Alice, so that she can't just re-encrypt it with Charlie's public key and make it look like Bob sent it to Charlie).

Also, it's generally not a good idea to use the same key pair for signing and encryption, even if algorithms like RSA technically allow it.  So in practice, every peer should really have two private RSA keys (one for signing, one for decryption) and every other peer should know the public keys corresponding to both of them (so that they can both encrypt and verify signatures).

Pps. For a simpler and more practical solution, ditch RSA entirely and replace it with e.g. NaCl / libsodium crypto_box.  It's simpler and faster, the keys and signatures are smaller, you only need one keypair for each peer, and since it's an all-in-one integrated solution, it's a lot harder to use it wrong and end up with a security hole than it would be if you insisted on rolling your own signing and encryption scheme with RSA.

Or, perhaps even better yet, don't try to design your own messaging protocol at all, but just use an open source implementation of some published and well studied protocol such as Signal.  Designing a good and secure messaging protocol is not easy, with all sorts of non-trivial details like protecting past conversations from the possibility of a later key compromise.  It's much easier to just use an existing protocol designed by smart people who have already considered those details and found ways to handle them.

(Even if you do insist on making your own messaging protocol, it's at least a good idea to review some widely used and studied existing protocols like Signal and see what issues their designers have considered and how they've dealt with them.  That way, you get a chance to learn from other people's mistakes instead of your own.)


Why aren't there function based discrete log problems?

Applying a function successively as you indicate does indeed form a group - Each time the function is applied, it is effectively equivalent to incrementing the group value by 1. This allows for an indirect way to compute an addition operation, by enumerating the number of times that the function has been applied.

You can actually instantiate Diffie-Hellman with an arbitrary deterministic function $f$ - correctness is guaranteed, but security is not.

Effectively, your DH private key is the number of times that the function has been applied. In classic DH, the function $f$ is simple multiplication by the generator $g$.

It is easy to see that when you apply the function $x$ times, and then apply the function $y$ more times, then the function has been applied in total $x + y$ times. Provided that both parties use the same $f$ and initial starting value (the generator $g$), both parties will arrive at the same value.

An example with small numbers:

$priv_1 \leftarrow 4\\
priv_2 \leftarrow 3\\
pub_1 \leftarrow F(F(F(F(g))))\\
pub_2 \leftarrow F(F(F(g)))\\
share_1 \leftarrow F(F(F(F(F(F(F(g)))))))\\
share_2 \leftarrow F(F(F(F(F(F(F(g)))))))$

Clearly, $share_1$ and $share_2$ yield the same output, as the function has been applied the same number of times. Thus correctness is guaranteed.

Challenges

There are three challenges that I have encountered to create a DH protocol this way.

The first is finding some $f$ that is difficult to recover the number of times that $f$ has been applied, given some output $F(F(F....(g)))$.

Failing to fulfill this property implies the ability of an adversary to recover the private key

The second is that the public keys must not be usable to reach the shared secret.

I.e. if $share_{secret} = pub_1 * pub_2$, then recovery of the private key is not necessary to break the system

The third requirement is that the function must offer an algebraic shortcut that allows you to compute the $N_{th}$ term without actually invoking $f$ $N$ times. For example, you can instantiate a DH like protocol using a standard cryptographic hash function such as sh256 - but there is no way to shortcut such a function. For security, a private key is a number that is at least 128 bits in size; Using sha256 for DH would imply the need for on the order of $2^{128}$ invocations of the function.

Without an algebraic shortcut, computing a public key is computationally intractable.

There is a actually fourth requirement that may or may not be trivial to fulfill: Finding a generator for the group must be "easy". (thank you to MarquisDeSitruce for pointing this out)

If there is no generator, you cannot generate group elements, and hence no key agreement can occur

Edit in response to further questions/comments

Since $f$ can be an arbitrary function, some are indeed trivial to recover the private key from, others are not; The exact way to violate that requirement depends on the exact ff that you use. Clearly if ff is $x+1$, then recovering the private key from the public key is trivial. There must exist no algorithm that can recover the private key in less time than guessing it; It does not have to be an otherwise convenient/trivial algorithm i.e. LLL could probably break $mx+b$.

Side note about $mx + b$

Actually, I have experimented with that particular function $mx + b$. It provides a shortcut (involving modular exponentiation and a geometric series); Unfortunately, it is broken. I don't usually bother to write up attacks, I tend to perform them live in the python interpreter. I don't remember the attack offhand, if I recall correctly it was algebraic, breaking the system in negligible time/space.


What's the difference between a known-plaintext attack and a ciphertext-only attack in terms of performance?

Usually we are talking about various attacks which are better than brute force, these attacks can very greatly depending on what we can do.
Ciphertext only is usually the most restrictive setting. Known Plain text where we have several plain&cipher text pairs is common. But we also have other attack modes. chosen cipher text, adaptive chosen plain text and mode.

If we take some classical ciphers for example. We will see a significant difference between the cipher text only and known plain text attacks. We know how to perform ciphertext only attacks on Viginere or substitution ciphers using only statistical knowledge about the plain text such as letter frequencies. But with a known plain text the key is trivially revealed. In Viginere subtract the cipher from plain and receive a repeating key. Without any tricks for finding key length or matching column frequencies.

Even with the simplest ciphers we see differences.

Also with modern attacks, different attacks published require different kinds of access. For a more modern example, let's look at a stream cipher with a limited internal state. For instance A5 family used for cell phone encryption. With cipher text only we don't have much to do in the way of generic attacks. we can brute force internal state and do a crib drag over cipher text to see if we find something that looks like plain text.
However when we know parts of the plain text (and we almost always do, due to protocols used and other reasons). We can do better, we can get parts of the key stream by xoring the known plain text with the cipher text. And not only brute force the internal state more efficiently looking for matches in the key-stream fragments we have, we can even off load most of the work and do Time-Memory-Date trade-off attack.

Better access, often leads to better more efficient attacks, though these are still specific to the cipher of cipher family.


How much stronger is RSA-2048 compared to RSA-1024?

You can use the complexity of the GNFS, the fastest known general-purpose factoring algorithm, to estimate the strength (in bits) of an RSA key size.

Referencing the table linked above, a 1024-bit key has approximately 80 bits of strength, while a 2048-bit key has approximately 112 bits. Thus, it takes approximately 2112/280 = 232 times as long to factor a 2048-bit key. In other words, it takes around four billion times longer to factor a 2048-bit key.

Thus, if you were able to magically factor a 1024-bit key in 10 seconds (which is totally unrealistic in every way possible, I may add), then it would take around 1,200 years to factor a 2048-bit key (note: this is not adjusted for Moore's law). Of course, it took around two years and a massive collaborative effort just to factor a 768-bit key, so factoring a 1024-bit key takes far, far longer than 10 seconds. But this is just to demonstrate the point: 2048-bit keys are much more secure.

If you do want to adjust for Moore's law and the ever-faster pace of computing, you can use this approximation by fgrieu. If you solve the equation for when a 2048-bit key is expected to be factored (keeping in mind that this is a rough approximation), you arrive at the year... 2048. So somewhere around 2040-2050, if that linear approximation holds true, we expect 2048-bit keys to be feasibly factored. In comparison, you can see that the 1024-bit key is expected to be factorable sometime around 2015-2020.


Why does WPA2-PSK use 4-way handshake instead of 2-way handshake

No, two messages is not sufficient to achieve what the WPA2-PSK 4WHS is supposed to do: mutual authenticated key-exchange.

The key term here is mutual authentication. Remember, at the start of the WPA2-PSK handshake we have two entities, the access point and the client, holding (hopefully) the same key, also known as the pairwise master key (PMK). Now they want to authenticate themselves by proving that they are both in possession of the PMK. This is the point of the 4WHS (in addition to establishing session keys).

Now let us consider your suggestion: (1) First party (assume this is the access point, as in WPA2) sends a nonce $N_A$ to the other party (the client). (2) Client responds with his own nonce $N_C$, the access point nonce $N_A$ and potentially some other stuff, and computes an HMAC tag on it using PMK. (3) The access point verifies the response from the client using the PMK. At this point, what can the two parties be sure of?

For the client, the answer is: Nothing! Remember, all the client sees is a lonely nonce $N_A$. This could have been created and sent by anyone. Hence the client can have no guarantee that he is actually talking to the right access point.

For the access point, the situation is slightly better. Since he receives back the nonce he himself created ($N_A$), he can be reasonably certain about the freshness of the response (i.e. this is not a replay), and since the HMAC tag checks out he can be certain that the client must also be in possession of the PMK. (Digression: It is however bad form to use long term keys, like the PMK, directly in your cryptographic computations. Usually one derives temporary keys which are used instead. This is also done in WPA2). Hopefully, this also makes it clear why we need the HMAC tag. It is there to convince the other side that it is in possession of the PMK (and of course to detect tampering, but which is aside the point here).

More generally, in an authentication protocol based on nonces, at least three messages are needed in order to establish mutual authentication. With two messages or less, you would also have to use something like a time-stamp in order to ensure mutual authentication (however, this is non-trivial to do correctly in practice and even harder to model theoretically, see for instance: Modelling Time, or A Step Towards Reduction-based Security Proofs for OTP and Kerberos). Why WPA2 uses 4 messages instead of just 3 I am not sure, however it is similar to the 4WHS in TLS, which also uses the last message to "install" the generated keys.


The number of keys generated in TLS 1.2?

1) Does that means the kdf generates "actually" 6 keys, but in fact they are 4 keys?

The KDF generates 6 values; of the 6, 4 of them can be considered "keys" (in the sense that they'll be used to key some cryptographical primitive) and 2 are not (an IV is typically not considered a "key", as exposing it does not yield a security weakness).

Also, some TLS transforms do not use all of the 6 values; the protocol handles that by making the length of the values they don't use to be 0 (so the same general structure applies).  I mention this because you may run into this situation later on...

  3) IS the client_write key different from the server_write key?

Yes, the client_write key is different from the server_write key.  The client_write key is used to encrypt the traffic that is sent by the client to the server, while the server_write key is used to encrypt the traffic that is sent by the server to the client.

As for why they use two different keys for the different directions, well, the original SSL protocol had different keys in the two directions because it used RC4 as the encryption transform, which would have serious problems if you used the same key in the two directions.  When we get to TLS 1.2, they maintained the same structure, in part because they still support RC4, in part because it also helps some transforms (e.g. GCM, which you could use the same key in both directions if you were careful with nonces, but it's easier not to have to worry about that), in part because using different keys for different purposes is just good practice, and in part because there was no real reason to change.

  shouldn't they generate a share secret?

Actually, the shared secret (assuming you're using a DH-based transform) is computed much earlier, as the premaster secret.  That's one of the inputs into the KDF, hence all the keys generated by TLS depend on it.

To answer your further questions:

  Which key is the key used in the Finished MAC ?

The master secret; that's not any of the 6 traffic values (which are used to protect traffic between the two stations), but an intermediate value that is generated from the premaster secret, and in turn is used to generate the 6 traffic keys.

And, yes, it is a value that is shared between the client and the server (absent a man-in-the-middle attack).

  But the standards talk about 6 keys, each party has its own key?

Again, only 4 of those values are "keys"; in any case, they are used to protect records that are exchanged between the client and the server; they too are also common between the two sides, with the understandard that the 'client->server' traffic will be protected by 3 of those values, and the 'server->client' traffic will be protected by the other 3.  All these keys are symmetric, so for the system to work, both sides need to know their values.

If you really want to learn about TLS 1.2 from the source, you might try looking at rfc5246.  This is not a description of TLS 1.2; it is the official definition, and hence cannot be wrong.


Discrete Log with regard to a random base

You are asking if it is hard to find $s$ given $r^s$, but you do not mention if $r$ is also given.

If $r$ is not given, then the problem is: given some value $y$ find $r$ and $s$ such that $r^s=y$. This is an easy problem - just outputs $r=y$ and $s=1$.

If $r$ is given, then the problem is: given $(r,y)$ find $s$ such that $r^s=y$, where $r,s$ are randomly chosen. This is a form of the discrete log problem where the base is random. This makes it ``harder'' in the sense that the adversary cannot preprocess. I don't know if it has anything more established than this.


Help in understanding exactly how lattices used as one way functions for hashing

I'm also afraid you couldn't understand this as D.W., but let us start.
I sometimes cannot understand your questions. Please restate them, if possible.

The definition of the Ajtai hash functions

Let $n$, $m$, and $q$ be positive integers.
Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$.
Let us define a function, which maps a vector in $D^m \subset R^m$ to $R^n$ and is indexed by a matrix $\boldsymbol{A}  \in R^{n \times m}$ as follows:

$f_\boldsymbol{A}(\vec{x}) = \boldsymbol{A} \vec{x} \bmod{q} = \sum_{i=1}^{m} x_i \vec{a}_i \bmod{q}$.

The Ajtai hash functions is defined as a family of the above hash functions;

$\mathcal{F}_{n,m,q,D} = \{f_{\boldsymbol{A}}:D^m \to R^n \mid \boldsymbol{A} \in R^{n \times m}\}$.

You can obtain your function by setting $n=1$, $m=2$, $q=5$, and $D = R$;
then set $\vec{a}_1 = 14 \ (= 4)$ and $\vec{a}_2 = 13 \ (= 3)$.

For example, you can set $n = 256$, $q = 4097$, $m = 4096$, and $D = \{0,1\}$.
The input of the function is a bit string of length $4096$
 and the output of the function on such parameters is $256$-dimensional vectors whose coefficients are in $\mathbb{Z}_q$.

Is it shrinking?

Good parameters makes the above functions shrinking.
Correctly speaking, if the size of domain is larger than the size of range, that is, $|D|^m > |R|^n$, the function is (obviously) shrinking.

A possible choice of parameters is $D = \{0,1\}$ and $m > n \log_2(q)$, which often appears in the context.
Another possible choice is $D = \{-1,1\}$ or $D = \{-1,0,1\}$.

Is it hard to find a collision? What is the relation between a collision and a short vector?

  How exactly is this linked to the shortest vector problem or short integer solution if they are not the same thing?

If $D = R$, it is too easy to find the collision is function by the power of the linear algebra. You can use Gauss's elimination if $R$ is a field.
But, if $D \subset R$ and the size of $D$ is small, it becomes hard.
Roughly speaking, the number of collisions depends on the ration $|D|^m/|R|^n$.

In 1996, Ajtai shows that, for good parameters, if there exists an inverter of his hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice.
Goldreich, Goldwasser, and Halevi pointed out in the note you refer that, if there exists an algorithm finding a collision of the Ajtai hash functions, then there exists an algorithm finding a short vector from any $n$-dimensional lattice.
The reductions are based on the fact that the sum of short vectors is (relatively) short.

How should we interpret the above in lattice words?

You would skip this part.

We define a lattice related to a matrix $\boldsymbol{A}\in R^{n \times m}$ as

$\Lambda = \Lambda_q^{\perp}(\boldsymbol{A}) = \{\vec{e} \in \mathbb{Z}^m \mid \boldsymbol{A} \vec{e} \equiv \vec{0} \bmod{q}\}$.

This $\Lambda$ is an $m$-dimensional lattice.
(You can check this is a lattice by verifying that for any two vectors $\vec{e}, \vec{e}' \in \Lambda$, the sum of them lies in $\Lambda$ again.
 You can check this is $m$-dimensional by verifying that any $q \vec{u}_i$ is in $\Lambda$, where $\vec{u}_i$ is a unit vector).

This lattice defines a map from $\mathbb{Z}^m$ to a quotient group $\mathbb{Z}^m/\Lambda$, which is isomorphic to $R^n$.
The map is a hash function.

Conversely, a collision $\vec{e} \neq \vec{e}'$ for $f_{\boldsymbol{A}}$ implies a short non-zero vector $\vec{e}-\vec{e}'$ in $\Lambda_q^{\perp}(\boldsymbol{A})$.


How to choose the size of the IV in AES-GCM?

But how to choose the IV's size and how - if so - it affects the
  security of the algorithm?

You really want to give 96-bit IVs to GCM (pad them if neccessary).

If you pick any IV size but 96-bit, GCM's polynomial hashing function GHASH is invoked to get the IV size down to 128-bit. This means that you basically apply a PRF on your IV, which means that there's a decent chance of hitting a collision if you use about $2^{64}$ IVs which will allow for a key-recovery attack on GCM and allows you to forge ciphertexts (numbers corrected by poncho).

NIST SP800-38D (PDF) has further treatment on the security considerations (especially with regards to IV sizes) in section 8. Furthermore it is the specific recommendation of NIST to use a 96-bit IV (section 5.2.1.1, found by Maarten):

  For IVs, it is recommended that implementation restrict support to the
  length  of 96 bits, to promote interoperability, efficiency, and
  simplicity of design.


What does "birational equivalence" mean in a cryptographic context?

I feel that as it was my comment, I am obliged to answer this :-).

First of all, birational equivalence is really a geometric notion. As far as I know, there is no analogue for groups, rings or fields and therefore the cryptographic relevance is limited. It becomes relevant when speaking of geometric objects: for example, elliptic curves.

Given these geometric objects, we want to define what it means to be "the same". The usual terminology is that given two curves $E_1$ and $E_2$, they are "the same" when they are isomorphic. There is another way to equate objects, and that is by saying that they are "almost the same". This is what a birational equivalence does: two curves $E_1$ and $E_2$ are birationally equivalent when there is a map $\phi:E_1\rightarrow E_2$ between them which is defined at every point of $E_1$ except a small set of exceptions and there is an inverse map $\phi^{-1}:E_2\rightarrow E_1$ which is defined at every point of $E_2$ except a small set of exceptions. This definition is very close to that of an isomorphism, except for the fact that we allow some exceptions.

To make this more concrete, you could think of an isomorphism as a tuple of polynomials:

$$\psi:E_1\rightarrow E_2,\quad (x,y)\mapsto (f(x,y),g(x,y)),$$
where $f,g$ are polynomials in $x,y$. The inverse is also defined in terms of polynomials.

A birational map can be thought of as a tuple of fractions of polynomials, say

$$\phi:E_1\rightarrow E_2,\quad (x,y)\mapsto \left(\frac{f_1(x,y)}{f_2(x,y)},\frac{g_1(x,y)}{g_2(x,y)}\right).$$

This is defined at all points $(x,y)$ except for the ones where $f_2(x,y)=0$ or $g_2(x,y)=0$. The inverse is also a fraction of polynomials, and can therefore be undefined at certain points.

Now let's make this even more concrete, and follow the Ed25519 paper. The Curve25519 curve is defined by $$E_1:v^2=u^3+486662u^2+u.$$
It is birationally equivalent to the Edwards curve given by
$$E_2:x^2+y^2=1+\frac{121665}{121666}x^2y^2.$$
The birational equivalence is given by the map $\phi:E_1\rightarrow E_2$ defined by
$$\phi(u,v)=\left(\frac{\sqrt{486664}u}{v},\frac{u-1}{u+1}\right).$$
Notice that it is undefined for $v=0$ or $u=-1$, and therefore is not an isomorphism. The inverse map is defined by
$$\phi^{-1}(x,y)=\left(\frac{1+y}{1-y},\frac{\sqrt{486664}u}{x}\right).$$
Again, it is undefined for $y=1$ or $x=0$.

Finally, consider the twisted Edwards curve
$$E_3:-x^2+y^2=1-\frac{121665}{121666}x^2y^2.$$
There is a map $\psi:E_2\rightarrow E_3$ defined by $\psi(x,y)=\left(ix,y\right)$, assuming that $i$ is a square root of $-1$. This is clearly defined everywhere, and is an isomorphism.


What are the differences between plain and encrypted private keys?

There is no such thing as a PKCS#5 plain private key. PKCS#5 defines Password Based Encryption (PBE) and it is noted that this can be used to encrypt a private key.

PKCS#8 does define plain and encrypted private keys. By using a parameterized object identifier that indicates one of the PKCS#5 schemes you can encrypt the private key.

Which one you should use if any is up to you and your requirements.

Encrypted private keys can be used to perform password based decryption where the encryption is performed by the corresponding (unencrypted) public key. The other party in other words don't need to know the password, they just need to have and trust the public key. Arguably PGP would be a better defined / more compatible format for that though.

Another advantage is that the password can be used to encrypt the private key so that the private key can be stored on e.g. a backed up network connection. This would be secure as long as the password used is relatively secure (note that dictionary / brute force attacks are possible in this kind of scheme).

Of course there are certainly other and more secure ways to protect a private key. Plain private keys should normally only be used for testing, although storing them on separate media (a thumbdrive for instance) could give some protection.


Usefulness of blockchain technology in private sector

Why not use a good old standard database in such cases?
Am I missing something?

No; you understand it perfectly well! It's nothing more than a particularly strange form of data integrity assurance (that, as you quickly realize, is trivially bypassed if not distributed across multiple nodes). If you're not using it as a resistance to adversarial peers, and you're not using it for consensus-building purposes, then there's little benefit to be wrung from prefacing each $\text{block}_n$ with $H(\text{block}_{n-1})$.
Even distributed systems such as highly-available and fault-tolerant hypervisors that have to "solve" the Two Generals Problem accomplish their task perfectly fine with non-blockchain-based consensus algorithms.
(However, as the commenters note, this is much more of a systems engineering question than a cryptographic one.)

I will amend this answer to note that Merkle trees per se can be useful in situations where you require, for instance, the public to be able to easily audit or assure themselves that some log has remained append-only, such as in the Certificate Transparency security addition to HTTPS. But (again a nod to Peregrinus) these aren't "blockchains"* since they're not being leveraged for consensus: the scheme itself imposes no restrictions on the whole thing being rewritten; all the auditors can do is sound the alarm if they see a fork in the tree.
(*As evidenced by the fact that a quick search turns up a whole host of schemes proposing blockchain-based augmentations of CT.)


Advantages of group signature schemes without encryption over with encryption

Usually the schemes without encryption are more efficient in terms of computational and size complexity. This owes to the fact that encrypting a membership certificate and proving the consistency is typically more expensive than simply randomising some signature and proving a simpler statement.

It should be noted, however, that some schemes following the without encryption paradigm are secure in a weaker model than the schemes which use sign-encrypt-proof. For example, in the scheme in this paper, the anonymity guarantees are lost upon leakage of a user key. It was only recently shown that one can actually construct highly efficient schemes following the without encryption paradigm which achieve security in the strongest model for dynamic group signatures.

Also see the introduction of this paper for an in depth discussion of the pros and cons (the term sign-randomize-proof is used there to describe the paradigm used by without encryption schemes, as this captures the essence of the without encryption paradigm more appropriately).


Are there security issues with adding plaintext length to TLS packets?

Not so high, the size of the plaintext should be known in advance. For all the stream cipher based cipher suites, including the ones with the newer authenticated ciphers the size of the plaintext can be directly derived from the ciphertext.

CBC mode only hides the plaintext length in the bounds of the block size - if that. You can however possibly abuse this to create a covert channel. Furthermore, you would be working out of spec - your scheme would not be compatible with TLS. You would only save up to the block size in bytes in your implementation at most, so the returns would be very small.

You may be better off choosing a cipher suite that uses a stream cipher instead. In that case the plaintext and ciphertext have the same length. Currently however that means RC4 or GCM mode encryption in TLS 1.2. In case of GCM you may have to subtract the size of the tag from your calculations of course.


Do any NIST PQC have "homomorphic" public keys, in the sense that any two pubkeys derive a combination pubkey?

No, this does not survive as is in the quantum world, since all discrete logarithm schemes (including Diffie-Hellman) are broken.

And more generally, this is probably not possible in the quantum world a priori, because it would imply having group homomorphic properties, which are hindered by the fact that Shor's algorithm is actually made of two parts:

A reduction of the factoring problem to the problem of order-finding.
A quantum algorithm to solve the order-finding problem

and the problem is that the order finding part implies that it allows to find the order of a group element, thus allowing to break the discrete logarithm easily.

There is even an impossibility result from 2014 for group homomorphic encryption in the quantum world.
Its core idea is basically that you can win the IND-CPA game by choosing two messages $m_0$ and $m_1$ such that $m_0=e$, and $m_1\neq e$, for $e$ the identity element in your plaintext group, which will be mapped when encrypted to the identity element of the ciphertext group, and since you can compute the order of an element using Shor's order finding part, you can find whether the ciphertext has order 1 (in which cases it corresponds to $m_0$) or not.
And the same kind of problems will arise with digital signatures or key exchanges algorithms.

This is also the reason why it is extremely difficult to come up with zero-knowledge proofs that are quantum safe.


Is there a definition of the pseudo-random sequences like PRG or PRF in cryptography?

I think that the pseudo-random sequence and the truly random sequence are indistinguishable.
And I think the definition should describe some possible collections of "pseudo-random sequences" (e.g. M-sequence).

Congratulations, you have a very good intuition! You're almost there.
A key to understanding the definition of a pseudorandom sequence is that there is no such thing as a pseudorandom sequence. If you have a specific sequence, then there's no randomness involved! Instead, the useful concept is that of a pseudorandom sequence family, more usually called pseudorandom function family (but abbreviated PRF). In a nutshell, a pseudorandom sequence family is a family of sequences such that given some data that may or may not be part of a sequence in that family, and bounded computational power, there is no way to know whether the data is from a sequence in the family or was generated uniformly at random. In other words, a pseudorandom sequence is indistinguishable from a random sequence.
Note that “uniformly at random” here is a mathematical definition: a uniformly random bit sequence is one where the value of each bit is independent (in the sense of probability theory) from the value of other bits as well as from all other events in the world. This definition does not consider whether it is possible to perform this generation in the physical world.
The definition of pseudorandomness only considers the output of the process, not how this output is produced. Otherwise it would be a circular definition: a pseudorandom generator is one that produces pseudorandom output — “pseudorandom output” has to have some definition other than where the output come from. The definition is about what you can deduce from observing the output. A pseudorandom generator is an algorithm that transforms a seed into the element of a pseudorandom sequence family that is indexed by the seed value.
To put this indistinguishability in more mathematical terms, consider an observable property $A$ of the output. For example, “bit $3$ is 1 and bits $4$, $5$ and $6$ are not all equal”. This observable property has a certain probability $\Pr_U(A)$ of being true for the uniform random distribution ($\frac{1}{2} \cdot \frac{6}{8}$ for the example above). If you pick a random element of the pseudorandom sequence family $F$, the probability of this observable property $\Pr_F(A)$ must be close enough to the probability for the uniform random distribution: $\Pr_F(A) \approx Pr_U(A)$.
To make this definition fully precise, we still need to say what observable properties are permitted and what “close enough” means. We aren't interested in adversaries with infinite computational power, which is why we restrict $A$ to polynomial computations. And “close enough” is defined as bounded by a negligible function. That's how the equation in your question comes about. The piece that you were missing is that you don't first select specific sequences $\alpha$ and $\beta$. Rather, $\alpha$ and $\beta$ are a probability distribution over sequences: $\alpha$ is a choice of element of the function famility, and $\beta$ is a uniform choice over all possible functions.