Is the "Signed on date" of a PGP Signature Verified?

The "signed on date" field of any signature message format is only trustworthy if you trust the signer to not

modify the software to include an arbitrary date (or use a software which allows setting the date) or
change his computer's system date.

So, if the signer wants to use this field to prove that this was signed at some time (specially, before some time), it is not trustworthy at all.

There are cryptographic means to certify that some data was signed at a certain point in time, but these use either a trusted third party (a signature service, which signs some digest of your message/signed message/... and a time stamp), or even a distributed system with a public time line.

An example would be something like the BitCoin block chain - for every piece of data referred from a block in the chain (i.e. from a transaction) you can be quite certain that it existed before the block was created, as long as the used hash functions are not broken. On the other hand, if you include in your signed data a hash of the latest block, your data bundle is certified to be newer than this block. (But of course, you could have recreated it later.)


Is it possible to break the SHA-512 hash algorithm?

We don't know. That is: it is impossible to prove that there aren't any attacks possible on SHA-512. But that doesn't mean that it can or cannot be broken.

  Are there any successful attacks out there?

No, except length extension attacks, which are possible on any unaltered or extended Merkle-Damgard hash construction (SHA-1, MD5 and many others, but not SHA-3 / Keccak). If that's a problem depends on how the hash is used. In general cryptographic hashes are not considered broken just because they suffer from length extension attacks.

The SHA-3 competition was created to replace SHA-2 in case it would be broken in the same way as it's predecessor, SHA-1. However during the competition it became clear that SHA-2 in itself looks pretty secure.


What is the difference between probabilistic and deterministic prime-factor recovery function in NIST 800-56B?

The probabilistic algorithm has (at least part) of it's runtime that follows an approximately geometric distribution. So it can sometime take a long time. In some applications, that's an issue: for excellent reasons, there's almost always some finite timeout to any process, often determined experimentally. Geometric distribution of execution time is a tried and tested method for field failures. I've seen this in more than one Smart Card production line at the RSA key generation step.
I have not analyzed the deterministic algorithm in detail, but it's maximum run time for a given parameter size can be strictly bounded, and is I guess lower than for the probabilistic algorithm in some sizable fraction of cases (perhaps, often; or even to the point of being faster on average). Also, if an implementation is made strictly constant-time, that's one less area of worries against side-channel leakage.


Homomorphic Encryption, LWE, and Practical Applications

I'll do this backwards

  If a database has two data types - TEXT (character arrays) and INTEGER (4 or 8 byte integral values), will 'p' ever be 'small' enough to transform an INTEGER value in-situ or in place?

No. Homomorphic ciphertexts are still way to big to be stored in a 32 or 64 bit integer. You would likely store the ciphertexts in a string (encoded in some way).

  When the authors discuss a small modulus p used for the transition from (n, log q) to (k, log p), how 'small' are they talking about?

They give the following hint in the paper

  To give a hint as to the magnitude of improvement, we typically set $k$ to be of size the security parameter and $p = poly(k)$. We can then set $n = k^c$ for essentially
  any constant $c$, and $q = 2^{n^\epsilon}$. We will thus be able to homomorphically evaluate functions of degree roughly $D = n^\epsilon = k^{c\cdot\epsilon}$ and we can choose $c$ to be large enough so that this is sufficient to evaluate the ($k$; $\log p$) decryption circuit.

So the size of $p$ is polynomial in the size of the security parameter. Note that the size of $q$ is $n^\epsilon$. $n$ is exponential in the size of the security parameter. So you go from exponential in the security parameter to polynomial, but we are still talking very, very large compared to a 32 or 64 bit integer. I believe ciphertexts in other FHE systems are on the order of kilobytes or megabytes and those were systems that improved upon this scheme.


how to prove our algorithm is secure against chosen plaintext attack?

The usual approach to prove IND-CPA security is to construct a logical argumentation called "reduction". In this argumentation you first start with the assumption that certain computational problem is hard (for example, the Decisional Diffie-Hellman assumption), and then you proceed to demonstrate that if your crypto scheme were insecure with respect to IND-CPA (which means that the adversary has access to an encryption oracle), then you could construct an algorithm that uses your scheme to break the hard problem. If our current knowledge dictates that indeed the chosen problem is hard, then your scheme must be IND-CPA-secure.
No. A trivial counterexample would be a deterministic encryption scheme. It is a well-known fact that an encryption function that is deterministic cannot be IND-CPA-secure. This is true regardless if its output is uniformly distributed.


Functional difference between stream cipher, XOF, seed expander, KDF, etc

Before we start answering the subquestions, let's bring up some background knowledge.

The sponge construct was first proposed by the Keccak team as a bridging element in a security proof for the older RadioGatún hash function. On their web page, they describe it as a generalization of both hash function (var->fix) and stream cipher (fix->var).

Since SHAKE-128/256 are directly based on sponge constructs, we'll just assume for now that the authors intended XOF as the generic term for their trademark product Sponge.

type                input                  output
stream cipher       fixed-length key       variable-length key-stream
xof                 variable-length data   variable-length data
hash function       variable-length data   fixed-length digest

So question 1 can be answered as follows: no, that would violate the definition of XOF.

And question 2: no. They're stream ciphers, two of which use the counter construct.

If you search "cryptographic seed-expander" on Bing in 2018-02, then the first few results unrelated to Crypto.SE refer to the NIST page for post-quantum cryptography. The story goes like this:

Back in the early days of preparing for the contest, NIST specified that submitters obtain randomness source for their keygen-signing-encrypt functions using libc rand(). This was correctly met with protest by notable participants on the official mailing list.

After discussion, it was decided there would be separate randomness calls for 1.) generating small amounts of keying material sufficient for a given security level, and for 2.) expanding keying material into a longer bitstring from which mathematical objects could be extracted.

The latter has since been called "seed expander" in official NIST documents, which roughly corresponds to DRBG.

So question 3 can be answered as follows: It does what a DRBG/PRNG does. The interface of a DRBG applies.

I'd like to answer question 4 as follows: It doesn't make sense to compare them, because their purposes are different. And this difference in purpose makes their programming interface different as well. For example, the typical interface for a XOF function is much simpler than that for a DRBG, and has many fewer parameters to tune than KDF.


Blum Blum Shub Pseudo-Random Generator Requirements

Your understanding of the requirements are correct. To elaborate, the first requirement you specify can be explained as taking the parity of $x_i$. Also, the two primes are called Blum primes and the modulus is called a Blum integer, which means $p,q \in \mathbb P$, $p \equiv q \equiv 3 \pmod 4$, and $N = p \cdot q$.
There are a few other requirements, such as choosing a random $p$ and $q$ of approximately equal length (essentially the same requirements for generating RSA primes, modulo congruence relations). The initial seed, $x_0$, must also be sufficiently large and must be kept secret along with the primes. Finally, $p$ and $q$ are typically chosen such that $\gcd(\varphi(p),\varphi(q))$ is small in order to maximize cycle length. They must be strong primes, usually done by choosing safe primes (integer $p$ is a safe prime if $p,(p-1)/2 \in \mathbb{P}$) as the period divides $\lambda(\lambda(N))$, which results in short cycles if smooth.
If you wish to calculate any $x_i$ value directly from $x_0$ without first calculating $x_1 \cdots x_{i-1}$, you can use Euler's theorem to do $x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$. Because of $\lambda$, you need to keep $p$ and $q$.
As usual, $\varphi$ refers to the Euler totient function and $\lambda$ refers to the Carmichael totient function.

Note that BBS is not a good CSPRNG. It is interesting from an academic perspective, but it does not provide a practical level of security, especially with realistic modulus sizes. It is also very slow.


Degree of M and Max Sequence Length for LFSR

Let $i+3=j$ so your recurrence becomes $s(j)=s(j-3)+s(j-5)+s(j-7)~mod~2.$ The degree of the corresponding connection polynomial is $7$ and the polynomial itself is $c(x)=1+x^3+x^5+x^7.$ If the polynomial is primitive, then the period of the resulting LFSR sequence with nonzero initial state is $2^7-1=127.$ However this polynomial is not even irreducible since it is $(x+1)(x^6+x^5+x^2+x+1)$ modulo 2. Thus your sequence will not be maximum period. Depending on the initial conditions it will be generated by either $x+1$ or the degree 6 factor. The degree 6 polynomial turns out to be primitive, however.


encrypt message with one digest 0-9 instead of 01-26

Firstly, I presume this is not something you are going to use for protecting data in any kind of real life scenario, but are only asking out of curiosity.

Secondly, just to get the terminology straight and avoid confusion, what gives an OTP cryptographic scheme information theoretic security is that it meets both of the following two criteria:

The key space is exactly as large as the total message space across all messages encrypted. Hence the "One Time" part of the term. The criterion is not that the key is as "long" as each message you encrypt, but both that it is as long as all messages you encrypt combined, and that there are, at each position in your message, at least as many possible key values as there are possible plain text values. Also, when the key is selected, it must be in such way that at each position, no key value at that position is any more or any less probable than any other key value.
When, at each position in your message, you combine a plain text value with a key value to produce a cipher text value, this has to be done using an operation that does not make any cipher text value any more or any less probable, than any other cipher text value. It just happens that a couple of simple operations, such as modular addition or exclusive-or, have this property, provided that the first criterion is already met. Hence, it is not the use of those operations for combining the key with the plain text that makes an OTP into what it is. These operations only happen to be used because they are conveniently simple, provided you already got a key that meets the first criterion.

Consequently, the problem with your proposal is that it doesn't meet the first criterion, that the key space must be as large as the message space. Going with your example, if you are only going to encrypt a four letter string (and only going to do this once), you will get a key space of only  $10^4 = 10000$ keys, but a message space of $26^4 = 456976$ possible plain texts.


Understanding the definition of Schnorrs identification protocol

The difference is the amount of information you have about the structure of the numbers.

Let $e\in_R\mathbb Z_q$. Then you know that the $e$ you have, is a random number from that set. You know no more and no less.

Let $r=g^k$ for some $k\in_R\mathbb Z_q$. Then you know that the $r$ is a random number from the group and you know its discrete logarithm to a pre-defined element. The fact that you randomly picked $k$ doesn't matter, you still know it and can use it in step 3. Even better you know that it is highly unlikely that somebody else will be able to infer $k$ from $r$ (because that is the discrete logarithm problem).

So you see: You know a lot more about $r$ than about $e$ because it was generated in this slightly different way.


Ciphertext and tag size and IV transmission with AES in GCM mode

I'll answer in order:

Output size = input size That's correct, GCM uses CTR internally. It encrypts a counter value for each block, but it only uses as many bits as required from the last block. CTR turns the block cipher into a stream cipher. Note that this doesn't include any additional authenticated data (AAD) that needs to be send, the optional inclusion of the (otherwise required) IV nor size of the required authentication tag.

IV of any size For GCM a 12 byte IV is strongly suggested as other IV lengths will require additional calculations. In principle any IV size can be used as long as the IV doesn't ever repeat. NIST however suggests that only an IV size of 12 bytes needs to be supported by implementations.

How to transport IV Yes, generally the IV is prefixed to the ciphertext or calculated using some kind of nonce on both sides. The size of the IV should be defined by the protocol. If it is possible to synchronize a nonce of 12 bytes then the IV doesn't need to be included with the ciphertext.

Size of authentication tags The calculated tag will always be 16 bytes long, but the leftmost bytes can be used. GCM is defined for the tag sizes 128, 120, 112, 104, or 96, 64 and 32. Note that the security of GCM is strongly dependent on the tag size. You should try and use a tag size of 64 bits at the very minimum, but in general a tag size of the full 128 bits should be preferred.

NIST Special Publication 800-38D (page 8) defining GCM has the following on the tag sizes:

The bit length of the tag, denoted $t$, is a security parameter, as discussed in Appendix B.  In general, $t$ may be any one of the following five values: 128, 120, 112, 104, or 96.  For certain applications, $t$ may be 64 or 32; guidance for the use of these two tag lengths, including requirements on the length of the input data and the lifetime of the key in these cases, is given in Appendix C.


If you have a rule such as "substitute 5 random letters with a fixed symbol" a direct calculation might be possible if you know average word length.

If you can't enumerate all the symbol substitutions into each word via a rule, it will be difficult to calculate directly.

A reasonable way estimate entropy when you can't calculate it is to use data compression. Write a script to output 1 million passwords generated using your method to a text file. Then compress with a high compression, slow algorithm such as LZMA on maximum settings. Perhaps use the 7-zip utility and try all of its available algorithms, picking the smallest result. The size of the resulting file in bits divided by the number of passwords in it should be pretty close to the entropy per password in bits.


Security of AES ECB for 128 bit random data

AES is designed so that it is infeasible to derive the key with only the plaintext and ciphertext. It's part of the definition of a strong cipher.

At the risk of sounding like a broken record, the real problem with ECB is that the same input blocks produce the same output blocks. This is devastating if your data is more than 128 bits. Other modes prevent this by adding in some randomness as well as having previous blocks affecting future blocks.

Another security feature added by some modes is authentication. They provide a way to prove your data came from the place you expect it did, and to prove it wasn't tampered with. Without authentication, attackers could corrupt a single block of your data without you being able to directly tell (barring non cryptographic methods, such as checking if the decrypted data makes sense, but thats a lot less strong).

If all you need is secrecy, and integrity and authentication is of absolutely no concern to your threat model, and you guarantee the same block isn't ever encrypted twice, then encrypting 16 bytes (128 bits) of random data with AES ECB is okay.


Is it possible to choose which point will have the public key of a given Elliptic Curve?

If that were possible, that is, if you could take an x-coordinate, and find the private key $k$ such that $kG$ has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure.

If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log problem", actually, no it doesn't.  There are at most two points that have a specific x-coordinate, and those two points are inverses of each other.  If you known the discrete log of one of the points, you immediately know the discrete log of the other.

As for choosing the most significant digits of the coordinate, I don't know of any easier way that brute force (that is, start at an arbitrary place $kG$ and test $kG, (k+1)G, (k+2)G, ...$ until you stumble across a point that meets the condition.


Vigenere ciphers : Need help for math analysis

First, you decrypt the first four characters. The plaintext you find is the key for the next block of four characters, so after this you can decrypt the next block, finding the key for the block after that, and so on.

This means you will need a case distinction: one case for the first $|K|$  characters (where $|\dots| \stackrel{\text{def}}{=} \text{the length of $\cdots$}$), and one case for the rest of the text. Mathematically, you could write this down as follows:

$$C_i = \begin{cases}i < |K| & M_i + K_i \pmod{26}\\
i \geq |K| & M_i + M_{i - |K|} \pmod{26}\end{cases}$$

For $i<|K|$ we take the standard Vigenère formula. For the rest, you take the ciphertext one keylength back as key. Note that my formula assumes you start with $i=0$; if you start with $i=1$ you'll need $\le$ and $>$ instead.

Then, decryption is done similarly:

$$M_i = \begin{cases}i < |K| & C_i - K_i \pmod{26}\\
i \geq |K| & C_i - M_{i - |K|} \pmod{26}\end{cases}$$


Is there any advantage using this kind of ROM-based randomized hashing in digital signatures?

You are essentially describing a salted hash which is very important for some post-quantum signature schemes. In some lattice-based schemes it is important that the same signing key never be used with the same hash so that some message-replay defence is required. Schemes such as FALCON achieve the anti-replay by salting the message before hashing. Your method is one way in which this could be achieved.


Is Wikipidia wrong about Schnorr Signatures?

The equation in Wikipedia is r = s*G + e*Y, and not r = s*G * e*Y

Thus, r = s*G + e*Y = (k - xe)*G + e*(x*G) = k*G - xe*G + xe*G = k*G


What is the most secure encryption algorithm that keeps the entropy the same or even lowers it?

This seems pretty simple if your 'isEncrypted' distinguisher looks for a cipher text entropy rate in excess of 7 bits byte. But it's not exactly an encryption. Just hex encode it.

All good cipher text is computationally indistinguishable from perfectly pseudo random.  Take the most securely encrypted cipher text from any decent algorithm.  It will be 8 bits/byte if occupying all the bits within a byte.  Then hex encode it to ASCII base 16. You now need two bytes to encode any single original byte of cipher text. Ergo the entropy rate has been halved to only 4 bits/byte and you still maintain maximum security. Your message would of course get correspondingly longer.

In extremis, go to UTF-32 binary encoding which could just be a series of two really funky characters.   Perhaps two Egyptian Hieroglyphs of your choice, each occupying 4 bytes. Mean entropy rate = 0.25 bits/byte.


Can I perform a division of two integers homomorphically using ElGamal?

Let $G$ is a cyclic group with order $q$ and generator $g$.

Let $x$ be Alice's private key. The two messages $c_1$ and $c_2$ are encrypted with the public key of Alice;

$$c_1 = (g^{y_1}, m_1 \cdot g^{x y_1})$$

$$c_2 = (g^{y_2}, m_2 \cdot g^{x y_2})$$

Now to calculate $m_1/m_2$ in the encrypted values, calculate the inverse of $g^{y_2}$ and $m_2 \cdot g^{x y_2}$ in the group

$$ c_2'=\Big((g^{y_2})^{-1},(m_2 \cdot g^{x y_2} )^{-1}\Big) = (g^{-y_2},m_2^{-1} \cdot g^{-x y_2})$$

then multiply,

$$c_1  c_2' = (g^{y_1}  g^{-y_2}, \;\; m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2})$$

Now, check the decryption.

$$s = (g^{y_1} g^{-y_2})^x = g^{x y_1 }  g^{-x y_2 } $$

$$s^{-1} =  g^{-x y_1 } \cdot g^{x y_2 } $$

$$ s^{-1} \cdot m_1 m_2^{-1} \cdot g^{x y_1} g^{- x y_2} =  m_1  m_2^{-1}  \cdot g^{-x y_1 }g^{x y_1}\cdot  g^{x y_2 } g^{- x y_2} = m_1  m_2^{-1}$$

Note: based on comments of Geoffroy and Mikeazo.


Why is the nonlinearity of this Boolean function evaluating to $\frac12$?

In this formulation you need to convert your function's output range to $\{-1,+1\}$ via $$f`(x)=(-1)^{f(x)}$$ and apply the Walsh Hadamard to the new function $f`(x)$. Using the zero one formulation means you are off by a constant depending on the number of variables since
$$
(-1)^u=1-2u
$$
for $u\in \{0,1\}.$
See my answer below on Boolean functions and crypto, it may be useful given your recent questions.
How are boolean functions used in cryptography?


Cipher suites: same name, different IDs, why?

These numbers belong to ElasticSearch;

TLS_ECDH_ECDSA_WITH_NULL_SHA is 0x0047
TLS_ECDH_ECDSA_WITH_RC4_128_SHA is 0x0048
SSL_RSA_FIPS_WITH_DES_CBC_SHA is 0xFEFE
SSL_RSA_FIPS_WITH_3DES_EDE_CBC_SHA is 0xFEFF

and 0x0047 has almost 0% at tlsfingerprint.io
The second numbers in SSL/TLS in this format {0xC0,0x01},{0xC0,0x01},{0xFF,0xE1},{0xFF,0xE0}. The first two in rfc4492. These are deprecated in rfc8422. The last two is for private usage.
The implementations can have different control by the maintainers, therefore it is good to have different numbers. It is bad that your original source doesn't list where they took the numbers.

Note: in TLS 1.3, there are only 5 cipher suites with their id's;

{0x13,0x01} - TLS_AES_256_GCM_SHA384
{0x13,0x02} - TLS_CHACHA20_POLY1305_SHA256
{0x13,0x03} - TLS_AES_128_GCM_SHA256
{0x13,0x04} - TLS_AES_128_CCM_8_SHA256
{0x13,0x05} - TLS_AES_128_CCM_SHA256


Signature to prove of ownership of arbitrary sized data

Proofs of Storage (PoS) are challenge-response protocols that allow a client to verify that a server is truthfully storing a file. See this paper from Ateniese, Kamara and Katz for an example of PoS.

The basic idea is explained in this quote from that paper:

  Viewing the file $\vec f$ as an $n$-dimensional vector, the client
  begins by tagging each element of $\vec f$ and then sending both $\vec f$ and the vector of tags $\vec t$ to the server. To verify that the
  server is storing the entire file, the client sends a random challenge
  vector $\vec c$ and  the server returns $\mu =\sum_i c_i f_i$ along
  with a tag $\tau$, computed using $\vec f$,$\vec t$, and $\vec c$,
  which is supposed to authenticate this value.

The key aspect here is defining

how the client (or more correctly, the one who uploads the file) create tags $\vec t$,
how the server computes response tag $\tau$,
(and perhaps more importantly), how the server's response can be verified publicly.

I don't have time at the moment to explain the details of these aspects (they are a little bit complicated...I will try to do it later). In any case, it is important to remark that in order to verify a response in the proposal of Ateniese, Kamara and Katz, one does not need the original file. This is a public-key setting, and the private key is only used for tagging the file at the beginning. After that, everything is done using the public key (both the proof of storage and its verification).

There are similar proposals, such as Proofs of Retrievability (PoR) and Provable Data Possession (PDP).


Do probabilistic one-way functions imply deterministic one-way functions?

Let's look at the definition in the linked thesis:

Definition 2.2.2 (probabilistic one-way function). A probabilistic function, $F$ (with randomness domain $R_n$), with a corresponding deterministic verifier, $V_F$ , is called one-way with respect to a well-spread distribution, $\mathbb{X}$, if for any PPT, $A$:
$$\Pr\bigl[x \gets X_n, r \gets R_n, V_F\bigl(A(F(x, r)), F(x, r)\bigr) = 1\bigr] < \mu(n).¹$$
$F$ is called one-way if it is one-way with respect to the uniform distribution.

I will assume, since you did not specify anything about the distribution, that we are looking at the uniform distribution.
This definition is a bit problematic since it does not contain any kind of correctness guarantee for the verifier. In particular, take any function $F$ and define $V_F$ to be the constant $0$ function. According to the definition above the pair $(F,V_F)$ is one-way. Clearly this is not what was meant.
Definition 2.5.1 defines efficient verifiability, though this definition doesn't quite fit for a one-way function as defined above since it talks about an ensemble of keyed functions. However, in the same spirit, I will assume that Definition 2.2.2 meant to require the following from $F$:

Definition (Effcient Verification). A function, $F$ satisfies efficient verification if there exists a deterministic polynomial time algorithm, $V_F$, such that:
$$\forall x \in X_n, r \in R_n, V_F(x, F(x, r)) = 1.$$

If that is the case then the following holds.
Theorem Let $F : X_n \to Y_n$ be a probabilistic one-way function with randomness domain $R_n$. Then the deterministic function $G : X_n \times R_n \to Y_n$ defined as $G(x,r)=F(x,r)$ is a deterministic one-way function.
Proof. Let $A$ denote an arbitrary PPT algorithm such that $$\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)] =\epsilon(n).$$
Note, that since the distribution over $X_n$ is uniform it holds that
\begin{align}
\epsilon(n) = &\Pr[(x,r) \gets X_n\times R_n, G(A(G(x,r))) = G(x,r)]\\
=&\Pr[x \gets X_n, r\gets R_n, G(A(G(x,r))) = G(x,r)]\\
=&\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]
\end{align}
where the last equality follows by the definition of $G$.
Now, consider the PPT algorithm $B$ that upon input $y$, executes $(x',r')\gets A(y)$ and outputs $x'$. By the definition of efficient verifiability, for all $x,x'\in X_n$, $r',r \in R_n$ it must hold that $$F(x',r') = F(x,r) \implies V_F(x',F(x,r))=1.$$
Thus,
\begin{align}
\epsilon(n) = &\Pr[x \gets X_n, r\gets R_n, F(A(F(x,r))) = F(x,r)]\\
\leq & \Pr[x \gets X_n, r\gets R_n, V_F(B(F(x,r)),F(x,r))=1] \leq \mu(n),
\end{align}
where the last inequality follows from the assumption that $F$ is a probabilistic one-way function.
Since the above holds for arbitrary PPT $A$, the theorem statement follows. $\quad\quad\Box$

¹Where $\mu$ denotes an unspecified negligible function.


What are the contents of a certificate and how can I view it?

HTTPS/TLS uses X.509 certificates generally. There is more detail here in the latest TLS specification.
You can view HTTPS certificates in a browser.
As per Wikipedia:
The structure of an X.509 v3 digital certificate is as follows:
Certificate

Version Number
Serial Number
Signature Algorithm ID
Issuer Name
Validity period

Not Before
Not After

Subject name
Subject Public Key Info

Public Key Algorithm
Subject Public Key

Issuer Unique Identifier (optional)
Subject Unique Identifier (optional)
Extensions (optional)

Certificate Signature Algorithm
Certificate Signature


What is the difference between exhaustive search and factorization in relationship to determining a key?

Your summary of exhaustive search is essentially correct; the attacker just tries every possible key until he finds one that works.  This works against almost any cryptosystem (exceptions: OTP, secret sharing, quantuum cryptography).  It's not practical against any modern system (mostly because 'has a key too large to be brute forced' is an essential attribute of any modern system).

Factorization is not a generic attack; instead, it is attack on certain public key crypto systems (mainly RSA).  With RSA, the public key contains a composite number; if someone where again to derive its factorization, they could reconstruct the private key.  That is, if someone could factor, they could break RSA.  However, a breakthough in factorization would affect only RSA (and a handful of other systems that are not used much in practice); there is no known way to use factorization to attack (say) AES, SHA-2 or Elliptic Curve Cryptography.


It is not possible:

Let $d_A, d_B$ be distinct private keys. Then

$$
  s=k^{-1}(z+rd_A)=k^{-1}((z+r\;(d_A-d_B)) + rd_B)
$$

So the pair $(r, s)$ is not only a valid signature for the public key $d_AG$ and the (partial) hash $z$, but also for the public key $d_BG$ and the message hash $z+r\,(d_A-d_B) \pmod n$.

So in many cases (if there are no restrictions on valid values for $z$), every valid signature $(r, s)$ ("valid" for some public key) and every public key $d_AG$ there will be a message $M$ such that $(r, s)$ is a signature for $M$ under $d_AG$.


Analysing communication complexity of a protocol

(Revised based on poncho's comment.)

If p is of 120-bit length, then any field element should better be sent with 120 bits. If you want to send, say 1, with a 1-bit message, then this reveals the element's length and adds the computation complexity of constructing variable-length messages for different elements. Besides, only half of the field elements may have leading 0s, so sending messages with variable lengths does not save much communication bits.

As for the communication complexity, it depends on what message you are sending and may not be linear to the field size.


Can public key be recovered from ciphertext & encrypted private key?

Are there fallacies in above argumentation and is it a reasonable scheme?

It's not unheard of to encrypt secrets for them to be decrypted by a HSM or smart card. Usually though the smart card or HSM itself is used to encrypt/decrypt stored secret values. I know that at least one HSM does this, and all TPM's out there.

If you are accepting an unlimited number of secrets, then you seem to be generating an unlimited amount of key pairs. If any combination of public/private key pair is accepted then you may as well always use the same public key/private key pair.

As a side note it's strange to talk about a secret being 512 characters. That doesn't mean anything in cryptography (unless you mean C/C++ char values that essentially translate to bytes).

Can a public key be derived from ciphertext & encrypted secret key?

No, not if the encrypted secret key is presented as raw key material. Both outputs should be (almost) indistinguishable from random.

What you are trying to accomplish should be possible without a secret public key. Using cryptography outside its bounds is dangerous and should be avoided.

Can a public key be derived from ciphertext & decrypted private key?

Yes, almost certainly, unless the public exponent has the same properties as the private exponent. The modulus will be known so it is required to keep the public exponent safe. Most private key containers will contain CRT parameters and/or the public exponent. Furthermore, the exponent of the public key is often a known value such as 3 or the fourth number of Fermat (65537).

Or am I unnecessary complicating things, and should simply encrypt the shared secret with a smart card and that's it?!

Yes. That seems at least more reasonable than the scheme you've described above.

Even if the scheme is not directly wrong, it contains too many assumptions and leaves too many things not well described. It's unlikely that a direct implementation will be secure.


Is this the correct procedure for cycle walking using an FPE?

Yes, what you're describing is the correct way to cycle walk with FPE.

In your case, the value you're encrypting is ten bits, so the largest possible ciphertext is 1024. You'll only need to cycle walk if the ciphertext is from 1000-1024, so 24 of the possible 1024 values will cause an iteration. This means your probability of cycle walking for any particular value is $\frac{24}{1024} \approx \frac{1}{40}$, which is pretty small.


OpenSSL - What Data Is Used To Create A Certificate's Digital Signature?

This applies over the entire certificate data. Per RFC 5280, section 4.1.1.3:

   The signatureValue field contains a digital signature computed upon
   the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
   tbsCertificate is used as the input to the signature function.  This
   signature value is encoded as a BIT STRING and included in the
   signature field.  The details of this process are specified for each
   of the algorithms listed in [RFC3279], [RFC4055], and [RFC4491].

   By generating this signature, a CA certifies the validity of the
   information in the tbsCertificate field.  In particular, the CA
   certifies the binding between the public key material and the subject
   of the certificate.

So every single field of the certificate is part of the signature (except of course for the signature). This is to guarantee that no element of it was tampered with (there is pretty much no field in the certificate that is not important. Even if one were, it's easier to require everything to be signed regardless of the use).

About public keys:

subject public key is definitely included. Note the last sentence I quoted. This is one of the critical parts of the certificate: who it was issued to.
issuer public key is not included in the certificate and therefore is not part of the signature. Instead, the subject field of the issuer is included as well as the Certificate Authority Key ID which can be found in the issuer's certificate under Subject Key ID. This is used in path building.


Is there any benefit to using a randomly chosen replacement strategy on a string before or after encrypting it?

"However, I'm not sure if this provides any real value as if the IV/Key has already been obtained then how hard is it really to figure out what I'm doing with the appended integer?"

If the adversary has your key, then you have already lost, and there is little that can be done besides generating a new one and keeping it safe. The IV is considered public information and does not need to be kept secret, and does not need measures applied to attempt to keep it secret.

Would it be better to use this post-encryption?

No, it would not improve anything to use this transformation after application of the AES.

I'm really curious what the community thinks of this idea. Does it have any merits?

The internals of a cipher often permute or shuffle the data somehow, in addition to the substitutions they usually do. That itself is a good idea.

You basically are suggesting a simple substitution. Substitution is an important part of an substitution permutation network. Combinations of substitutions and permutations (shuffles), combined with key interaction, can indeed make a strong cipher. The AES is built off of these principles.

The exact transformation that you mention is not particularly novel or capable. Typically the substitution layer is performed via the application of an S-Box, which is very fast, or in situations where resistance to timing attacks is desired, some kind of non linear function that operates in constant time

 What are the drawbacks? How good/bad of an idea is it really?

However, your substitution is totally unnecessary if you are going to be encrypting with AES. The AES is by itself, already secure. Your modification would not improve this fact.

Worst case scenario, your modification could somehow open up a weakness that you had not considered. For example, what key were you planning on using to apply your substitution? Rarely do ciphers use the master key directly in their operations, usually they apply a key schedule first, as this can create a layer of separation between the "real" key and the round key used to actually do the work. Your transformation, considered in isolation, appears to be weak to known plaintext attack that could lead to key recovery.

Long story short, some form of substitution isn't just a good idea for a cipher, it's necessary. However, the AES was literally designed for this purpose, and does a good enough job already.


The video (at least, where the question links) illustrates the Baby-step/Giant-step Discrete Logarithm method in the multiplicative group modulo $p$, for prime $p$. That is the set $\{1,2,\ldots,p-2,p-1\}$, under the internal operation multiplication modulo $p$.
This group has essentially nothing to do with an Elliptic Curve group. The principle of Baby-step/Giant-step is the same regardless of group, however the operation analog to multiplication modulo $p$ is extremely different in an Elliptic Curve group.

It is important for security that the order of the group generated by $g$ (that is, the number of distinct values $g^x\bmod p$ can take) is prime, or at least has a large prime factor. When working in the multiplicative group modulo $p$, the order of the full group is $p-1$, and the order of $g$ is some divisor of that. One option is to choose $p$ such that $(p-1)/2$ is prime ($p$ is a so-called safe prime). Now we can take any $g$ except $g=1$ and $g=p-1$, and it's order will be $p-1$ or $(p-1)/2$, which both have a large prime factor $(p-1)/2$.
There is no imperious reason to choose a generator $g$ that is prime. It happens that $2$ and $3$ are popular, and prime; and some people have found satisfactory to choose $g$ prime.
There's even less reason to worry about prime $g$ in ECC groups. In secp256k1, both the $x$ and $y$ coordinates of the generator point are large even integers, thus not prime. What matters is the order of the group generated by $g$. That is noted $n$, and the curve parameters are usually chosen such that $n$ is prime.


What you are describing sounds something like a Merkle Tree:
https://en.m.wikipedia.org/wiki/Merkle_tree

Note that the organization of a Merkle tree is fairly arbitrary; the graph can look like just about anything so long as it is acyclic.

The interesting aspect of a Merkle tree is that any change anywhere in the data "bubbles up" the tree to the root, changing the hash value stored there. But there is no requirement to re-hash all of the data in the tree on every change.


Why pairing based crypto is suitable for some particular cryptographic primitives?

Crypto based on cyclic groups is (at a very high level) about "hiding" things "in the exponent" and then manipulating those values as they live in the exponent. As an example, in a cyclic group $\langle g\rangle$, you can "hide" a random value $x$ as $g^x$.

Without a bilinear pairing, all you can really do "in the exponent" are linear/affine (degree-1) combinations of these hidden values. That is, given $g^{x_1}, \ldots, g^{x_n}$, you can obtain $g^{a_0 + a_1 x_1 + \cdots + a_n x_n}$ for known coefficients $a_i$.

With a bilinear pairing, you can do degree-2 combinations. This is huge, it allows you to "multiply hidden values together in the exponent". This extra expressivity is what lends itself to a wider variety of cryptographic primitives, like identity-based and functional encryption, etc.

There are other tools like lattices that also have a lot of algebraic structure. The capabilities of lattices are somewhat incomparable to those of groups with bilinear pairings. But more of these "functional encryption" applications are now being achieved using lattices as well. So none of these applications are probably unique to bilinear pairings, it is a bit of a historical accident that we have seen an explosion in techniques and applications of bilinear pairings.


Subgroup generation: should we check that order is not 2? or g in not too small?

Assuming you have the same setting as the linked question (in particular $q$ is prime, it's true: you cannot have $g^2 = 1\bmod p$ and $g^q = 1\bmod p$ simultaneously unless $g=1$ or $q=2$.

It's important to notice that if the condition $g^q = 1\bmod p$ is satisfied and $g$ is not the identity, then $g$ will be a generator.

I think that what PulpSpy means in the answer you linked is that either you're lucky and $g^q = 1\bmod p$, with $g$ not the identity, or you're not lucky and $g^2 = 1\bmod p$ (not both congruences simultaneously), in which case you have to try again with another $g$.


Why is the P-521 elliptic curve not in Suite B if AES-256 is?

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported.

  "In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) showed that there were very few implemented AES-192, whence the decision to go with AES-128 and AES-256 in Suite B, paired with P256 and P384.   All of the crypt purists grumbled endlessly about the mismatch betwixt AES-256 and P384."

  -- Kevin M. Igoe, NSA

(I am choosing to take his explanation at face value, but you never know with intelligence agencies.)


Can I achieve data authentication with ChaCha20 without MAC?

You're in luck!  According to your question, you have 64 bytes of bandwidth per 32-byte message available.  The authenticated cipher crypto_secretbox_xsalsa20poly1305 has a ciphertext expansion of only 16 bytes—that is, the ciphertext is only 16 bytes longer than its plaintext, no matter how long the plaintext is, so in this case it will use only 48 bytes and leave you 16 bytes under budget!

Just use crypto_secretbox_xsalsa20poly1305 for each 32-byte message before you act on it—if you use NaCl/libsodium, you won't even be allowed to get at the decrypted plaintext if it's a forgery—and you'll be good to go.

If you already have a message sequence number, use that as the crypto_secretbox_xsalsa20poly1305 nonce; if not, you can use 8 of the remaining 16 bytes available to you for a message sequence number.  If you ever repeat a nonce with the same key, the security vanishes.

No need to worry about stream ciphers (which can fail to protect confidentiality if you act on forged messages), MACs (which don't protect confidentiality at all), HMACs (which are a specific kind of MAC), etc.  Focus on authenticated ciphers like crypto_secretbox_xsalsa20poly1305 or AES-GCM.


Breaking a small-scale Example Diffie-Hellman?

Actually, given $p,g,g^x\bmod p,g^y\bmod p$ deciding whether a given number is actually $g^{xy}\bmod p$ is also known as the Decisional Diffie-Hellman Problem (DDH), which sits at the basis of the (formal) security for the ElGamal cryptosystem and is assumed to be hard for properly chosen values of $p,g$ and $x,y$ in general.

For your particular scenario the best solution is to "just" solve the discrete logarithm problem, ie computing $x$ or $y$ and then computing $g^{xy}\bmod p$ to see which number falls out (113).


The Hill Cipher as one of the classical cipher is invented by Lester S. Hill in 1929. It is the first polygraphic cipher that can operate more than one letter at a time.

There is a rule for key K:  Determinant of matrix and number of characters of the alphabet must be coprime. What does this rule say? Why
it must be like this? So If I had determinant 5 and characters 30, it
would not work?

In the Hill cipher, there is an invertible matrix for the key $K$ of size $n\times n$, and the plaintexts $m_i$'s are row vectors of size $n$.
The encryption of a block $m$ is performed by $c = m K$ and the encryption of the message can be considered mathematically take $c = m K$. For decryption, multiply both sides with $K^{-1}$ and get $cK^{-1} = m K K^{-1}$ and $cK^{-1} = m I$. That is the inverse of a matrix and it is a well-known property that to be invertible a matrix must have of square size and have a non-zero determinant.
If the determinant has common factors with the alphabet size then it will not have inverse since invertible matrixes must have invertible determinants. This is due to fact that we are in the composite modulus. In this case, choose a new uniform random key or choose a prime alphabet.

Let's assume I have key K which should be 3x3. I would get the key: ENCRYPT. I would create trigrams like ENC RYP T?? - now the last
trigraph is missing two characters. Should this input key be REFUSED
by application for example or should I fill it with some values like
#?(# alphabet must contain this char). Or how should the application behave when this happens?
Let's assume I have plain text T which is: textabcd - again the same question (as 2.). I have TEX TAB CD? - (should I again insert
something in that empty space (?) (for instance #) ?

In modern Cryptography, we call it padding and the classical era has padding also. I'm not aware that Hill proposed any padding.
Fixed padding can cause serious problems with the Hill cipher since it hasn't got known-plaintext attack security. Putting X or any fixed character can cause information leak about the key.
Wikipedia states it very well. The messages are starting end ending with predictable ways, like my dear ambassador, Weather report, Sincerely your From .. To in the military, etc. Context can change according to the target. Therefore we need randomized padding in the beginning and at the end. This can cause confusion, too. The better one may use nonsense letters for this aim.

Should HILL cipher accept MATRICES (input as matrices) or as alphabet key like ABCD?

If I've understood this part correctly; first, the messages are encoded into row vectors of numbers by using the alphabet then multiplied with the key matrix $K$. The key matrix is also a number matrix, not a character. We operate on the numbers then decode the information back to character.

Little proof of the claim that the determinant must have relatively prime to $n$. When $n$ is a prime it is clear that we are in a field and the determinant must be non-zero by the Invertible Matrix Theorem
The theorem also gives the general case for this as;

In general, a square matrix over a commutative ring is invertible if and only if its determinant is a unit in that ring.

The units are invertible elements. For a given $u$, if $\gcd(u,n)=1$ then it has an inverse, therefore it is a unit. The converse is also true that for a given unit the $\gcd(u,n)=1$ must hold. We can see it form that $u x \equiv 1 \pmod n$ then we can form the bezout's identity $ux+bn=1$ then we can conclude that they are relatively prime.
Or directly; if $ax\equiv 1 \pmod n$, then there is a $k$ such that $ax=bk+1$, equivalently $ax−bz=1.$ If $d=\gcd(a,b)$, then $d|a$ and $d|b$, so $d|ax−bz=1$. We can conclude that $d=1$.


Security of Randomized Encryption Scheme

Ciphertext Indistinguishability means that if you encrypt a message many times, each time the ciphertexts must be different.

For example, think about a device that searches flaws in a dam. Every time, when this device traverses, it will send "Yes" or "No" signals that it means for a receiver that the device has found a flaw or not. If an eavesdropper sniffs these signals, because of the number of "no" signals are more Than "yes" signals, he could understand the meaning of these signals even though they are encrypted and could not break their encryption. This weakness happens because the encryption algorithm is DETERMINISTIC and it means that always it produces same encryptions for "YES" signal and same encryptions for "NO" signals, in other words, the attacker could distinguish these encrypted messages without knowing the nature of the encryptions.

The solution for making messages resistance against distinguishability is using Non-Deterministic encryption and use parameters like IV and so for make ciphertext Random and each time giving the same message, it produces different ciphertexts and the attacker could not distinguish them.


Is it possible to decrypt double-key crypted file knowing public key and a having one or more original files?

Short answer: No.

Public Key Encryption Basics

In public key encryption, public key is used to encrypt and private key is used to decrypt. It is not possible to decrypt using public key. It is also not possible to use public key to find private key.
The opposite is commonly true: if you have private key, you likely can easily derive matching public key.

Using two versions of one file, crypted and decrypted, it may be possible to derive the public key. However, again, it will not be possible to use that for deriving the private key.

Implementation issues

The security properties you asked about are generally provided by public key cryptography. However, given the fact that it is not known what program was used and what key length + what padding, so the answer is based on assumption of ideally implemented public key cryptography.

In theory the files will be safe (i.e. undecryptable) from parties without access to the private key. In practice, theory is not neccessarily accurate.


Do Quantum Key Distribution and Physical Unclonable Functions combine, and how?

It seems difficult to combine the two. PUFs can provide authentication but they are based on the sender having first built up a small number of challenge/response pairs before handing the PUF over. So if Alice gives the PUF to Bob, Alice can authenticate Bob with the response. However if the protocol is two-phased, where Alice authenticates Bob and then they do QKD, the MITM will just jump in at the second phase. So the idea is that PUF-based authentication needs to be binded to the key generated during QKD.

For example, Alice and Bob could perform QKD but treat the output as a challenge, and the response from the PUF is their shared secret key. Unfortunately, the number of possible outputs is too large for building up a set of challenge/response pairs. Without jumping into using classical cryptography, I don't see a way that the addition of a PUF could be useful.


Digital Signatures, Standard Hash Functions and MACs

Digital Signatures, hashes and MACs can do similar jobs.  They allow someone sending a message to a check value along with the message.  They allow someone receiving the message to verify that the message corresponds to the check value.  However, a hash is an unkeyed operation; anyone can compute the hash of the message.  So, while they provide protection against accidental message modification, they cannot provide any protection from an active attacker.

Digital signatures and MACs both ensure that someone in the middle (without the key) cannot modify a message without being detected (by the check value not validating).

However, even here still a difference; with a MAC, the sender and the receiver have the same key.  So, someone in the middle (without the key) cannot forge a message; however, the receiver can himself generate a message that validates.

With a digital signature, this is not the case.  The sender has a 'signing' key, and the receiver has a 'verification' key; the verification key allows the receiver to validate messages; however, he himself cannot forge any messages.

So, if the question is "should I use a HASH, a MAC (such as HMAC), or a digital signature", well, that depends on how much you trust anyone who does the validation.  If you just want to protect accidental changes to the message, well, a hash is fine (and doesn't force you to do the bother of key management).  If what you need is to protect messages from Alice to Bob (and so Bob is the only person who will ever validate a message with that key), then a MAC is appropriate (and a lot cheaper).  On the other hand, if you are posting messages to your blog, and you want everyone to be able to verify that you are the one posting, well, everyone will need the verification key, and so in that case, a digital signature is required.


Construct an encryption algorithm using hash function

Theoretically, there are several ways to turn a hash function into an encryption system. However, the Devil is in the details. A cryptographic hash function is a function which is resistant to preimages, second preimages, and collisions. As far as I know, it has not been proven that these conditions are sufficient to build a stream cipher. In fact, what we want is a random oracle (there are subtleties with regards to definition, that I will not detail here).

We have no proof that cryptographic functions really exist. We also have no proof that random oracles really exist. And we do not know how to build a random oracle out of a cryptographic hash function. We do know how to build a secure hash function out of a random oracle. However, we also have strong indications that random oracles cannot actually exist, at least in a general sense. Basically we grope in the dark: we have candidates like SHA-256, which appear to be "quite strong" as hash function, and also are reasonably oraclish as far as we known. In fact, the length extension attack is proof enough that SHA-256 is not a random oracle, but this can be fixed by using SHA-256 on fixed-length inputs, or by invoking it as part of more convoluted structures like HMAC.

In any case, if you have a hash-function-with-oracle-powers, then it is rather easy to generate a pseudo random stream from a secret key, by hashing K||n where K is the secret key and n is a counter. By XORing this key-dependent pseudo-random stream with the data to encrypt, you have a stream cipher.

To make a block cipher, you can use a Feistel network where your hash function is used as "confusion function" for each round, although there again there are details (you must inject round subkeys at that point). The theoretical analysis is due to Luby and Rackoff, back in the 1980s. It can be proven that four rounds are sufficient, subject to some details; e.g. if you are targeting $n$-bit blocks, the proof works up to security level $2^{n/2}$ or so (if I remember it correctly). Variants imply unbalanced networks, which allow for better security at the expense of more rounds (see the Thorp shuffle).

Theoretical upper limit for Feistel schemes is that such a scheme is necessarily an even permutation, so if you have $n$-bit blocks and know the encryption of $2^n-2$ distinct plaintexts, you can guess the encryption of the two plaintext blocks that you don't know with probability $1$, instead of probability $0.5$ for a truly pseudorandom permutation. You would be very hard-pressed to find a practical situation where this point actually matters in any way.

Another theoretical method which does not involve a Feistel scheme at all is described in that article: it is a generic method to turn a "seekable pseudorandom stream" (e.g. the hash-based stream cipher alluded to above) into a generic pseudo-random permutation. The implementation overhead is huge, so nobody does that in practice. It still shows that a PRP can be generically built out of a PRF without the (slight) limitations implied by Feistel networks.


What is the most an adversary can do in the context of public key masquerading?

Perhaps the situation should be concretized a little.

A and B both have a public/private key pair:

Does A already know $P_B$, and vice versa? If not, then $C$ can send to A the $P_C$ saying it's «$P_B$» (similar for B, $P_C$ substitutes $P_A$), and become a typical man-in-the-middle, being able to, for example, remove any «real» message from B to A (something he can perform without keys at all) and decrypt or even modify everything that A sends to «B».

but not more since not being in possession of B's secret key C cannot retrieve the message from A.

Hypothetically, if A is «naive» enough (may A be a machine, for instance?), C sends him the message like «stop using my public key $P_B$, instead use $P_C$» (encrypted with $P_A$), A decrypts it with $S_A$, believes without approvals, switches to $P_C$, and then C becomes a man-in-the-middle again.

Does A know $S_B$? Obviously, he must not; otherwise, using the preceding trick, C may convince A to share $S_B$, and impersonate B elsewhere.

In general, the «exploitability» here depends not only on the cleverness of C, but on the «naivety» of A and B as well (they have to know what's dangerous and don't do it).

do from this point with retrieving the secret key of B?

Didn't you mean without retrieving?

Sorry if this looks like a comment. In case you consider a man-in-the-middle attack to be «the most an adversary can do» (or at least critical), it probably helps to concretize the picture. Also, although it is stated that

assume there is no authentication employed

to avoid man-in-the-middle attack is a kind of authentication, in itself.

When the situation is clarified, other answers will be much more useful, and this one may be deleted.


In few words:

OTP has perfect secrecy;
For a cipher to have perfect secrecy, it is required that $|K| \ge|M|$.

Let $K=M=C=\{0,1\}^n$ be the set of keys, messages and ciphertexts. If you apply the "improvement", ie, if you remove $0^n$ from the keyspace, then you've created a cipher that cannot show perfect secrecy (because now $|K| = |M| - 1 < |M|$).

Therefore, the "improvement" completely breaks perfect secrecy, which makes this modified OTP worse than the original.

In many more words, with illustrating examples.

As you should know, the one-time pad has the perfect secrecy property, which is defined as follows: let $M,C,K$ be the sets of messages, ciphertexts and keys; $\forall k \in K, \forall c \in C, \forall m \in M: P[E(k,m)=c] = P[k \,\,xor\,\,m = c] = \alpha$, for some (tiny) positive real number $\alpha$.

In words, you have absolutely no information about the original message if you're given only the ciphertext. Suppose the cipher text reads:

The password of my bank account is my wife's birthday

What's the most probable original message?

The password of my bank account is my wife's birthday
The password of my bank account is my aunt's birthday
The password of my bank account is: b4nk-P4ssw0rd1234
Love of my life you've hurt me You've broken my heart

See? The "improvement" can't possibly improve this cipher. Actually, it makes it worse: by reading the ciphertext, the attacker can be sure that your password is anything but your wife's birthday -- he could get some information from the ciphertext!!!


Is there any alternative for extended euclidean algorithm to perform modulo division?

For increasing speed, you should use of  "Barrett reduction" and "Montgomery multiplication". For more detail you can see "Guide to Elliptic Curve Cryptography". Also you can use "MAGMA". This program is  one of the best and fastest program for elliptic curve.


In a better world, TLS_FALLBACK_SCSV would not be necessary: SSL has been supporting downgrade-proof version negotiation since at least SSL 3.0, so a man in the middle should never be able to limit a connection to a version older than the mutually supported maximum.

However, out there are some broken servers that don't really support that kind of version negotiation; simply receiving an unknown, i.e. newer, version number, or unknown TLS extensions in a ClientHello causes them to crash. (Compliant servers would not crash, but simply tell the client that they want to use a lower version of the protocol; the connection would be established using the highest mutually supported version.)

Ideally, clients would simply refuse to connect to such broken servers; the problem would be swiftly fixed by the server vendor, and proper version negotiation would be restored.

As it turns out, quite a lot of server vendors or administrators couldn't be bothered to do that. Many browsers will now try to fix the problem on their end by connecting using a "legacy" ClientHello that doesn't trigger the buggy server behavior, which is essentially a second connection attempt using only SSL 3.0.

Unfortunately, this opens up an attack possibility for a man in the middle: By simply suppressing client connection attempts using new TLS versions to the server and simulating a buggy server response to the client, they force an SSL 3.0 connection attempt; the connection using SSL 3.0 will eventually be established, with the server thinking that the client uses a really old SSL library, and the client thinking that it is talking to a buggy SSL-3.0-only server.

Essentially, TLS_FALLBACK_SCSV allows clients to send a hidden version number in the downgraded connection attempt in a way that doesn't trigger the server bugs.

Informally, the conveyed message might be interpreted as follows:

  Hey Server, even though I only claim to support TLS version $x$ in the version header, I actually support TLS versions up to $y$. If you support anything better than $x$, this means that there is something sinister going on here!

Practically, the backwards-compatible signal is a special "dummy" cipher suite that will be ignored by servers not supporting fallback prevention (whether they are broken SSL 3.0 or fairly recent TLS 1.2 servers).

Only servers supporting the draft specification will be able to interpret the signal and act accordingly; older servers will simply think that the client supports some additional cipher suites that they don't know about, and will continue the handshake as usual.


The key to a mono-alphabetic substitution cipher is a substitution table. Thus you already have (most of) the key for that cipher, it is

a   b   c   d   e   f   g   h   i   j
?   D   E   F   G   H   I   ?   K   L

k   l   m   n   o   p   q   r   s   t
M   N   O   P   Q   R   S   B   T   U

u   v   w   x   y   z
V   W   X   Y   C   ?

where the question marks are unknown parts.

Often instead of defining the table manually, some simple generation algorithm is specified, such as “Shift all characters by $n$ positions to the right”. But not every substitution table can be produced in a simple way.

However, in your case, a simple algorithm would be (assuming a $\rightarrow$ A, h $\rightarrow$ J, z $\rightarrow$ Z):

Write the ciphertext alphabet A … Z in the first row and below write the corresponding plaintext characters, that is "a, r, y" and then the remaining ones in alphabetical order:

A  B  C  D  E  F  G  H ...
a  r  y  b  c  d  e  f ...

So in some way, you can consider "ary" to be the key but knowledge of the algorithm is also required.


Why do we need to use supersingular curve on SIDH?

There's many different answers to this question, depending on what you mean by "why".

You can't replace supersingular with ordinary and still have SIDH. Supersingular isogeny graphs are regular graphs ((ℓ+1)-regular for the graph of isogenies of degree ℓ). Ordinary isogeny graphs are not in general, so SIDH simply would not work with them.
There is an older key-exchange protocol, proposed independently by Couveignes and Rostovtsev-Stolbunov, which uses ordinary graphs (we'll call CRS this protocol). It is similar to SIDH, but not the same. It is vulnerable to a sub-exponential attack by Childs-Jao-Soukharev, so its quantum security is hard to assess, although the system is not considered completely broken. At security levels that could be considered equivalent to SIDH, CRS is much slower (absolutely impractical).
Recently, Castryck, Lange, Martindale, Panny and Renes introduced CSIDH, which is really the CRS system, where you replace the word "ordinary" with "supersingular", and do some optimizations. CSIDH is much faster than CRS, although slower than SIDH. CSIDH is still vulnerable to the Childs-Jao-Soukharev attack, so its parameters scale worse than SIDH.
CSIDH highlights one of the main reasons we use supersingular curves: it is easy to control their group structure, which in turns makes it easy to have rational torsion points, which allows us to apply Vélu's formulas, which are much more efficient than generic isogeny-computation algorithms.
Finally, going back to SIDH, the Childs-Jao-Soukharev attack does not apply to it. Why? Because the endomorphism ring of supersingular curves is larger (and non-commutative). The Childs-Jao-Soukharev attack requires expressing the isogeny computation problem as an (abelian) hidden shift problem. In the SIDH case, there is no known hidden shift structure. The net effect is that SIDH parameters scale better as security grows.


Are passwords generated from sine vulnerable to certain attacks?

If someone knows your password creation method, the only hope you have of foiling an attack is if the method has a lot of entropy - roughly, if there are a lot of different passwords you could have with that method (it's not quite the same if some passwords are more likely than others, but it's a good heuristic). If the method is "sine of an integral number of degrees to some precision," this is a fairly weak method. Assuming it's in a base between 2 and 36 (i.e. 0-9 and a-z), and that you only use an integer number of degrees (which means an attacker need only consider integers between -90 and 90), and that the number of digits is between 1 and 15, and that it starts on a digit between 1 and 5, the number of passwords is just $180\cdot 15\cdot 5\cdot 35=472,500$. With a bit of thought, we can guess he's most likely to use base 10 or base 16, and so you just have $180\cdot 15\cdot 5\cdot 2=27,000$ passwords. More thought will reduce the number of likely passwords even further (e.g. if he's doing this for laziness, which is likely, he'll have between 8 and 15 digits starting at the first digit, for 2,880 possibilities).

If the attacker can only try passwords via a web login page, you might not need too many passwords possible to be secure; a login page can lock out the account after 10 tries or similar things that slow down a brute-force. But if an attacker can do an offline attack, it's fairly easy.

Length of a password doesn't determine the security of the password against a smart attacker; entropy does. If I have two possible passwords ("the blue moon rises over the sunny beach" and "colorless green ideas sleep furiously") which I randomly pick between, then an attacker who doesn't know my scheme might have trouble cracking them. But it's better to assume the attacker can figure out your scheme, and only consider how much randomness you inject into each individual password, and in that case my scheme only injects 1 bit despite having long passwords.


Feistel cipher vs Substitution-permutation network - number of rounds

While I can confirm that your “feeling“ is indeed correct, the rest of your question is not that easy to answer. I’ll try to give you some insight nevertheless.

Generally…

The number of rounds depends on the design and security parameters of the individual ciphers. This makes it rather impossible to generalize things in form of “structure $A$ should use $x$ rounds, and structure $B$ should use $y$ rounds”. While cipher algorithms may share alike structures, their internals differ… and so do their individual round numbers.

Yet, what we can say is that less rounds tend to make a cipher less secure, while more rounds tend to make a cipher more secure. This might sound perfect, but you have to keep in mind that you can’t simply take a random cipher and hope to make it “unbreakable” by throwing enough rounds at it.

Where increasing rounds doesn’t save the day…

You might have heard about cryptanalysis where people show that some algorithms are breakable when you attack “reduced rounds” of that cipher. That practically means that they took a cipher algorithm, decreased the number of rounds below the recommended minimum, and tried to successfully apply attacks on the reduced-round version of the cipher to learn about potential weaknesses. A potential weaknesses in the reduced-round version might be expandable  to the full-round version of the cipher (which uses the originally defined and/or agreed upon number of rounds).

In a worst-case scenario, someone finds a successful attack on a reduced-round cipher and successfully expands that attack to any number of rounds. From that moment on, all hope is lost for the involved cipher as that would be a “total break”… and increasing the number of rounds won’t help.

But as long as we’re not talking about such worst-case scenarios, increasing the number of rounds can help increase (or regain) the safety margin in other cases.

The “ideal” number of rounds…

In the end, cryptography is all about safety margins. During the design phase, the cipher algorithm designer will try to pinpoint the to-be-expected security his/her cipher offers as exact as he/she possibly can and/or can prove. (Assuming you’ve seen a few reference papers already, you’ll know that cipher designers publish such proofs in the reference papers which describes their individual cipher designs.) Simpler said: while creating the cipher algorithm, the designer tries to identify the minimum number of rounds his cipher needs to be able to meet the security parameters of the cipher, as well as the recommended number of rounds.

Most of the time, there is no maximum number of rounds defined. The reason for this is pretty simple: the cipher designer already provided the *recommended * number of rounds  and – if possible – related security proofs. The recommended number of rounds represents the (let’s just call it) “ideal” number of rounds in relation to the cipher’s security.

Increasing the number of rounds beyond that level may increase security, but from a certain level on you will merely be able to detect a minimal security gain, while – at the same time – you’ll notice you’re wasting too many system resources and valuable time… which doesn’t really make sense as the gain is discardable compared to the investment of time and resources. (Think about it: no one will want to wait half an hour for something to encrypt, just because you chose to increase the original number of rounds from 10 to 1.000.0000.000. Besides, the cipher will not be a million times more secure if you do that.)

tl;dr

There is no perfect answer to the question “which cipher structure” will need “what number of rounds” to be secure, because that depends on the individual cipher algorithms. While cipher structures might be alike, the security margins tend to be different. Simpler said: two ciphers with the same structure might need a totally different number of rounds to make both provide a comparable security.

But, what we can say is:

You can make almost any cipher more secure by adding enough rounds… assuming it’s not totally broken. Also, you can make almost every cipher insecure by reducing enough rounds. (1)

(1) Never reduce rounds unless you can actually prove that your reduced-round version will still provide the expected safety margin. Without such proof, you’re walking on very thin ice.


Factoring two RSA moduli $N_i=p_i\cdot q_i$ knowing that $p_2=p_1+2$?

The fancy name for this is factorization with an implicit hint. If the primes are unbalanced, i.e., if $\log_2 p_i > 2 \log_2 q_i$, we know how to factor $n_1$ and $n_2$ quite easily. Let $k$ be the number of bits $p_1$ and $p_2$ differ by (a very small $k$, usually, for $(p, p+2)$); reduce the following lattice

$$
\begin{pmatrix}
2^k & 0 & n_2 \\
0   & 2^k & -n_1
\end{pmatrix}
$$

using LLL or equivalent. The resulting shortest vector will be $(2^k q_1, 2^k q_2, 2q_1q_2)$. This method is described, in much more generality (i.e., in terms of shared $p_i$ bits) in Faugère, Marinier, and Renault (see also May and Ritzenhofen, Sarkar-Maitra, Kurusawa-Ueda, and Nitaj-Ariffin).

Two recent papers make improvements to the above lattice-based method, and Theorem 1 of Lu-Peng-Zhang-Lin seems to imply that implicit factorization with balanced moduli is indeed possible. So the answer to your question would seem to be yes.


SHA-256 is defined for inputting and outputting binary data using bits. Most libraries only perform calculations based on byte input instead of bit input though. So in general, SHA-256 operates on bytes, not on characters.

You need to explicitly encode your characters to to bytes using character encoding such as UTF-8 to use SHA-256. Some platforms have an implicit conversion to bytes, or even equate characters with bytes (the char type in C/C++), but it is better to use explicit conversion none-the-less.

Never confuse characters and bytes, it's the source of about half of the problems with cryptography on stackoverflow (as well as countless bugs on system in the field, not just concerning cryptography).

When comparing the implementation of your library, don't test against random sites on the internet; they usually get encoding/decoding wrong as well. Instead compare with test vectors that do make clear which bytes are actually processed.

After you succeed with the official test vectors, you could perform string comparison with known good libraries (Java, OpenSSL etc.) using code for which the string encoding is explicitly specified.


Why does a fixed key not make MACs like CBC-MAC or GMAC into secure hash functions?

GMAC, for example, is trivially broken if used as an unkeyed hash algorithm.

GMAC is effectively a series of operations on blocks where you take the previous state, XOR it with the next block, then multiply it in $GF(2^{128})$ by the derived secret subkey $H$.  That is, for data block $A_i$, the next hash value is computed from the previous one as follows:

$X_i = (X_{i-1} \oplus A_i) \cdot H$

$H$ is itself simply the result of encrypting a block of entirely zero bits with the cipher and secret key.  Thus, if the secret key is fixed, $H$ is known to an attacker.

With this design, with $H$ public, preimage attacks are trivial.  Let's say that you have a previous state $X_i$ and want to cause the next state of the hash, $X_{i+1}$, to be equal to $P$, your target hash.  You need to determine $A_{i+1}$ such that:

$P = X_{i+1} = (X_i \oplus A_{i+1}) \cdot H$

Solving for $A_{i+1}$, we get this, with $H^{-1}$ easily computable from $H$:

$A_{i+1} = (P \cdot H^{-1}) \oplus X_i$

Thus, you can arbitrarily control what the next hash value will be, a preimage attack.  If you don't know $H$, though, you can't do this attack.

In short, don't use MACs as general hash functions, even though it happens to work for some MACs (e.g. HMAC).


Best method of converting a private key string into a 12 word mnemonic?

BIP 39 describes the implementation of a mnemonic code or mnemonic sentence -- a group of easy to remember words -- for the generation of deterministic wallets.

Bitcoin private key is not stored in this way, rather seed to prng which generated the private and public key pair is converted into mnemonic so that its easy for human to type or remember.

A list of 2048 words, which is indexed from 0-2047(11 bit information) is used. 132 bit value (128 bit seed + 4 bit checksum) is divided into 12 chunks of 11 bits each, then each 11 bit is used to select a word from dictionary.

for more details see BIP39


What would be a really secure way to encrypt sensitive data on a web site

1. Clarifying the attacker model

You need to decide, what sort of attacks you want to protect from. The general  eavesdropping adversary model suggest that the attacker can access your database and your entire system any time.

Another, more specific assumption can be mobile eavesdropping adversary. The "mobile" attributive relates to the fact that the adversary does not have access to your system any time, only for a limited time - for instance, somebody breaks in to your server and you detect the attack, patching the system, and with that move you "remove" the attacker. The attacker might break in again, but until that point the new information is considered to be secure. Any data accessible on your server during the time window of compromise considered to be leaked in full.

You may also consider, that some special hardware (e.g. HSM) stored private keys cannot be compromised - whether this assumption is correct or not depends on the further capabilities of the attacker

You also need to consider outsider or insider attack - outsider can be a hacker from the internet, insider can be a rogue employee.

It is important to note, what axapaxa pointed out clearly: an active attacker might be able to change the behavior of your site, and steal the passwords or do other malicious changes to gain access to the information. Protection against an active attacker is hard, would require digital signing of your webserver resources on a way, that the user can check it before connecting to your service - for instance, checking the code signature on your javascript, signed with a key not available on your webserver (so, TLS does not count...). Unfortunately, there is no such a standard - yet.

So, I will stick with the passive/eavesdropping adversary assumption. Still a nice challenge to solve :).

2. Encryption architectures

On the market, you can categorize the existing solutions for this matter based on two standpoints:

where is the key managed and persistently stored
where is the encryption process takes place

Key management categories:

Managed by the site provider (this is you) with the site (e.g. simple database encryption)
Managed by the site provider in a different system (e.g. a HSM or other special hardware)
Managed by the end-user, in its own datacenter/on-premise server (e.g. HSM is provided by the end-user, your system get temporal keys from such hardware)
Managed by the end-user, on its end-device (e.g. private keys in the browser; or the password of the user if you don't store it on your webserver)

Encryption process categories:

Encryption takes place at the site provider's server (e.g. using simply a software encryption lib, with a key anywhere above)
Encryption takes place at the site provider's, separate subsystem (e.g. using a special hardware, HSM, for the encryption process as well, not just for key management)
Encryption takes place at the end-user on-premise server (e.g. encryption gateway like CipherCloud)
Encryption takes place at the end-user device (e.g. using JavaScript to encrypt).

I will not go through all of the combinations here (16 cases) in details, only the end-device key management and encryption.

Note, that your suggested version falls into the category of End-device managed key with site provider managed encryption process. This can limit the damage of a mobile eavesdropping adversary, if you regularly patch and check the system. If you want to go down that road, that is fine, even not the most secure setup, I would suggest the following:

Use PBKDF2, or preferably bcrypt, or scrypt (the last is the best) to derive a good secret from the password. Use random salt + at least 1000, but preferably 10,000 iterations, with scrypt sufficient size of memory map (larger the better, but webserver is a tricky question...). Let's say that the secret derived from the password is X.
DO NOT store X for password validation.
Use HKDF-Extract with random salt to derive from X (let's say, V), or derive from the password using PBKF2/bcrypt/scrypt using the same parameters as for X, but with a different IV. Store V for password validation.
Use HSM or other special hardware to do the server side encryption of the data.

DO NOT encrypt data with HSM+X, rather encrypt a key-encryption-key K. Encryption of actual data with K can be done outside of a HSM, simply using a crypto lib on your webserver.
I suggest using AES-GCM with random IV for data encryption, AES-KW for key wrapping. You may also consider format-preserving encryption modes IF, and ONLY IF there is an unavoidable size constraint for the data, because format-preserving encryption modes are less secure than AES-GCM with random IV.

3. End-device managed key with end-device managed encryption (aka. end-to-end encryption)

You asked about a website, so I will focus only on WebCrypto API capabilities - an encryption library for JavaScript, provided by modern browsers. For applications, you may use other cryptolibs.

With WebCrypto, you can generate a secure random key, to use it for encryption. Encryption can take place at the frontend of the website, for instance before submiting a form, a JavaScript encrypts its content with AES-GCM. The keys can be stored in the local storage of the browser, which is never shared with your website, unlike cookies - it is kept local all the time.

However, if you want that a user access the information from another computer, I suggest that you use PBKDF2 to derive a secret from user password (using proper salt and proper number of iterations for stretching) on the browser side. Then, using this derived key, you can wrap the encryption keys with AES-KW - all supported by WebCrypto API.

This way, your server will not get access to the user password any-time, unless you do the password authentication properly. If you want to authenticate the user, do not send the password to your server, because that is an actual disclosure and the whole point of keywrapping, encryption will slip on this banana... instead of that, use PBKDF2 derived secret for authentication, with a completely random salt, different from what is used for encryption. You may also consider using SRP, SPAKE, AugPAKE, etc. for authentication - however, those are not supported by WebCrypto.

If you do not want to implement those, you may also consider using 0_kit, a project I am involved in, which provides all those features integrated, on top of WebCrypto and other JavaScript implementation of crypto algorithms.


Since you asked in general "Are there any other obvious flaws/issues I'm missing", I would recommend that you would take a critical look at the whole update process flow. I would not consider the quality of the PRNG at your server as an obvious weak point, as long as it is reasonably strong, since on servers you have quite a bit of choice of reasonably good routines to generate a fair PRN (note that it is quite acceptable to generate a pair of good PGP keys on a regular server or client machines).

Critical review of the update process as a whole should consider the following, by no means an exhaustive, list:

A server that is opened to the public internet usually exhibits a fairly wide attack surface - OS, apps, services, open ports etc.
If I were an attacker, I would first try to penetrate your server, and use your private key in there to send malicious update commands out.
You need to secure the environment of your embedded processor. I assume that you discount the possibility of direct physical acess to the embedded system (otherwise all security bets are off), but you do need to think about other issues like flooding the device's comm channel with badely signed messages generated by an attacker, thus causing DOS on your embedded system. You may possibly mitigate this with a watchdog timer that will kill the update loop after a set time.
I concur with maeher - questioning the need to generate a key pair for each device. This will be a nighmare of a management vis a vis the chance of private key compromise: How would you remotely identify the client in order to know which private key to use for the signature going to that particular client? would you send a bunch of records for each client to test them all in order to find the one recognized sig in them? would you first send a client ID in the clear and respond with the appropriate signed message? I would also, as maeher proposed, recommend one key pair with all clients will have the same public key.
If you are really concerned about someone stealing your private keys, you may want to consider having all the keys expired after each update and regenerating a new pair for the next update cycle (the new pair will be signed by the old one before expiring). This is not as strong as a unique pair for each client, but certainly more manageable.

When you consider the above, it does make a difference if your embedded app is just an industrial controller, or a system whose failure due to a rogue update will cause a regional catastrophe.


My understanding is that the cipher's encryption:

Performs a fixed public reversible transformation of the first 128 bytes of plaintext.
Enciphers the first 8 bytes $[B_0…B_7]$ with $K_1$, $K_2$, then $K_3$
Enciphers bytes $[B_{4+8i}…B_{11+8i}]$ with $K_1$
Enciphers bytes $[B_{2+8i}…B_{9+8i}]$ with $K_2$
Enciphers bytes $[B_{1+8i}…B_{8+8i}]$ with $K_3$

The index $i\ge0$ grows as large as necessary to cover the whole plaintext (something untold takes care of the end).
Consider what happens when one enciphers the all-zero plaintext. Step 1 leaves that unchanged. Step 2 causes irregularities in the first 8 bytes. Step 3 extends that to the first 8+4=12 bytes. Step 4 extends that to the first 12+6=18 bytes.  Step 4 extends that to the first 18+7=25 bytes. But starting from byte 25 in the output of step 5, there's a key-dependent pattern that repeats every 8 bytes.
More generally, for any repeating 8-byte pattern in plaintext, there's a matching 8-byte pattern in the ciphertext (after the first 128+4+6+7=145 bytes or so).
I conclude that the proposed construction does not fully "address the block size limitation in terms of bulk encryption". It does increase diffusion, thought.

I advocate against step 1. It does make the first byte of ciphertext dependent on more input bytes, but any fixed public reversible transformation of plaintext demonstrably has no cryptographic value under Chosen Plaintext Attack (as in the above), or under any Known Plaintext Attack working with random plaintext.
It's possible to make a 128-bit block cipher out of a 64-bit one. Assuming some safe operating mode like GCM, CTR, CBC, OFB, CFB on top of that, a simple such 128-bit block cipher construction that I would trust to have security up to $2^{48}$ bytes encrypted (rather than $2^{31}$ for Blowfish or $2^{64}$ for AES) uses 6 keys, assumed independent. In a Blowfish context, we could prefix a common key with 6 different 4-byte haphazard public constants. Starting from a 128-bit plaintext $[B_0…B_{15}]$:

encipher $[B_0…B_7]$ with $K_1$, $[B_8…B_{15}]$ with $K_2$.
encipher $[B_4…B_{11}]$ with $K_3$, $[B_{12}…B_{15}]\mathbin\|[B_0…B_3]$ with $K_4$.
encipher $[B_0…B_7]$ with $K_5$, $[B_8…B_{15}]$ with $K_6$.


Is using AES-256 with a key of less than 256 bits of entropy still quantum-resistant?

Currently, the quantum attacks work on the block cipher itself. The Grover's search algorithm reduces the complexity of 256-bit key into 128-bit since it has complexity $\mathcal{O}(\sqrt{n})$ and in the case of 256-bit $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$

Since you have started with 128-bit entropy, theoretically, the quantum attacker to block cipher itself with a 256-bit key will not benefit from Grover's algorithm since Grover's algorithm will search 256-bit. Keep in mind that 256-bit space is infeasible for the quantum.

What if in an unforeseeable future, someone builds a quantum circuit for the PBKDF2 + AES combination that is the search for the 128-bit input to PBKDF2 and uses the output for the AES-256 key and perform Grover's kind of attack?

This can be done by extending the AES-256 Grover Search with a 128-Q-bit PBKDF2 Quantum circuit. Since the input is 128-bit, the search will be $\mathcal{O}(2^{64})$ to find the ciphertext.

The attacker, always, will use the weakest point!.


Why is a Feistel network not a type of substitution-permutation network?

In the substitution step of a typical Substitution-Permutation Network (e.g. in AES SubBytes), the whole state is broken in parts and each part substituted. That's not the case in (the core of) a Feistel cipher, where at each step/round some sizable part of the state is bound to remain unchanged (in order that each step be reversible).


Encrypt multiple RSA keys with same passphrase

The openssl docs say nothing about this issue, and no answer from the community. So I tried to figure it out with a small experiment. I created a private key (not encrypted) with:

openssl genrsa -out key.pem

Then I encrypted the key twice, using the same password:

openssl rsa -aes256 -in key.pem -out key-enc-1.pem
openssl rsa -aes256 -in key.pem -out key-enc-2.pem

and compared the content of key-enc-1.pem and key-enc-2.pem

Files were completely different so it looks like the AES-encryption is done with a random salt.

So, answering my own question: using openssl genrsa with aes-encryption, it is safe to use the same password for all my private keys.


What does "circuits" mean in Cryptography?

Circuits can be expressed using very simple operations. For example, a boolean circuit consists of only two types of gates, addition and multiplication (where the input values are each 1 bit). Furthermore, (boolean) circuits can describe any computation.

This is very nice when it comes to fully-homomorphic encryption. All we have to do is provide a way to homomorphically evaluate two types of gates and voila, we can evaluate any computation homomorphically. As pointed out in a comment below, circuits have been used for more than just homomorphic encryption. Secure multiparty computation (both the secret sharing and the garbled circuits variants) uses this as well.

This makes the job for cryptographers much easier, but makes things harder on users, right. If I want my super awesome algorithm to be evaluated homomorphically, I've got to come up with a way to implement it as a boolean circuit. That means no loops, no conditionals, etc. I only get addition and multiplication. Other computation paradigms have been looked at. One early one was moving from boolean circuits to arithmetic circuits (not too big of a jump).

Update
Recent work is interested in not limiting programmers to circuits. For example this, this, and this all look at language based approaches.

P.S. Sorry for the link dump. I haven't properly read through these so I can't really comment. A question on how non-circuit approaches work could be a good question to ask. I'm betting there is someone on here who can go into detail on those.


Arbitrary width pseudorandom permutation

There's XXTEA, whose block size is an arbitrary multiple of 64 bits, but it's broken.  There's the Hasty Pudding Cipher, an AES candidate, but it was not selected to be one of the AES finalists and has received relatively little attention.

Built out of a stream cipher (short key $\mapsto$ long output stream) and hash function (long message $\mapsto$ short hash), there are BEAR, LION, and LIONESS.  But you probably won't break any speed records with an authenticated encryption scheme built out of one of those, rather than out of the stream cipher and hash function directly.


An example of of an information theoretically secure protocol that is not cryptographically secure

In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is the standard definition, specifically to avoid protocols such as you presented in your question.

So, the answer is:

If you allow the simulator to be unbounded in running time (and irrespective of the running time of the real adversary) then information-theoretic security does not necessarily imply computational security.
If you restrict the simulator as I described, then information-theoretic security does imply computational security.

In my opinion, it makes no sense to allow the simulator to be unbounded if the real world party is (and this is the case in the real world). Therefore, I strongly argue that you must restrict the simulator as described.


1) I don't know any established alternatives.

2) It is not correct to say that such algorithms are purposely-slowed. They not only can be slowed, but also can use much memory. A single word for this would be resources. And I would stress even not resources, but rather the price, because the whole idea is to make the price prohibiting for attackers. I would suggest following terms:

Expensive hashing
Resource intensive
Resource demanding
Resource hard
Resource greedy
Resource hungry

I will put these terms each as a separate comment below my answer. Feel free to vote :) In a couple of weeks we'll see the result.


Finding where I am in a linear recurrence relation

First of all, your linear recurrence relation is not exactly linear, it is affine. However, in general, it is not difficult to get rid of the constant term $d$.

To do this, define $A(n)=a(n)+t$, and choose $t$ to make sure that the constant term vanishes. This requires $t=(c_1+...+c_k)t+d$, clearly, this can be done unless $c_1+...+c_k=1$.

From now on, I assume that we have no constant term $d$. You want to recover a possible $n$ from a single value $a(n)$. As far as I know, there is no direct relation between this and discrete logarithms.

However, there is a direct relation to the discrete logarithm problem for a simple variant of your question, i.e. given $a(n), a(n-1), ..., a(n-k+1)$ recover $n$.

This variant is a classical question about LFSR (linear feedback shift register). Usually, people consider LFSRs modulo 2, but it is also possible to consider them modulo $p$ and this is precisely what we are doing here.

To the recurrence formula, you can associate a polynomial $P(x)=x^n-(c_n\cdot x^{(n-1)}+...+c_2\cdot x+c_1)$. If you associate to a state $a(1),...,a(n)$ the polynomial $a(1)+a(2)\cdot x+...+a(n)\cdot x^{n-1}$ then updating a state is simply multiplication by $x$ modulo $p$. If this polynomial is irreducible, then finding the correct power of $x$ is simply a discrete logarithm problem in $GF(p^n)$.

When $P(x)$ is not irreducible, you are in fact simultaneously computing the values modulo several irreducible polynomials (and the results are pasted together using the Chinese Remainder Theorem), so you can solve it by computing discrete logarithms in smaller fields.

Coming back to your original question, a equivalent formulation in terms of discrete logarithms is: given $x$ an integer modulo $p$ and an extension field $GF(p^n)$ find an arbitrary element $X$ in $GF(p^n)$ represented by a polynomial whose constant term is $x$, together with a logarithm of $X$.


RSA encryption input range - plaintexts that map to ciphertexts?

Yes, this is textbook RSA, so by definition:

$0^e \equiv 0 \pmod{n}$

$1^e \equiv 1 \pmod{n}$

$(n - 1)^e \equiv (-1)^e \equiv -1 \equiv n - 1 \pmod{n}$

(since $e$ must be odd as $\varphi{(n)}$ is even and thus $2$ has no modular inverse modulo $\varphi{(n)}$)

This is (obviously) bad since an observer can immediately deduce the plaintext for those messages even without knowing the decryption exponent, but normally you use padding in real life RSA which makes those kind of inputs essentially impossible.

However you are wrong for $n - 2$. It does not necessarily encrypt to itself. How did you get that? You must be making some mistake in your implementation, or perhaps got lucky with a few small inputs.

Counterexample, $n = 377$, $e = 17$ ($d = 257$, $\varphi{(377)} = 336$):

$(n - 2)^e \equiv 375^{17} \equiv 124 \pmod{377}$

Are you sure you are calculating $e$ right?


Number of functions included in a keyed PRF

There are $2^n$ possible values for $k$, and for each one there is a function $F_k$, ergo, there are at most $2^n$ possible functions $F_k$. ("At most" is because it is possible that two different values of $k$ yield the same function $F_k$.)


Is it possible to tweak AES-GCM so that it is satisfactory for whole-disk encryption (like XTS mode)?

The ZFS file system uses AES in CCM or GCM modes.  This works because in ZFS the data and file system metadata is encrypted but the block pointers are in the clear, the AuthTag (MAC) is stored in the block pointer.  ZFS also has a SHA256 based merkle tree based on the block pointers that is used for data integrity for resilvering and navigation purposes.

Note that ZFS is file system (actually object based really) encryption it does not claim to be "full disk encryption".

For more details see here: https://blogs.oracle.com/darren/entry/zfs_encryption_what_is_on

Darren J Moffat (Architect and lead developer for ZFS encryption).


How to verify a trusted Issuer in U-Prove

For any credentials scheme, trust is defined out of the scheme. It might be your employer or your government.

Please note there is no clear separation whether signature is coming from Issuer or Prover. Signature on token public key $h$ is verified with Issuer public key (Figure 4) as a proof of equality of two logarithms. However, it is created by running a blind signature protocol running both by Issuer and User (Figure 8). There is no chance to create this signature without Issuer private key $y_0$.

Please consider to double-check Issuer parameters generation (section 2.3.1): once on scheme setup.


How can I be sure the RNGCryptoServiceProvider is able to produce 12 bytes that can have 2^96 values?

RNGCryptoServiceProvider - according to many sites including the following Wikipedia link itself - uses the CryptGenRandom functionality of the operating system. You therefore need to convince your clients that the OS functionality is sufficient.

The Wikipedia article contains references to FIPS and Common Criteria EAL4 evaluations of the operating systems containing the RNG. That should normally be sufficient - although I must admit that I cannot find the actual FIPS validation certificate of the RNG.

The best reference is probably the documentation of BCryptGenRandom which states:

  The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.

This is for Windows versions after Windows Vista. Before that an RC4 based algorithm seems to have been used.


How can I prove I'm the recipient of an encrypted message without revealing my identity and the message?

One possible approach to this may use a commitment scheme.

That when Alice deposits the message $m$, she signs $m$ resulting in the signature $\sigma$, then she picks a (eg 256-bit) random string $r$ and encrypts $(r,m,\sigma)$ into the ciphertext $c$. Now she creates a commitment $\rho$ (eg a SHA-256 hash of $r$) for $r$ and publishes $(\rho,c)$ at the dead drop.

When Bob retrieves the message, he decrypts $c$, yielding $(r,m,\sigma$) and then opens the commitment (e.g. presenting $r$ such that $H(r)=\rho$) to the operator, who can now know that Bob was indeed able to decrypt the ciphertext. But because $r$ is a random string it doesn't leak anything about $m$.

Of course, while this solution works, it assumes that Alice is actually "honest" and doesn't encrypt something without also leaving the solution to the commitment behind (and thus taking up space that can never be reclaimed). Of course it depends on your concrete situation whether this suffices or whether you want a more sophisticated scheme (of which there some I think).