secretKey ⊕ (secretKey ≪ 1), is randomness lost?

While bmm6o's answer is correct, I want to give another angle onto things.

The function / transformation you described is linear! Specifically, it is a linear function over the vector space $\mathbb F_2^n$ if you consider $n$-bit inputs. Now this means, that you can apply all the tricks you learned in linear algebra to this transformation, which is characterized by the following matrix for $n=4$ (assuming $\ll$ denotes cyclic shift instead of logical shift):

\begin{equation}
\begin{pmatrix}
x_1'\\x_2'\\x_3'\\x_4'
\end{pmatrix}
=
\begin{pmatrix}
1&0&0&1\\
1&1&0&0\\
0&1&1&0\\
0&0&1&1
\end{pmatrix}
\cdot
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}
\end{equation}

If $\ll$ denotes logical shift (i.e. fill up on the right with 0 instead of what was pushed out), then simply replace the top-right $1$ with $0$.

As it turns out, if you have the top-right $1$, the determinant of the matrix is $0$ which also means, the transformation is not a permutation, as there's no unique inverse function!

However, if we use the version with a logical shift instead, we always get a determinant of $1$ and thus the confirmation that this indeed describes a permutation (and if we want to, we can also invert it).

To see the above assertions, let's call the matrix $A$ and the value of the top-right bit $b$. Note $A-I$ is the companion matrix to the polynomial $x^n-b$, which means the characteristic polynomial of $A-I$ is $x^n-b$. Now the characteristic polynomial of a matrix $B$ is equal to $\det(B-xI)$, which in our case is $\det((A-I)-xI)=\det(A-(x+1)I)$ which for $x=-1$ yields $\det(A)=(-1)^n-b$, however in $\mathbb F_2$, $-1$ is equal to $1$, meaning $\det(A)=1-b$, which implies that the key transformation is invertible (and thus entropy-preserving) iff a logical instead of a cyclical shift is used for all values sizes of the input and output! Credit goes to Will Jagy for the inspiration (and for a shorter, but more mathy explanation).


RSA:Plaintext block has a common factor with modulus

Here's one way to argue for this property using the Chinese Remainder Theorem:

Let $m,e,n=pq$ be arbitrary with $\gcd(p,q)=1$. Let's assume $\gcd(m,n)>1$ and more precisely wlog $\gcd(m,n)=p$. Now we shall apply the Chinese Remainder Map $\theta:\mathbb Z_n\to\mathbb Z_p\times \mathbb Z_q:x\mapsto(x\bmod p,x\bmod q)$ which will yield $\theta(m)=(0,y)$ for $y:=m\bmod q$. Now, $\theta$ is a ring isomorphism, meaning that it preserves multiplication and addition, that is $\theta(m^e)=(0,z:=y^e\bmod q)$. Because $\theta$ is a bijection, its inverse is unique and the solution $c\in\mathbb Z_n$ to the following set of equations:

\begin{align*}
c&\equiv0\pmod p\\
c&\equiv z\pmod q
\end{align*}
And as you can easily verify, $c=zp$ satisfies these equations, meaning it is the encryption of $m$ and thus a multiple of $p$.


Which elements of private RSA file are really constitutive of private key?

This is a harder question than that it looks.

To perform "plain" RSA modular exponentiation you can simply use the private exponent and the modulus. However, for faster RSA calculations that use the Chinese Remainder Theorem (CRT) you need the prime values, exponents and modulus. For RSA CRT you don't need the private exponent.

In principle you can calculate all private values from the primes: that's just RSA key pair generation after all: you find primes and then you perform calculations on them. So just storing the primes is a space efficient option. However, it does mean you have to recreate the modulus and private exponent or the CRT parameters before every RSA calculation, which will take time.

There is one even more space efficient option: store the random seed from which the prime search starts from, but it comes with a large set of problems (such as having to find the primes for each calculation, which is a terribly inefficient operation). However, it does mean you can store just 128 bits.

To get back the CRT parameters from just the private exponent and modulus is possible, but it takes time and thus negates any advantage to use CRT in the first place. So that kind of calculation should just be performed once, if at all. It can make sense if you first did choose plain RSA and then decide to go for CRT calculations. This is hard to do - tools will generally not include this option - so I would try and avoid having to ever use it.

The public exponent you don't need for private key operations. Sometimes the public key is used to verify that the operation concluded successfully (e.g. by verifying a signature right after generating it). This is of course a fully optional operation and usually only performed to make sure nobody messed with the generation in the first place.

You can say that the public exponent is mainly included because it may be easily / efficiently calculated / guessed from the private exponent, so including it makes sense for PKCS#1, where the structure in the question is defined.

Note that the public exponent is often simply set to a single small value, 65537 or F4, the fifth prime of Fermat. This is what OpenSSL (currently) uses by default.

EDIT: I don't think you can leave too much out if you're required to deal with OpenSSL. OpenSSL uses PKCS#1 or PKCS#8 private RSA keys. PKCS#8 simply includes the PKCS#1 private key, so that representation is just ever so slightly larger.

In turn, PKCS#1 is defined as follows (from the ASN.1 module in Appendix C of RFC 3447 that defines PKCS#1):

--
-- Representation of RSA private key with information for the CRT
-- algorithm.
--
RSAPrivateKey ::= SEQUENCE {
    version           Version,
    modulus           INTEGER,  -- n
    publicExponent    INTEGER,  -- e
    privateExponent   INTEGER,  -- d
    prime1            INTEGER,  -- p
    prime2            INTEGER,  -- q
    exponent1         INTEGER,  -- d mod (p-1)
    exponent2         INTEGER,  -- d mod (q-1)
    coefficient       INTEGER,  -- (inverse of q) mod p
    otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

as you can see, most of the stuff in there is non-optional. Only otherPrimeInfos can - and usually will already - be empty as it is used for CRT multi-prime computations.


Is entropy being lost when the hash of a secret has a specific format?

From the linked page, a minikey is a 30-character string over the base58 alphabet with the first byte fixed to 'S', so effectively 29 characters. This gives a space of $log_2(58^{29}) \approx 169.88$ bits. Assuming that SHA is a random function, the probability of the hash starting with an 0-byte after appending a ? is 1/256, so this check loses 8 bits of entropy giving just over 161 bits of security.


Why is OCB-AES mode not becoming a standard for authenticated encryption?

Because OCB is patented.

And there are other good solutions for authenticated encryption that aren't patented.  This makes them more suitable, in most situations.  I can recommend, e.g., EAX, GCM, or CWC.  EAX and GCM have been used in some standards, and AES-GCM has been standardized.

For pointers where you can learn more, read Wikipedia.  And try using search on this site with the phrase "authenticated encryption".

Update: There are now free licenses available for OCB.  However, they have some unusual restrictions, which some implementors have expressed concerns over (e.g., one license only applies to open-source software; another allows only non-military uses).  For a detailed discussion, see the responses on this thread on the IRTF CFRG mailing list.


No, nothing is ever undisputed.

There is a cipher that provides perfect security (OTP) but that doesn't mean it is very practical if just for key distribution. So saying it's "the best" can be and should be disputed.

However, the answer the quiz master is looking for is probably the Vigenère cipher. I presume however that there must have been at least one person that had a doubt about the strength of the cipher.


Does this equation hold in a bilinear map?

No it does not. To see it, take $b=1$:

$e(a,c)^{c1\cdot c2\cdot c3}e(b,c)^{c1\cdot c2\cdot c4}= e(a,c)^{c1\cdot c2\cdot c3}e(1,c)^{c1\cdot c2\cdot c4} = e(a,c)^{c1\cdot c2\cdot c3}1^{c1\cdot c2\cdot c4} = e(a,c)^{c1\cdot c2\cdot c3}$

similarly,

$e(a,c)^{c2\cdot c3}e(b,c)^{c1^2\cdot c2\cdot c4} = e(a,c)^{c2\cdot c3}$

So you would get

$e(a,c)^{c1\cdot c2\cdot c3} = e(a,c)^{c2\cdot c3}$

which is clearly not true in general (unless $c_1 = 1$ or $c_1 = 0$ or $e(a,c) = 1$).


Allowing third party to verify and/or replay a draw

Here is a paper that examines one possible approach to do this.  In essense, it this allows anyone who cares to through in some randomness; when the deadline occurs, then all the inputs are published (so everyone can verify that their input was included), and then all the inputs are hashed together (using a transform that is slow to compute, but can be verified quickly).  The output of this transform can then be used directly to generate the selections for your lottery.

Because the eventual output is a complex (and hard to predict) verifiable function of everyone's input, then anyone who contributes an input knows that lottery was selected honestly.  And, because the transform is deliberately hard to compute, they know that no one could do some precomputations a few seconds ahead of the deadline, and generate an input at the last second to skew it.

The paper uses this to select a random elliptic curve; it could just as easily be a lottery...


Why inversion and multiplication operations are costly in elliptic curves?

When we perform, say, a point addition of two elliptic curve points, we need to work with elements of the field that the elliptic curve is defined over.   There are several operations we may need to perform, and the total cost of the point addition is the sum of the cost of all the field operations we need to do (plus some overhead, which is typically pretty small):

We may need to add and subtract field elements.  There two operations have about the same cost, and so we typically don't distinguish them.  They're also quite cheap (compared to the other operations required), so it is quite common to ignore them when coming up with an approximation of the total cost.
We may need to multiply two elements.  The cost of this operation is often the 'unit' where all other costs are measured against.
We may need to square an element.  This can be done by just handing the element to the multiply routine; however there are symmetries that we can take advantage of to make this specific operation cheaper.  For odd-characteristic fields, this squaring operation will be somewhere between 0.5 and 1 times the cost of a multiply.  Different implementations will differ in the precise figure; we try to account for that.
We may need to find the multiplicative inverse of an element; that is, given $x$, find the value $y$ such that $xy = 1$, where $1$ is the multiplicative identity.  This operation is by far the most expensive operation for just about any representation.

This $I/M$ value tries to capture exactly how expensive an inverse operation is; an $I/M$ value of 8 estimates that an inverse operation is about as expensive as the total of 8 multiplication operations.

We need an estimate here to guide us which mix of operations will run quickest in total.  If we have an $I/M$ of 5, then an optimization that replaces one inverse with 6 multiplies is a loss.  However, if we have an $I/M$ value of 8; then it is a win.

Now, in my experience, $I/M$ ratios tend to be quite high; a ratio of 8 would be far smaller than what I've seen.


That's correct.  Here are the padding instructions from RFC1321, the MD5 spec:

3.1 Step 1. Append Padding Bits

   The message is "padded" (extended) so that its length (in bits) is
   congruent to 448, modulo 512. That is, the message is extended so
   that it is just 64 bits shy of being a multiple of 512 bits long.
   Padding is always performed, even if the length of the message is
   already congruent to 448, modulo 512.

   Padding is performed as follows: a single "1" bit is appended to the
   message, and then "0" bits are appended so that the length in bits of
   the padded message becomes congruent to 448, modulo 512. In all, at
   least one bit and at most 512 bits are appended.

3.2 Step 2. Append Length

   A 64-bit representation of b (the length of the message before the
   padding bits were added) is appended to the result of the previous
   step. In the unlikely event that b is greater than 2^64, then only
   the low-order 64 bits of b are used. (These bits are appended as two
   32-bit words and appended low-order word first in accordance with the
   previous conventions.)

   At this point the resulting message (after padding with bits and with
   b) has a length that is an exact multiple of 512 bits. Equivalently,
   this message has a length that is an exact multiple of 16 (32-bit)
   words. Let M[0 ... N-1] denote the words of the resulting message,
   where N is a multiple of 16.


Ok, here is a random idea I had; it needs further analysis, especially in regards to the security parameters.

It's based on RSA; I believe that there are ways to run RSA as a threshold scheme; I'll assume that you'll use one of those.

The public key will be the normal RSA parameters $N, e$, as well as an integer $C$.  The private key will be the RSA private key (and the integer $T$).

Definitions: we will call an integer $x$ smooth if all its prime factors are $< T$.  We will call an integer $x$ rough if all its prime factors are $\ge T$.

Encryption method: we first encode the plaintext as a rough integer $P$ between $\sqrt[4]{N}$ and $\sqrt[4]{N}/2$.  Then, the ciphertext is the value $P^e \bmod N$.

Blinding method: we take the ciphertext $C$, and select a random smooth value $\sqrt{N}/2 < S < \sqrt{N}$.  Then, the blinded ciphertext is the value $C^2 S^e \bmod N$.

Decryption method: we take the ciphertext $C$, and compute $D = C^d \bmod N$.  If $\sqrt[4]{N}/ 2 < D < \sqrt[4]{N}$, then $D$ is the resulting plaintext.  If $D > \sqrt[4]{N}$, then we divide out all the prime factors $< T$ from $D$, and then compute the integer squareroot (and if it's not a perfect square, decryption fails); the resulting squareroot is the plaintext.

Notes:

Blinding works because the blinded value $C^2S^e = (P^2S)^e \pmod N$, and as $P^2S < N$, RSA decryption results in the integer $P^2S$.
It should be obvious why blinding an already blinded value doesn't work.
Obviously, we need to specify the sizes of $N$ and $T$.  One requirement is to make the blinding recognization problem hard, that is, given two ciphertexts $C_1$, $C_2$, determine whether one the blinded version of the other.  There is a MITM attack available, such to be $s$-bits secure, there needs to be at least $2^{2s}$ smooth numbers below $\sqrt{N}$.  I suspect this will imply that $N$ will need to be larger than normally required for RSA, however that needs to be analyzed.  My instincts say that $N \approx 2^{4096}$ and $C = 10000$ should work reasonably, but again, real analysis is needed.
One thing that needs to be considered are possible weaknesses due to the homomorphic properties of RSA.  Even though we're not using a conventional padding scheme, I believe we're safe (because $T$ is large and rough), however that really does need analysis.
Of course, this doesn't work for $e=3$; the standard $e=65537$ should be fine.
We also need to spell out how to randomly select a large smooth value, but again, should be spelled out.
The process of encoding the plaintext as a rough integer (and decoding it at the end) is straight-forward.

On review, the idea isn't perfect; an attacker could generate a "weak blind" on an already blinded value by multiplying it by $(a/b)^e$ (for small $a, b$); this works if $b$ is a factor of the $S$ the blinding used.  I'll leave this answer open, in case someone sees a way to address this...


What can I do if I get private key of signing algorithm in Digital signiture

When talking about digital signatures, the private key is what proves the authenticity of the signature, precisely because it is private.

The use case proceeds like this: I choose a private and public key pair. Because I chose it, only I know both keys. I then send a message and sign it by using my private key, typically by encrypting a digest, hash, or checksum of the message with the private key, so that it can only be decrypted with the matching public key.

I publish my public key for others to verify my signature with.

The receiver then manually computes the same digest of the message, decrypts the signature I sent along with it using my public key, and compares the two. If they are identical, the only way that is possible is if I am indeed the person who has the private key and published its matching public key. Otherwise, I would not have been able to properly sign the message without my private key.

This works because it is exceedingly difficult to compute the private key from the public key, so much so that it would take a very long time even on a supercomputer.

You might ask at this point, why is the signature an encrypted digest or hash of the message? If the message differs in any way (was tampered with or intercepted, as with a man-in-the-middle attack), the digest won't match whether it's decrypted correctly or not. So tampering with the message necessarily invalidates the signature, because it's a digest of the message itself, proving it's the same message sent by the person who signed it.


For uniterated SHA-256 of salted password, should the password precede the salt?

We are considering two hypothetical password hashes

$(S_i,P_i)\mapsto H_i=\operatorname{SHA-256}(S_i\mathbin\|P_i)$
$(S_i,P_i)\mapsto H_i=\operatorname{SHA-256}(P_i\mathbin\|S_i)$

As pointed in the question, both are un-iterated, thus very weak under the attack model where the salt $S_i$ and hashes $H_i$ leak, and the adversary is after $P_i$ (for a particular $i$, or worse for one of any $i$).

An important thing is what we put in the salt $S_i$: that should include both a fixed string $F$ dependent on the instantiation (e.g the name of the server), and a user-unique string (e.g. userid, login, email, random) $U_i$. The term $U_i$ helps because with $U_i$ adversaries can not attack multiple logins simultaneously, they must perform a hash for each password tested for each login. The term $F$ prevents amortizing attack work across multiple servers, and makes the hash slower, thus more secure.

The least feeble option is probably $H_i=\operatorname{SHA-256}(P_i\mathbin\|U_i\mathbin\|F)$, with $F$ as large as possible. The password should be first for the reason in the question: that blocks optimizations where some of the hash's internal operations is reused across multiple $P_i$. For the same reason, $U_i$ should be second.

But when $P_i\mathbin\|U_i\mathbin\|F$ is short (less than 64 bytes), the order is nearly immaterial, because that fits in the same first padded block of message of SHA-256, thus an attacker can not precompute any full compression in SHA-256, at worse some of very few rounds among 64.

Thus if for some strange reason (like a device operated on small battery and very little RAM) one can't go for an iterated password hash and must use plain SHA-256, then put the constant part $F$ of the salt last, and make it as long as practical; and rather put the password before the salt.

As an aside, if a long $F$ is obtained by repeating a shorter string (which allows arbitrary long $F$ with only little RAM), it should have an odd length, in order to reduce the potential for optimization of the message expansion of SHA-256.

P.S. per comment: While the $U_i$ part of the salt must be in the database, $F$ needs not, at least in each entry, especially if it is long. I have been assuming that $F$ is public, not "pepper" (that is, semi-secret). If there is some pepper $K$ (that is, a tentatively secret key, by opposition to salt that is assumed fully public), it should be early in the hashed data, in contact with $P_i$ or otherwise in the first 64 bytes; and backed up other than in the database in case the whole thing needs to be restored on a different machine.


If you wrote a reversible SHA-256 algorithm, how many "metadata" bits would be required for reversability?

If you would write such an algo, it would not be SHA-256 anymore. Also, it would lose its cryptographic usefulness.

SHA-256 is a non-reversible, one-way compression function. Voiding the non-reversability would void the core functionality that makes SHA-256 a cryptographically secure hash.

In  the end you would end up having a non-lossy, two-way compression function — and a bad one too as it would waste too much space compared to simple compression functions like (for example) ZIP.

Also, since the goal ends up right there, it is not about cryptography anymore… rendering any further discussion about your idea off-topic.

TL;DR:

Assuming you do not modify SHA-256 and simply rely on your "metadata" for reconstruction, the size of your "metadata" would be equal to the size of the input.
Modifying SHA-256 itself to optimize the space needed for any kind of "metadata" is not an option, as the algo would lose its cryptographic usefulness (and not be SHA-256 anymore anyway).

Besides that, your question seems to try work around something which has been asked several times before.

For example, see Would it be possible to generate the original data from a SHA-512 checksum?.

So, in a broad sense your question is a duplicate of all existing questions asking about restoring the original input data from a cryptographically secure hash output.

Any other interpretation of your question (in its current state) would make it an information theory question which would be more on-topic at Computer Science StackExchange.


why Efail CFB malleability gadget is different from CFB mode decryption?

Both schemes present in your image represent the same thing. Only the indexing of Ci differ by 1. It all depends on what you consider to be your "first block":

In the first, you decrypt by manipulating the previous block and the current block. This means your decryption process start with C-1 and C0 to recover P0. Here, C-1 = IV
In the other, you decrypt by manipulating the current block and the next. So P0 = Enc(C0) XOR C1, meaning C0 = IV.

Clarification:

CFB malleability gadget does not modify the decryption process in any way. The only trick is to modify the ciphertext before decryption.

You seem to have trouble with the notation and the block indexing, so here is a little example of how the CFB gadget would be used. In this example, C0 is the first block of encrypted data, the IV is considered apart (whereas C0 is the IV if we follow Efail notation, hence the shift in the index you may notice in my figure).

To make it clear, keeping the same notation as in my figure, CFB decryption would go as follow:

P0 = Enc(IV) xor C0
P1 = Enc(C0) xor C1
P2 = Enc(C1) xor C2
...
Pi = Enc(Ci-1) xor Ci
Pi+1 = Enc(Ci) xor Ci+1
...

That is how CFB decryption works, whether or not you are using it as a gadget.


The paper you link to in your comment is a fictional paper where the author (inspired by experiences with reviews he got for his own papers) imagines how negative reviews to groundbreaking papers could have looked like. So its just fun ;)

AFAIK the RSA paper has never been rejected (but the very first paper of Ralph Merkle on public key crypto got rejected, as already mentioned in the comments).


Encrypt-then-MAC: Do I need to authenticate the IV?

In short: You must authenticate the IV.
Which particular attacks apply if you don't depends on the block cipher mode; I will give two common examples.

In CTR mode, an attacker who fiddles with the IV can forge authenticated messages, but the content of the corresponding plaintext is beyond his control (since he doesn't know the key). Depending on the encrypted data, this may or may not be a real problem (as random binary garbage may be caught by subsequent validations in the protocol), but it certainly is an unnecessary security risk in any case.
CBC mode breaks horribly, as the following diagram shows:

Clearly, the IV is exclusively XORed into the first plaintext block after decryption and discarded afterwards, enabling an attacker to introduce arbitrary differentials in the first block without changing anything else by XORing them into the IV. Depending on the payload's structure, this could, for example, be used to toggle some important flag in a protocol header or change a length field.


Key lengths of asymmetric encryption: ElGamal and ECC

Key size and encryption system

Encryption systems are often grouped into families. Common families
 include symmetric systems (e.g. AES) and asymmetric systems (e.g.
 RSA); they may alternatively be grouped according to the central
 algorithm used (e.g. elliptic curve cryptography).

As each of these is of a different level of cryptographic complexity,
 it is usual to have different key sizes for the same level of
 security, depending upon the algorithm used. For example, the security
 available with a 1024-bit key using asymmetric RSA is considered
 approximately equal in security to an 80-bit key in a symmetric
 algorithm.

The actual degree of security achieved over time varies, as more
 computational power and more powerful mathematical analytic methods
 become available. For this reason cryptologists tend to look at
 indicators that an algorithm or key length shows signs of potential
 vulnerability, to move to longer key sizes or more difficult
 algorithms. For example, as of May 2007, a 1039 bit integer was
 factored with the special number field sieve using 400 computers over
 11 months. The factored number was of a special form; the special
 number field sieve cannot be used on RSA keys. The computation is
 roughly equivalent to breaking a 700 bit RSA key. However, this might
 be an advance warning that 1024 bit RSA used in secure online commerce
 should be deprecated, since they may become breakable in the near
 future. Cryptography professor Arjen Lenstra observed that "Last time,
 it took nine years for us to generalize from a special to a
 nonspecial, hard-to-factor number" and when asked whether 1024-bit RSA
 keys are dead, said: "The answer to that question is an unqualified
 yes."

The 2015 Logjam attack revealed additional dangers in using
 Diffie-Helman key exchange when only one or a few common 1024-bit or
 smaller prime moduli are in use. This common practice allows large
 amounts of communications to be compromised at the expense of
 attacking a small number of primes.

Acording to this Wiki Page

Also here are some more links to visit if you want to learn more about asymmetric cryptography:

asymmetric cryptography (public key cryptography)

Elliptic-curve cryptography

Elliptic-curve Cryptography Key Sizes

This 3rd link for Key Sizes is where it gets into some pretty complex methods, but if you really want to know Key length / sizes, then you will want to review that section.


Is Poly1305 an information-theoretically secure MAC?

Can the $AES_k(n)$ portion be simply replaced with $k \oplus n$?

No, but you're close, it would be replaced with $k + n$, where $+$ is addition modulo $2^{128}$; then it becomes informational theoretic.

Here's why: Poly1305 is based on a polynomial universal hash.  This is a hash where we select a finite field $GF(p^i)$, select a private value $x \in GF(p^i)$, interpret the message being authenticated as a series of value $m_a, m_{a-1}, ..., m_1$, and compute the value:

$$m_a x^a + m_{a-1} x^{a-1} + ... + m_1 x^1 + f(k)$$

where the above additions and multiplications are done in $GF(p^i)$, and $f(k)$ is the 'unknown encrypted nonce' ($AES_k(n)$ in the Poly1305, $k$ in your case).

The idea here is if someone is able to find a second message and tag that authentications with the same nonce, then we can 'subtract' the two polynomials, and find a polynomial in $x$ that evaluates to 0.  And because $GF(p^i)$ is a field, that polynomial has no more than $a$ zeros; that is, unless $x$ is one of $a$ out of $p^i$ possible values, that polynomial won't be zero).

Now, with Poly1305, they use the values $p = 2^{130}-5$ and $i = 1$.  What this means is that the operation that adds $k$ is not bitwise xor; instead, it is modular addition.  Now, the above proof assumes that the addition is actually modulo $2^{130}-5$, not $2^{128}$; it turns out that it isn't hard to show that this increases the possible number of 0's by a relatively small factor.  I don't know of any corresponding proof if you replace the addition with xor, and hence using xor would appear to be foolhardy.


What is the difference between LCG and Affine cipher?

A LCG -- linear congruential generator -- is used to generate a sequence of pseudorandom numbers. Therefore, it takes the previous output to calculate a new number:

yi = (a*yi-1+c) mod N

With an Affine cipher, in contrast, you can encrypt and decrypt. You can convert your text to a number; for example, character for character "A"->0 "B"->1... "Z"-> 25

To encrypt a message m you use the following formula:

c = (a*m + b) mod N


Security of Fernet Construction (wrt non self delimiting tokens and HMAC short key size)

The spec states that

  Fernet tokens are not self-delimiting. It is assumed that the transport will provide a means of finding the length of each complete fernet token.

Does this allow us to tamper with the tokens in a way we shouldn't be able to by adding data to the front or the end of a token? My intuition says no as HMAC is computed over all the data and the composition is Encrypt-then-MAC.

HMAC is not vulnerable to length extension attacks, and prefixing or removing data from the start of end should indeed result in a different HMAC (assuming that the HMAC is indeed over that part of the data).

Is there any danger in computing HMAC (with SHA256 as the underlying hash function) using only a 128 bit key? My understanding is that the standard key size would be 256 bits in this case.

No, HMAC is surprisingly resilient and has been defined for smaller key sizes. 256 bits key would give you (at least) a 256 bits of security, but 128 bits is plenty.

Note that this answer tries to answer the given questions directly, rather than to perform a full review of Fernet. Note that Fernet has gone through several revisions by now; please check if the questions / answers are still valid.


You could throw away bits of the encryption key so that there is a brute-force portion to decrypting e.g. encrypt with a 128-bit key but only share 96 bits.

Or protect the key using something like an RSA time-lock puzzle. The benefit of this is recovering the key cannot be sped up with parallelism.


You cannot encrypt a file with a private key. With RSA, that's not because of any technical obstacle (with other schemes private keys literally are not valid inputs to the encryption function), but because private keys are designated as "private" and using them in an encryption operation compromises the security of that message. To prove you wrote the message, you don't encrypt it with your private key.

What you do do is sign the message. Signatures take a private key; best practices are to use a different keypair for signatures than for encryption (a default GPG "keypair" is really at two keypairs; there's a master keypair that's tied to your identity which is used only for signing, and a different subordinate keypair which is signed with the master keypair and which is used only for encryption). If you use different keys for signing and encryption, there are no issues with compromising your encryption.

Signing with RSA is not "encrypt with the private key." It has a passing resemblance to that (as the primitive used for encryption, the one for signing, the one for decryption, and the one for verification are all the same operation with different inputs and outputs) but it is a conceptually distinct algorithm which is designed not to let someone with the signature recover the message.

An RSA signature is created by creating a preimage-resistant hash of the message, doing various operations (known as padding) to the hash value to increase security, and passing it through the signature primitive (raising it to the power of the private exponent modulo $n$). In the more modern signature padding algorithm (PSS), the hash of the message is itself not recoverable, because it is combined with a random salt and passed through another preimage-resistant hash, and that is part of what's passed to the signature primitive (the other part is the salt, obfuscated using the hash of the hash+salt). In the older system (PKCS 1.5 padding), the hash could be directly recovered, but as it's preimage-resistant that doesn't give much help to an attacker looking for the message. An attacker in either case can test whether a given message was the one sent, but they can't find the message if they don't already have a candidate message.


What is the correct format for a CRLF in a SSL certificate's pem

No, x509: certificate signed by unknown authority shows that the certificate of the Certificate Authority or one of the intermediate certificates issued by it is not present at the other party. It could be that the certificate is very new and it hasn't yet been taken into account, or that the certificate was not received or accepted by the parties you mention. Even more likely is that an intermediate certificate is missing so that the chain to a trusted certificate cannot be made.

To look up the certificates above it the certificates look up the issuer certificate which is referenced by the certificate you send them. Then using that certificate the next certificate is looked up. Finally the signatures within the certificates are verified and the other information (validity period etc.) are validated. This is called chain validation. This ends with a trusted certificate, often the self signed root certificate of the CA.

Obviously to even try to look up the "parent" certificate the certificate must first be parsed. You'd expect another error if the certificate could not be parsed at all.

As for the carriage return: openssl returns only a line-feed character - as most unix utilities probably will. But any implementation that doesn't accept CRLF or even just CR (for Apple) will be in serious trouble, so I don't think you'll find many libraries / applications that won't accept any kind of line ending (and certainly not Amazon etc.).


How to make a hypothesis test for a simple statistical test for a certain RNG?

The number of one bits in a sequence of iid Bernoulli trials won't be normal: it will be binomial.  But you have the right intuition that, as the number of bits grows, the binomial distribution converges to a normal distribution—specifically, for fixed $p$, as $n \to \infty$, $$\operatorname{Binom}(n, p) \to \mathcal N\bigl(np, np(1 - p)\bigr),$$ or, more precisely and with less abuse of notation, if $X_n \sim \operatorname{Binom}(n, p)$, then $(X_n - np)/\sqrt{np(1 - p)} \to Z$ where $Z \sim \mathcal N(0, 1)$ is a standard normal.  This is a standard theorem of probability theory, the de Moivre–Laplace theorem; see, e.g., Feller, Vol. I, Ch. VII, ‘The Normal Approximation to the Binomial Distribution’, for an introduction.

That said, once you have decided on your test statistic and cutoff for a prescribed false alarm rate (‘statistical significance’), your job is not done: you should also have alternative hypotheses for the bugs you might have in your software, or physical defects you might have in your hardware.  For instance, will you detect deterministic alternating 0/1 bits?

The hypothesis test is valuable only insofar as it distinguishes plausible nonuniform distributions from uniform ones.  After all, if all you want is a hypothesis test with statistical significance 0.05 like any good little psychology journal, you could ignore the data altogether, roll a d20, and raise an alarm if you rolled a 1.

If you're talking about a pseudorandom generator, which is a deterministic function of a key, then your hypothesis test should be designed with knowledge of the function.
If you're talking about a hardware entropy source, which is a physical process, then your hypothesis test should be designed with knowledge of the physics.

If you just count bits and apply a test for goodness-of-fit in terms of the ratio of zeros to ones with significance level 0.05, and stop there, you've only made an entertaining way to implement a d20 in software.


At the end of Section 2 of the lecture notes that you cite, it explicitly states "We note that an analogue of this result holds for uniform distinguishers and predictors, provided that we change the definition of next-bit predictor to involve a random choice of $i \leftarrow R [n]$ instead of a fixed value of $i$, and change the time bounds in the conclusions to be $t − O(n)$ rather than $t − O(1)$ and $t$ (we can’t do tricks like in the final paragraph of the proof). In contrast to the multiple-sample indistinguishability result from last time, this result does not need $X$ to be efficiently samplable for the uniform version."


Back up an information as $n$ pieces and require exactly $n-1$ to recover it

What you describe is known as Threshold-secret-sharing, for which a good candidate is the threshold version of shamir-secret-sharing.
In particular, for your use case I would recommend implementing an "n-1 out of n threshold sharing scheme".

Shamir Secret Sharing $(n,k)$-threshold scheme.
Shamir's $k$ of $n$ threshold sharing scheme is based on the observation that a $k-1$ polynomial over a field is determined by $k$ points, and yet cannot be determined with fewer than $k$ points. If we let $k=n$ then this reduces to Shamir's original sharing scheme.

Choose $q$ such that $\mathbb F_q$ be a finite field (the size of $q$ will specify how secure the scheme is).
Sample $a_1,\dots,a_{k-1}$ uniformly from $\mathbb F_q$.
Let $a_0=s$ be the secret you wish to share.
Let $f(x)=\sum_{i=0}^{k-1} a_i x^i$.
For each of the $n$ people, let share $i$ be the pair $(i,f(i))$.

To decrypt, we use polynomial interpolation to reconstruct the polynomial $f$, which requires at least $k$ shares, and then simply read off the coefficient $a_0$.
Security:
No information about the $a_0$ coefficient is leaked until the polynomial is completely recovered, the scheme is informationally secure. As such, the size of the finite field will be the same as the security margin presented, because the best attack will be to directly guess the secret. nb: This assumes that an adversary must treat the secret as if it were uniformly sampled from all possible field elements - obviously if your secret $s\in\{0,1\}$ your security is bounded by that!


What is the complexity to break second preimage resistance?

The right terminology is second preimage resistance and preimage resistance.

Edited to reflect comment by otus. Preimage attack takes $O(2^{n})$ hash function calls on average.

Second preimage attack takes just one extra call so the complexity is essentially the same as that of the preimage attack. Given $x$ you want $x'\neq x$ such that $H(x)=H(x').$ So evaluate $H(x)$ for one extra query, and then apply the preimage attack to $y=H(x).$


Converting a 5-bit s-box to its bit-sliced format

A recent paper presented at FSE'2016 [1] addresses this exact question. In fact, it even provides a bitsliced implementation for the S-Box you are interested in Section 4.

In summary: you first encode the existence of a bitsliced implementation as a SAT problem, use an off-th-shelf SAT-solver to solve it and finally retrieve the bitsliced encoding from the output of the SAT-solver.

[1]: http://eprint.iacr.org/2016/198.pdf "Optimizing S-box Implementations for Several Criteria using SAT Solvers", Ko Stoffelen, Proceedings of Fast Software Encryption 2016


DSS security in comparison to ECDSA or RSA

As noted in comments, DSS strictly means the Digital Signature Standard, a document (FIPS 186) published by NIST, a part of the US government. The original version of FIPS 186 in 1994 defined (and was the original definition of) a single algorithm, DSA the Digital Signature Algorithm. Later versions of FIPS 186 added other algorithms primarily by reference to definitions elsewhere: RSA from X9.31 and later PKCS1, ECDSA from X9.62 (and SEC1). So technically DSS is now ambiguous as an algorithm identification, but quite a few standards including SSL (now TLS) were set using 'DSS' when it actually meant DSA and those names still survive because it would be a huge hassle to change them and everyone who matters knows what is meant.

In principle both DSA and ECDSA rely on the difficulty of finding discrete logarithms (or equivalently the one-way-ness of exponentiation) in appropriately structured finite groups. For DSA this group is a generated subgroup of the multiplicative group of integers modulo a large prime, notated $Z_p^*$. For ECDSA it is a subgroup (often 'improper' = the whole group) using 'addition' of points on a suitable elliptic curve over a suitable finite field -- either a 'prime' curve over $F_p$ represented/implemented as integers modulo p ($Z_p$) or a 'characteristic two' or 'binary' curve over $F_{2^m}$ represented as binary polymonials modulo a given irreducible polynomial. Although the point operation is usually notated as addition and the curve operation as scalar multiplication, these operations are not ordinary arithmetic addition and multiplication.

Although in abstract the same, there are practical differences due to the size and resulting strength of the 'parameters' used.

The original versions of FIPS 186 specified that p, the prime defining $Z_p^*$, should be 512 to 1024 bits in steps of 64 bits only, and the subgroup size $q$ only 160 bits. These sizes were sufficient in the 1990s, but as the 2000s passed they no longer provided sufficient margin of safety. FIPS 186-3 in 2009 belatedly increased standard sizes of p to 2048 and 3072 bits and q to 224 and 256, but it took some time for implementations to follow; as one notable example, Java 7 was supported until 2015 (and appears to still be in use today from Qs in stackoverflow and similar places) and limits p in DSA (and also DH!) to 1024 bits.

RSA similarly needs larger sizes now than it did in the 1980s and 1990s, but the standards for RSA never set a fixed maximum and most implementations allowed some (often a lot) of leeway. Thus when most standards and authorities -- and especially SSL/TLS CAs -- began requiring RSA-2048 instead of RSA-1024 in or soon after 2014, a lot of people had to generate new keys and certs but did NOT need to change their software (at least not for this reason).

In contrast ECDSA was initially defined with curves covering a range of sizes up to 500+ bits with strengths up to 250+ bits, and NSA adopted two of them (P-256 and P-384) in its Suite B, so practically everybody began using those two (or at least the first) which are strong enough.

As a result in general you can assume that if ECDSA (or ECDH) is used at all it is probably used with sufficiently strong parameters, whereas you can't always make this assumption for DSA and RSA. However for OpenSSL this is usually not a problem; due perhaps to lucky timing OpenSSL 1.0.0 was released in 2010 and included the increased FIPS 186-3 sizes, so unless you're on a really old system stuck at 0.9.x you're okay.

Another feature/limitation of both DSA and ECDSA is that they require each signature to use a nonrepeating and at least nominally random value (a nonce), and if you do repeat a value an adversary can easily recover your private key and forge signatures, which is Bad. There are proposals to change this including by our very own bear but not much progress yet. RSA signatures do not strictly require randomization, and the most-common (mostly because oldest) scheme RSASSA-PKCS1v1_5 does not use it at all (after key generation, which does require good randomness but is done rarely).

FWIW a similar naming issue occured with DES, which formally was the Data Encryption Standard document FIPS 46 from what was then NBS, and defined a single algorithm DEA the Data Encryption Algorithm (modified from IBM's Lucifer). As time passed and 56-bit keys became too short -- or at least more visibly too short -- the document FIPS 46 (DES) was revised to include TDEA the Triple Data Encryption Algorithm which many people called (and still call) Triple-DES even though it was not a separate standard. Then after AES (document) FIPS 197 was published defining AEA (algorithm, a profile of Rindael) FIPS 46 was withdrawn and TDEA (but NOT DEA) was republished as a Special Publication which is formally not a standard and thus formally DES and Triple-DES no longer exist. But both people and software and documents written in the past still refer to them, and many (like some SSL/TLS ciphersuites and OpenSSL, and also Java crypto) refer to TDEA as DESEDE or DES-EDE, sometimes with 3 attached somewhere, which were basically the nicknames used during a discussion period before TDEA was standardized; this is because both encrypt-decrypt-encrypt (EDE) and encrypt-encrypt-encrypt (EEE) constructions were seriously considered before the former was chosen.


Commutative homomorphic encryption for zero-knowledge transfers

Your protocol won't work if the encryption scheme is randomized. In fact, the commutative property would be that $D(D(x,priv_a),priv_b)=D(D(x,priv_b),priv_a)$, which is different than $E(E(x,pub_a),pub_b)=E(E(x,pub_b),pub_a)$.

A deterministic encryption scheme cannot be semantically secure. So if a scheme could meet the requirements to be used in this protocol, it wouldn't have the security guarantees you would want from an encryption scheme.

This is not to mention that $*$ could also be non-deterministic.


The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least $B$ bytes of memory.  Basically, the server gives the client a function $f$ that requires at least $B$ bytes to compute, and the client proves it can compute $f$.  The method is complicated and I haven't absorbed all of the machinery.

One of the lead developers of Bitcoin has proposed a different scheme, which allows the client to prove that it is "tieing up" a certain amount of space over time.  The server can periodically send the client a challenge; if the client can always respond correctly, this proves that the client must have set aside that much space.

The idea behind the latter scheme is not too complex.  Basically, we form a GGM hash tree: for a complete binary tree of depth $d$, with a random 160-bit seed at the root, and then recursively label all of the nodes of the tree as follows: if a node has label $x$, then its left child has label $H(x||0)$ and its right child has label $H(x||1)$, where $H$ is a cryptographic hash function.  There are $2^d$ leaves.  Each leaf can be thought of as a pair $(i,x)$, where $i \in \{0,1\}^d$ is the index of the leaf (a binary string indicating the path taken from the root to that leaf) and $x$ is the label on that leaf.  Now sort these pairs on their $x$-values.

At any point, the server can challenge the client by picking a random index $i$, computing the label $x$ on that leaf (this takes just $d$ evaluations of $H$, and can be done by the server, since $H$ is publicly known), sending $x$ to the client, and asking the client to send back the corresponding index.  If the client has been tying up enough space to store all $2^d$ records, it can quickly find the corresponding $(i,x)$ pair and send back the correct value of $i$; if it hasn't, it will find it difficult to respond correctly.


How would Private-key Cryptography be if we use quadratic polynomials as OWF's?

You might look at the stream cipher QUAD invented by Berbain, Gilbert, and Patarin.

It uses the complexity of a multivariate quadratic map as the basis for its security. A drawback of this and other multivariate quadratic map crypto systems is the space needed to store a large random quadratic map.


Simplified Example of ECC to use in the classroom

In short: the question does not explain well the notion of asymmetry in ECC; and the exposition is not how Elliptic Curve Cryptography works. A reasoning sidestepping the notion of Discrete Logarithm Problem over a finite group can not really explain asymmetry as meant in ECC.

Asymmetry is in the knowledge Alice and Bob have about the key, not asymmetry of a curve, or even asymmetry in variables in the equation, or different forms of the curve's equation. Foremost, ECC does not work as explained. Among discrepancies:

The variables in the "curve" are on discrete sets like $\mathbb Z_p$ or $\mathbb Z_{2^k}$, not real numbers $\mathbb R$; that makes a hell of a difference to the appearance of the "plot" of a curve with a given equation. A plot using real variables is traditionally used to illustrate how the group law is built; but (since a curve is with real variables, and it is used discrete ones in actual use) this is not how things are actually being used in ECC. Update: The Ars Technica article (page 2) quoted in comment does a good job explaining this.
The curve/equation is there to define an appropriate finite group (typically: where the Discrete Logarithm Problem is hard), and the actual crypto is built on top of that. There's no viable exposition of ECC (that I know) short of building that finite group structure. Update: the Ars Technica article does not even mention group, or associativity of the "dot" law.
Typically, the asymmetry lies in the difficulty of

computing $G+G+\dots+G$ repeated $k$ times in the group defined by the curve, which is easy;
finding $k$ from $kG$ (that is, $G+G+\dots+G$ repeated $k$ times), which is believed intractable.

ECC encryption schemes (that I know) do not work as stated in the question. In particular $k$ is not a message, but is the private key; $kG$ is the public key, and is unrelated to the message. That's perhaps because the Ars Technica article does not explain ECC encryption (it introduces asymmetric encryption using RSA in a very naive setup, but there's no viable transposition of that to ECC).

In order to introduce "how ECC relates to asymmetric keys" to a classroom (if that must be done for some reason), I suggest:

introducing post-symmetric cryptography with Diffie-Hellman key exchange, defined on a finite group initially illustrated by the relatively familiar $\mathbb Z_p^*$, because that's by far the simplest example;
probably, using as the defining problem for asymmetric cryptography signature (illustrated by El Gamal signature or its common variant DSA) rather than encryption (illustrated by El Gamal encryption), because the former is simpler;
showing that an appropriate Elliptic Curve equation over a (finite commutative field) can be be used to define a finite group usable for the above purposes;
stating that this is computationally attractive for a given security level, hence the growing interest in ECC (a true justification requires examining the running time of various known algorithms for solving the DLP, as well as introducing as competitor factorization-based asymmetric cryptography, probably RSA).


Are modified implementations of cryptographic algorithms a good idea?

No, modified algorithms they are unlikely to be harder to break, unless the changes were explicitly made by a cryptographer to make the algorithm more secure. They are certainly not any safer just because they are different.

Due to the Kerckhoff principle you should assume that the algorithm is known. So changes in the algorithm in itself does not increase security;
If there is a trivial change made then all the attacks on the algorithms are still valid;
If it is a non-trivial change then the algorithm requires a new security description or proof; basically it should be treated as a new algorithm.

Now in the latter case the algorithm could be safer of course, and many parts of the original security proof may hold. There are many algorithms that have been tweaked to a certain extend to make them more safe or more functional, often by their original authors. As example, for SHA-1 the original, untweaked variant called SHA-0 can be found in the wild.

But to change an algorithm without an explicit idea to fix the previous algorithm is not likely to make it more secure. Most of the time the algorithm will be less secure.

Note that even minor changes in the vectors (internal constants) of symmetric algorithms may completely destroy the security of algorithms. Often these tables were specifically created for the purpose of adding security. If you change one constant in there, you may already break security. Other specific constants may be as safe or even slightly more safe (see for example the changes made by the authors to many of the SHA-3 contestants). In other words, small changes may not equate to trivial changes.

If you change for instance the SHA-2 vectors of SHA-256 to a new, secure set, the you may make it harder to use rainbow tables. But if you use SHA-2 correctly then rainbow tables should not be an issue (because of using salt for password based key derivation). In this way, for very specific attack scenarios, using a modified algorithm may bring some localized benefit. But in general it would be wiser to change the key derivation primitive, of course.


How does TLS with PQC use key encapsulation?

As there don't seem to be any PQC alternatives for Diffie-Hellman (DH / ECDH), DH must have been replaced by key encapsulation using an ephemeral key pair.

I don't believe that is correct; a postquantum Key Encapsulation Method (KEM) would appear to be the natural replacement for DH/ECDH within TLS.  In the KEM, one side (the client) produces a KEM public key, the other side (the server) produces a response, and they both generate a 'shared secret'; this is what TLS 1.3 needs.
Now, the server can't have a static key (because, unlike DH, the server response depends on the client public key).  On the other hand, TLS 1.3 currently doesn't assume that.
All of the NIST public encryption candidates can work like this; except for the ones that make it problematic by having huge key sizes, they all can fit within the current TLS 1.3 architecture.


RSA assumption and relationship given by generating elemts of a Cayley graph

For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle?

It looks like it shouldn't. I'm pretty sure I was visualizing cycles in the Cayley Graph as being paths in the lattice $\mathbb{Z}^2$. This corresponds to viewing points in the RSA group as tuples $(g_p^{r_p}, g_q^{r_q})$ (where $(r_p, r_q)\in\mathbb{Z}^2$). One could hope to make some statement about maximum elements in this representation relating to maximum length cycles, but this is different than the congruences mentioned.
One could maybe hope to prove some statement about maximal elements in the above representation $(r_p, r_q)$, and then transfer (via exponentiation) to the "standard representation" and hope that they are "close to maximal". I would strongly expect this to be false though --- this property would be akin to being something like Lipschitz normally, which is much more regularity than I'd expect from these functions.

Can we write other groups such as $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$, where $p, q$ are odd distinct primes, in terms of a free group as above? I am very glad if some guidance/steps to do so can be explained.

For $G\rtimes_\varphi H$ I explicitly include the homomorphism $\varphi : H \to \mathsf{Aut}(G)$ that the semi-direct product is defined with respect to.
The concept you're looking for is that of a group presentation.
This is a way of writing a group $G$ as a set of generators $R$ and relations $S$ the generators satisfy (denoted $\langle R | S\rangle$).
Equivalently, this is a way of writing a group $G$ as a free group on the generators $R$, quotiented by the normal subgroup generated by the relations $S$.
In this terminology, your question becomes "What is a group presentation of $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$?"
It will be useful to know how group presentations behave under direct products and semi-direct products.

Let $G_1 = \langle R_1 | S_1\rangle$ and $G_2 = \langle R_2 | S_2\rangle$. Then:

$G_1 \times G_2 = \langle R_1, R_2 | S_1, S_2, [R_1, R_2]\rangle$

$G_1\rtimes_\varphi G_2 =\langle R_1, R_2 | S_1 , S_2, \forall (r_1, r_2)\in R_1\times R_2 : r_2 r_1^{-1}r_2 = \varphi(r_2)(r_1)\rangle$

Here $[A, B]$ is the commutator subgroup.
One should be able to use the above "transformation rules" (along with the presentation $\mathbb{Z}_p = \langle g | g^p = e\rangle$ for prime $p$) to compute a group presentation for the group you're interested in (or any other group built from direct and semi-direct products of cyclic groups).


Can multiple Pearson permutation tables be reduced or merged?

Claim: A $\pi$ permutation table can be found such that applying it to a message $m$ will yield the same output as applying multiple, different permutations to that message $m$.

i.e. For any number of permutation steps $\phi_n$, $m_{initial}\rightarrow\phi_1\rightarrow\phi_2\rightarrow...\rightarrow\phi_n\rightarrow m_{permuted}$

$\exists$ a single permutation $\pi$ such that: $m_{initial}\rightarrow\pi\rightarrow m_{permuted}$

Where both $m_{permuted}$'s are identical.

Proof:

Assume we have two permutation tables, $\phi_1$ and $\phi_2$ s.t.

$\phi_1=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    a & b & c & d
\end{bmatrix} $
$\phi_2=
\begin{bmatrix}
    m_{1\phi_1} & m_{2\phi_1} & m_{3\phi_1} & m_{4\phi_1} \\
    e & f & g & h
\end{bmatrix} $

Where the first row contains the input broken into bits and the second row contains the positions that each bit will be mapped to. (For $\phi_2$ notice that each bit of $m$ is now $m_{0\phi_1}$, indicating that it is the first bit of the message after being permuted by $\phi_1$). For example:

$
m=3512
$

\begin{bmatrix}
    3 & 5 & 1 & 2 \\
    4 & 2 & 3 & 1
\end{bmatrix}

yields a $m_{permuted}=2513$, and then this new permuted message can be permuted again (as many times as desired).

Right, so back to our earlier example using $m$, $\phi$, and $a,b,c,...$.

Going through the first permutation, we will have the message $m_{\phi_1}=m_{a}m_{b}m_{c}m_{d}$

Going through the second permutation, we will have the message
$m_{\phi_2}=m_em_fm_gm_h$

So, it is sufficient to find a permutation matrix that directly maps $m_1,m_2$ etc. to the locations that $m_1,m_2,...$ end up in the final permutation matrix. Finding such a permutation matrix is quite simple, as you can pass a message $m$ through the multiple permutations $\phi_n$, observe where they end up, and create the mapping based on that. This is best illustrated by and example, but proof by example is not acceptable, so I added the other info in before this. Also note that this works for any size of $m$ assuming the permutation has mappings that include all bits in $m$ (So each bit gets assigned a new place).

Example:

$m=m_1m_2m_3m_4$

$\rightarrow$$\phi_1=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    3 & 2 & 4 & 1
\end{bmatrix} $$\rightarrow m_{\phi_1}=m_3m_2m_4m_1$

$\rightarrow$$\phi_2=
\begin{bmatrix}
    m_{3} & m_{2} & m_{4} & m_{1} \\
    4 & 2 & 3 & 1
\end{bmatrix} $$\rightarrow m_{\phi_2}=m_1m_2m_4m_3$

$\therefore$ It is sufficient to have a permutation table to complete the mapping $m_1m_2m_3m_4 \rightarrow m_1m_2m_4m_3$

This matrix is
$\pi=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    1 & 2 & 4 & 3
\end{bmatrix} $$\rightarrow \pi(m)=m_1m_2m_4m_3$

And $\phi_2(\phi_1(m))=\pi(m)$


Exactly what RNG weaknesses endanger (EC)DSA?

It is well known and trivial to show that if the same random $k$ is used in two different signatures, then the secret key can be extracted. In particular, you have two signatures $(r,s_1)$ and $(r,s_2)$--the $r$ is the same since it is a deterministic function of $k$--where $s_1=k^{-1}\cdot(H(m_1)+x\cdot r) \bmod q$ and $s_2=k^{-1}\cdot(H(m_2)+x\cdot r) \bmod q$. Computing $d = \frac{s_1}{s_2} \bmod q$ one obtains $d = \frac{H(m_1) + r\cdot x}{H(m_2) + r\cdot x} \bmod q$, and so $(d-1)\cdot r \cdot x = H(m_1) - d \cdot H(m_2)$ yielding $x = \frac{H(m_1)-d\cdot H(m_2)}{(d-1)\cdot r} \bmod q$.

One could think that this type of thing only happens if the exact same $k$ is used twice. However, if two $k$'s are related in some way, then the same thing can happen. This was shown in an interesting way in the paper Pseudorandom Generation in Cryptographic Algorithms: The DSS Case by Bellare, Goldwasser and Micciancio.

The above paper assumes a strong relation between the nonces. However, the point is that if the same nonce reveals the key, and if knowledge of the nonce reveals the key (trivial to show), then biases in the nonce can reveal information about the key. One would then need more signatures, but this can be done. This is shown in GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures With Single-Bit Nonce Bias.


How is de-synchronisation of HOTP solved?

The usual resynchronization method involves getting several consecutive codes from the token and then running the algorithm once with a very large look-ahead window until the set of consecutive codes are found. The number of consecutive codes needed depends on how far off the token is.

With a typical token, two codes would suffice to handle a desynch of 200. Many HOTP systems will simply ask you for a second code and fix a desynch of less than 500 codes or so by themselves.


Stream cipher with an additional integrity stream?

Break your stream into chunks.  Use an AEAD for each chunk using the chunk sequence number as a nonce.  Anything else is going to have at best the same effect, but will be convoluted, full of holes for the first umpteen drafts, difficult to implement, and nonstandard, and will have the effect of making cryptographers look at you like you have three heads.

Or, use a system that was already designed to do this (in particular, STREAM).


Re-negotiation may happen in the middle of existing session, "session
  ticked" or "session Id" are not required to find "current state
  parameters", just 5 tuple may be used to look for proper running
  session context.

Yes.

  [...]BUT ClientHello message itself is encrypted. How this is solved for
  TLS1.2 ?

The ClientHello on an abbreviated handshake is in fact not encrypted. The message flow for an abbreviated handshake goes roughly as follows: Client sends unencrypted ClientHello, Server responds with ServerHello, ChangeCipherSpec and Finished message and client answers with ChangeCipherSpec and Finished message and application data. Also see page 37 of RFC 5246.

  in both cases client-server dialog follow abbreviated Handshake

No, only for session resumption the abbreviated handshake is used, for renegotiation a full handshake is performed.

  In opposite resumption may happen even after actual connection has
  been closed

Yes.

  In context of TLS1.3 renegotiation is done now using KeyUpdate message
  and clearly described by draft, but resumption has the same issues.
  How resumption is solved for TLS1.3 ?

Section 2.2 of the TLS 1.3 draft (-23) talks about the session resumption protocol flow. Section 4.6.1 talks about how the ticket mechanism works in detail. Section 4.2.11 talks about how the tickets are used in the Hello Messages. It turns out that the client may offer the server multiple PSK identities in the (cleartext!) ClientHello of which the server selects and thus "consumes" at most one and indicates which in its ServerHello message.


I believe that the python built-in pow(g, p/2, n) does what you want fairly quickly...


I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem.

The first observation is that if you know the group order $n$ and a group generator $g$, that this problem can be reduced to $2i$ discrete log problems with the same base; if we find the values $y_a, z_a$ such that $g^{y_a} = g_a$, $g^{z_a} = h_a$, then we know $x_a = y_a^{-1} z_a \bmod n$.

So, here is how we can use Baby-Step/Giant-Step to solve all $2i$ discrete log problems in $O(\sqrt{in})$ time:

Let $t$ be the integer closest to $\sqrt{2in}$
Compute the $t$ values $g^j$, for $0 \le j < t$, and store those values in a hash table.
For each $g_a, h_a$ value, compute the $n/t$ values $g_ag^{-tk}$ for $0 \le k < n/t$.  Look up each value in the hash table; when we find $g_ag^{-tk} = g^j$, we know $g_a = g^{tk + j}$

The first step involves computing $t = O(\sqrt{in})$ values, and hence takes $O(\sqrt{in})$ time.  The second step involves iterating over $2i = O(i)$ variables, each iteration involving $n/t = O(\sqrt{n/i})$ time, for a total of $O(\sqrt{in})$ time.

Now, this gives an answer to the question from a theoretical standpoint ("yes, there do exist ways where we can take advantage of multiple subproblems"), however, it's not very interesting from a practical basis -- groups small enough for Baby-step/Giant-step to be a threat are too small to give real security.


What information is revealed if we send our points in Projective Coordinates?

The danger of revealing results in protective coordinates is pointed by David Naccache, Nigel P. Smart, and Jacques Stern's Projective Coordinates Leak, in proceedings of Eurocrypt 2004. As noted in comment, a concise re-exposition is in section 3 of Alejandro C. Aldaya, Cesar P. García and Billy B. Brumley's From A to Z: Projective coordinates leakage in the wild, in proceedings of CHES 2020 (which uses it in side-channel leakage attacks on implementations using projective coordinates internally, even when the result is output in affine coordinates).
In a nutshell: revealing $[k]\,G$ in projective coordinates can leak some information about $k$; that's problematic.

Slightly more detail: in affine coordinates, a point (other than the point at infinity) is expressed as $(x,y)$ satisfying the curve equation $y^2=x^3+a\,x+b$, where $x$ and $y$ are field elements. In standard projective coordinates, the same point is expressed as $(X,Y,Z)=(Z\,x,Z\,y,Z)$, where $Z$ is any non-zero field element. That becomes $(X,Y,Z)=(Z^2\,x,Z^3\,y,Z)$ in Jacobian projective coordinates.
Therefore giving a point in projective coordinate gives the point, and an extra information $Z$ that can be any non-zero field element. That $Z$ depends on how the point was obtained, and is a potential information leak.

More in detail: Assume that it is given $P=[k]\,G$ with unknown $k\in[1,n)$ as projective coordinates $(X_P,Y_P,Z_P)$, and that was computed starting from a known $G$ of projective coordinates $X_G,Y_G,Z_G=(x_g,y,g,1)$, and integer $k$, using standard formulas for point addition and point doubling, and the straightforward left-to-right exponent scanning algorithm:

$P\gets G$
for each bit $b$ of $k$ from second high-order to low-order

$P\gets P+P$ (point doubling)
if bit $b$ is set

$P\gets P+G$ (point addition)

It turns out that there is a relation between $k$ and the final $Z_P$, and that relation is exploitable to get some information on $k$.
[I started summarizing the first article, but did not finish, sorry. Feel free to expand!]


The exact difference between a permutation and a substitution

As noted in this answer and this answer to another question, permutation is just a mathematical term for a function $\sigma:X{\rightarrow}X$ that maps a finite set $X$ onto itself, in such way that for each $y \in X$ there exists exactly one $x \in X$ such that $\sigma(x) = y$. This is also equivalent to how the term substitution is used in cryptography, so your question is indeed justified.

For instance, the term Pseudo Random Permutation denotes a function that might also have been described as a Pseudo Random Substitution (but never is).

As D.W. pointed out in a comment below, the terms P-boxes (permutation boxes) and S-boxes (substitution boxes) have a specific meaning in block cipher design. Suppose you have a P-box and a S-box that both map a bit-string of length $n$ to another bit-string of length $n$. In such case the P-box can be expressed as a function $\sigma:[0..n-1]\rightarrow[0..n-1]$ that maps one index in the bit string to another, while the S-box, simply put, does more. This means that there are only $n! = \Pi_{i=1}^ni$ different P-boxes that map one bit string of length $n$ to another, while there are $2^n!-n!$ different S-boxes that map any bit string of length $n$ to another, without being a P-box and without mapping two different inputs to the same output.

Using the term Permutation in the specific meaning described in the above paragraph is unambiguous within the field of block cipher design. However, I would recommend using the term P-box, which, to the best of my knowledge, is never used in a meaning that differs from above.

Why? Well, for instance, a block cipher designer who hypothetically decides to incorporate e.g. the RC4 key schedule for setting up the S-boxes used in a block cipher, would be technically correct to refer to the operation that sets up those S-Box as a "permutation" (because one property of such a S-box might be best understood by looking at the setup in terms of permutation decomposition). The result would clearly not be a P-box, though.

Consequently, the best answer is probably that the distinction must be clear from definitions made in the context where the terms appear. When in doubt, avoid terms that might cause confusion.


I will omit the exact complexities as it is not directly asked, however let me know if you would like me to elaborate on them more.
There are three levels of security for a cryptographic hash function $H$:

Preimage resistance: it is infeasible for an attacker presented with $x$ to find $m$ so that $H(m) = x$.
Second-preimage resistance: it is infeasible for an attacker presented with $m_1$ to find $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.
Collision resistance: it is infeasible for an attacker to find any $m_1$ and $m_2\neq m_1$ so that $H(m_1) = H(m_2)$.

Now to the alternative answers in your quiz:

a. It is impossible to break its resistance to collision and preimage

No, it can not be impossible in theory since an attacker with unlimited resources could brute-force over all possible inputs. The key here is the concept of computational infeasibility.

b. It is more difficult to break its resistance to collision than to the preimage
c. It's just as easy to break your resistance to collision than to preimage
d. It is easier to break its resistance to collision than to preimage

(d.) is the correct answer. Here's why:
For successfully 'breaking' preimage resistance, you get some output hash $x$ and need to find the corresponding input $m$ to that specific $x$. Unless there is a structural flaw in the hash algorithm, the quasi-randomising effect of the hash function dictates that the only way is to brute-force over a lot of different inputs until you find your target input $m$. This is extremely expensive, and intentionally so.
For collisions, you need to find any two distinct inputs $m_1,m_2$ that result in the same output hash. Now again you could choose a brute-force approach and try different inputs until you find a match. However you are not constrained by the fact that your inputs must result in a specific hash, like in both preimage cases. This makes it significantly easier to 'break' collision resistance.


Skein or Keccak stream cipher construction

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure:

In the case of Skein and Keccak it should be secure. However, both of those have defined their own cipher modes which you should IMO prefer. (For speed and compatibility, if not security.)

The Skein one is defined in section 4.10 of the paper. It uses the underlying primitive directly rather than hashing the key and nonce.
For Keccak the web site links to a separate paper on an authenticated encryption mode. It uses the sponge to squeeze a larger number of output bits, like the SHAKE modes of the hash function.

Alternatively, in the case of Keccak/SHA-3 you may want to use one of the SHAKE extendable output functions, which produce an arbitrarily long output stream. They may also be faster than repeated calls to the hash function.

  Is there a particular attack on using the same key for encryption and MAC?

You should make sure the MAC invocation can never match an encryption one. I.e. it is not possible for $K|IV|C$ to match any $K|IV|i$. Easiest would probably be to add a string to make them differ, like $H(K|\text{'E'}|IV|i)$ and $H(K|\text{'A'}|IV|C)$.

In that case the MAC and encryption are independent, and a known or chosen plaintext attack cannot leak any extra MAC values.

Generically, your construction is not necessarily secure. First a hash function doesn't have to be a secure MAC when you prepend the key. Second, a stream cipher must be a PRF, which is a stronger condition than unforgeability for a MAC.

For example, you could define a stupid MAC like: $MAC_k(m)||MAC_k(m)$ and it would be just as strong a MAC as the original, but would make a lousy stream cipher.

(In practice most MACs do seem to also claim to be PRF.)


Why can't I reverse a hash to a possible input?

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction of gates is a function, rather than depending on some internal state. And the number of gates is manageable (perhaps in the order of $n=10^{5\pm1}$ OR gates for the SHA familly and single-block message).

This does give a constructive way to find an input corresponding to a given output, as outlined in the question: try every possible inputs for a gate with an output that's a given output, or has been hypothesized in an earlier step. For NOT, there's only one possible input (the complement of the output). If the output of OR is 0, its inputs are 00. If the output of OR is 1, there are 3 possibilities for its inputs: 01, 10, 11. When a new hypothesis conflicts with an earlier hypothesis (which occurs since inputs of different gates can be connected to the same output), eliminate the new hypothesis. If all new hypothesis for a gate's input(s) are eliminated, eliminate the old hypothesis. When all the circuit is covered, and if there's a possible input, any hypothesis not eliminated gives a possible message input.

That works. But critically: new hypothesis are dependent on earlier ones, thus when we meet an OR gate with a 1 output, it multiplies by 3 our number of hypothesis to keep track of (in a breadth-first approach) or explore later in case of failure (in a depth-first approach). If we examine the maximum number of hypothesis to be examined as a function of the number $n$ of OR gates, it grows as $\mathcal O(c^n)$ for some constant $c$ that can be significantly above 1. Using that a XOR can be built with 3 OR gates (and some NOTs), we have an argument that $c\ge\sqrt[3]2\approx1.26$ for some large portion of some possible circuits (adding a XOR gate on an unknown input transforms it into 2 unknown inputs).

Thus the argument in the question proves that a hash can be reversed with enough effort, but it gives no lower bound for the corresponding effort; and the best bound we know to derive is exponential w.r.t. the gate complexity. It turns out that for hash constructions used in cryptography (e.g. SHA-1 with 160-bit output and 176-bit input), the cost of this method is much higher that trying all possible hash inputs (e.g. $2^{176}$).


Is RSA of a random nonce with no padding safe?

If you pad a 128-bit value $K$ with zeroes to the left, and interpret the value numerically with big-endian convention (as happens in PKCS#1 in general), you end up with a value which is no greater than $2^{128}$. If the public exponent is $e = 3$, then the "encrypted value" is no greater than $2^{768}$, and no actual modular reduction takes place. Consequently, a simple cube root extraction on plain integers reveals $K$.

So, that can be quite unsafe.

What is safe is the following:

you generate a random integer $x$, between $0$ and $n-1$ ($n$ is the RSA modulus);
you encrypt $x$ by simply raising it to the power $e$ modulo $n$;
the encryption key you will use with AES is $h(x)$ for some hash function $h$.

It is still relatively limiting, in that this is safe as long as you do one encryption only of $x$. If you want to "send" your symmetric key $K$ to several recipients (a common model, e.g. for email encryption), then the scheme above does not work, and, more generally, you need some per-encryption randomness inserted (as PKCS#1 does for encryption).


Is it acceptable to add a setup algorithm in the public key encryption?

Yes.

There are a lot of precedents, for example DSA of FIPS 186-4 has a setup algorithm, described in appendix B.1.


Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

Yes.  Such proofs are possible for El Gamal.

It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption.

Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal.  Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is the public key).  Then proving that $a=b$ is equivalent to proving that $a/b=1$, i.e., that $(r,s)=(g^k,h^k)$ for some $k$, or in other words, that $(g,h,r,s)$ is a Diffie-Hellman 4-tuple.  There is a standard zero-knowledge protocol to prove this fact.  That's all you need.


In RSA, given public key $(n,e)$ and $d^e\bmod n$, can we factor $n$?

We can compute the amount of $E=e^{e-1} mod(n)$ then compute $C=c^E=(d^e)^{e^{e-1}}=d^{e^e} mod(n)$. Now we can compute the secret key $d$ as below:
$C^c=(d^{e^e})^{d^e} mod(n)=d^{e^e.d^e}=d^{(e.d)^e}=d^{1^e}=d \mod(n)$


How to detect what crypto-method is used by Filecoder.Q?

Filecoder.Q ransomware used one of three encryption algorithms: XOR ,Tiny Encryption Algorithm(TEA) and AES,but this ransomware does not encrypt beginning of the files so in your picture beginning of original and locked file are equal.if this ransomware uses XOR Algorithm then you can decrypt locked file with XORing original file and locked file(key Extraction) else if it uses TEA Algorithm then decryption of file is hard(but possible),but decryption of file when it uses AES is impossible.


Is there a term for "bootstrapping" encryption by storing an encrypted key?

The random key that encrypts the message is commonly called a Data Encryption Key or DEK using a Data Encryption Mechanism or DEM. If this key is encrypted then it is encrypted using a Key Encryption Key or KEK within a Key Encryption Mechanism or KEM. Instead of "encryption" the term "enveloping" may also be used. An encrypted key is also called a wrapped key and the key that does the wrapping is then called a wrapping key. This just names the keys and lower mechanisms, not the overall scheme.

I'm not sure if there is a single term that is used for for this type of scheme. Usually the scheme is not explicitly mentioned. It is often part of a scheme that specifies a container format such as PGP. PGP however calls the data keys session keys:

  The message is encrypted with a session key, and the session key is
     itself encrypted and stored in the Encrypted Session Key packet or
     the Symmetric-Key Encrypted Session Key packet.

Note that PGP can also directly encrypt using the key derived from the password.

I've heard the term key hierarchy used a lot in this sense. Here the password / derived key is a higher level key than the one encrypting the data itself. Multiple data keys may be encrypted or derived from the password derived key material. So you could say that the file is encrypted using a hierarchy of keys, but you would likely still be required to explain what you mean by that.


Are any of the practical implementations of ORAM being used in a real world system?

In addition to Paul's answer there is even an ORAM module inside a processor architecture, fully implemented: “A secure processor architecture for encrypted computation on untrusted programs”

Abstract:

  This paper considers encrypted computation where the user specifies encrypted inputs to an untrusted program, and the server computes on those encrypted inputs. To this end we propose a secure processor architecture, called Ascend, that guarantees privacy of data when arbitrary programs use the data running in a cloud-like environment (eg, an untrusted server running an untrusted software stack).


Breaking zero knowledge protocol for graph hamiltonicity

The protocol for Hamiltonicity is by Blum and not FLS (FLS indeed use it). The protocol as you presented it is zero-knowledge for a malicious verifier as well. However, it is not known to be zero-knowledge when run in parallel (in order to get negligible soundness error). On the flip side, we also do not know how a dishonest verifier can do anything.

What do we know about the parallel repetition of Hamiltonicity?

First, we know that it is not black-box zero knowledge; see On the Composition of Zero-Knowledge Proof Systems.

Second, it is possible to prove that $log^2 n$ repetitions of the proof is actually zero knowledge in the unlikely case (not believed to be true) that Circuit-SAT on $n$ variables can be solved in time $2^{\sqrt{n}}$. This demonstrates that it would be very hard to prove that this protocol is not zero knowledge, without proving strong lower bounds on CSAT (note one could theoretically prove this under such an assumption, but no one knows how to do this). This proof can be found in Section 8 of Lower Bounds for Non-Black-Box Zero-Knowledge.

Third, we can prove that parallel Hamiltonicity is witness indistinguishable.

Finally, it is clearly honest-verifier zero knowledge.


If you XOR two independent streams of two random number generators together then the result is as strong as the strongest of the two.


The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can even practically prove (or disprove) the primality of an arbitrary 2048-bit integer, using a number of methods, including (as pointed in comment): Daniel J. Bernstein, Proving primality in essentially quartic random time, in Mathematics of Computation 76 (2007), 389–403 (which is a randomized test giving a certainty; only the time it takes to reach certainty depends on the particular randomness used). Or better (as pointed in another comment) APR-CL or ECPP.
However this is complex, and practical cryptography is happy with a simpler probabilistic primality test. Notice that 64 rounds of Miller-Rabin test against a 2048-bit integer one have randomly drawn (which is the case in RSA key generation), rather than received from a potentially hostile party, are way overkill to rule out compositeness with residual odds less than $2^{-128}$; 4 rounds are more than enough, see FIPS 186-4 table C-2, with justification in appendix F and its reference: Ivan Damgard, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, in Mathematics of Computation 61 (1993), 177–194.

If we accidentally try to perform RSA with one of $p$ or $q$ composite (because an error crept in the implementation of the primality test), the usual formulas $\varphi(p\cdot q)=(p-1)\cdot(q-1)$ or $\lambda(p\cdot q)=\operatorname{lcm}(p-1,q-1)$ will lead to an incorrect value, and with overwhelming odds, decryption or signature verification will fail on the first real use (assuming non-malicious choice of $p$ and $q$, and a random message or proper padding is used). In a PKI context, the verification by the certification authority of the public-key certification request (which is customarily self-signed) will almost certainly fail.
That's because successful use of RSA with a random message constitutes a powerful primality test of $p$ and $q$, essentially performing a Fermat test for $p$ and $q$; that is less powerful than a Miller-Rabin test, but still very effective for random $p$ and $q$. However (just as all practical primality tests for large integers), it gives an indication of compositeness, but does not reveal a previously unknown factor; that's where the reasoning/intuition in the question breaks.
More precisely, assume $e$ and $d$ follow the necessary and sufficient condition to be matching public and private exponents in two-primes RSA, that is $e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$.
Equivalently $\exists u\in\mathbb N, e\cdot d=1+u\cdot\operatorname{lcm}(p-1,q-1)$.
By setting $v=\gcd(p-1,q-1)\cdot(q-1)$, we get $e\cdot d=1+u\cdot v\cdot(p-1)$.
Now if for some random $x<N$, we verify that ${(x^e\bmod N)}^d\bmod N=x$ (that is, textbook RSA encryption then decryption for $x$ yields back $x$), by reducing modulo $p$ we see this implies $x^{e\cdot d}\equiv x\pmod p$, thus $x^{1+u\cdot v\cdot(p-1)}\equiv x\pmod p$, thus (except if $\gcd(x,p)\ne1$, which is improbable) ${(x^{u\cdot v})}^{p-1}\equiv 1\pmod p$.
Our RSA encryption/decryption test has performed a Fermat test for $p$ with witness $x^{u\cdot v}\bmod p$, and this witness is quite random if things are non-maliciously crafted (e.g. $q$ is chosen independently of $p$, and $d<N$).
An exception pointed in comment is when the composite $p$ that crept-in happens to be a Carmichael number. These are (rare) composites such that $x\not\equiv0\pmod p\implies x^{p-1}\equiv 1\pmod p$; that is, no Fermat test can detect that a Carmichael number is composite!
Correspondingly, RSA will "work" with Carmichael numbers instead of primes, but will be arguably less safe than if $p$ was prime because $p\cdot q$ will be relatively easy to factor: if $p$ is 2048-bit, it will have at least one factor of less than 682-bit (or less if $p$ has more than three factors). However this won't happen by chance, because Carmichael numbers are very rare: by far the most abundant kind has three factors, and there are no more than $x^{5/14+\mathcal o(1)}$ of these below $x$ (see R. Balasubramanian and S. V. Nagaraj, Density of Carmichael numbers with three prime factors, in Mathematics of Computation 66 (1997), 1705-1708). A random 2048-bit integer has odds less than $2^{-1300}$ to be a Carmichael number. Hence if $p$ is a Carmichael number, this could only have happened by malicious intend: in addition to the primality test, the random selection of $p$ is intentionally flawed, and the possibility of factorization of $p\cdot q$ using that it has a small prime factor is a comparatively moot issue.


There is no out of the box tester which can tell you what you need, you need to do research. I'm having the same 'problem'. I'm doing an internship for a company which wants to protect their self-created protocol which works on top of TCP.

So to tackle this I've create a plan of approach and defined my research parameters (quite broadly). Now i'm looking into the history of several algorithms (RC6, AES, Twofish) and looking which is best applicable to my situation.

Since i have hardware restrictions (it's for embedded use and some embedded divces they use are OLD) so I'm currently looking into libraries such as PolarSSL to find C implementations of cryptographic algorithms to test on the embedded devices i have.

When i test them i'll test for speed, code space and other things.

So in short, what you need all depends on what you need, maybe TDES even though it's old and almost insecure is what you need. but you need to do your own research.

As far as good implementations are concerned, open source libraries is the way to go. They are used world wide and it is safe to say well known open source libraries have been tested to an extend no stack overflow solution has (given the solution isn't a direct copy of an open source library :P )

But for all your questions these websites are for your best research:

NIST publications,  proven secure algorithms (no implementations
but lots of background)
Wikipedia, General background and    specifications
PolarSSL Source code in C
For implementations in for example c# the .net library has everything you could possible need.

So final note do not create your own implementation! use the libraries but that's a disclaimer everyone should know by now :P


Authenticated EC key exchange without a signing/signature scheme?

For a pre-shared secret, you just use a secure MAC to authenticate the key exchange, e.g. for the exchanged public ephemeral keys $A$, $B$ and the resultant shared secret $S$, one side could send $HMAC(PSK, S, A, B)$ and the other $HMAC(PSK, S, B, A)$.  Each side can easily verify that the other is using the same exchanged values and shared secret, and that the message could only have come from someone with the same PSK.  They could then use $HMAC(PSK,S)$ for the encryption key, for example.

There are several public-key methods of authenticated key exchange that can work using EC, basically using DH with an ephemeral session key and a public key.  Although the use of the public key can be thought of as signing the key exchange, it's done in an integrated fashion so there's no explicit signing step, the proofs exchanged are as much a proof of the ephemeral keys as they are of the public keys.

An example is SRP-Z (the mutually-authenticating version) with keys instead of passwords (the method uses modular addition, but that's not necessary if the public key isn't subject to a dictionary attack, i.e. it's a strong key rather than a password).  You could also just use ordinary SRP if the verifier is kept secret and a strong key is used (instead of deriving the key from a salt and password), with the same reasoning as above.

Other examples are YAK, which has a very similar structure to SRP-Z, STS, and KEA+.

KEA+ is patented, as is SRP (though SRP is licensed for free for the non-Z form).


As @tylo says, projecting the point to the $x$ coordinate does not give you a homomorphism. So
this version is not useful if you want to have additively homomorphic ElGamal.

However, you could use the "exponential" version of standard ElGamal on elliptic
curves, i.e., instead of encrypting a message $m$ somehow mapped to a point $M$ on the curve (using an injective efficiently invertible encoding), to encrypt a message $m$ straightforwardly mapped as $M=m\cdot P$ to a point on the curve where $P$ is your generator and $m$ an integer in the order
of the group. This will give you an additive homomorphic encryption
scheme. However, as discussed below, this encoding is not efficiently invertible.

Let $P$ be the generator of your elliptic curve group of prime order $q$ and $Y=xP$ be your
public key ($x$ the private key). Then given two ciphertexts for messages $m_1,m_2\in Z_q$:

$C_1=(k_1P,m_1P+k_1Y)$ and $C_2=(k_2P,m_2P+k_2Y)$, then by componentwise point addition you receive

$$C=((k_1+k_2)P,(m_1+m_2)P+(k_1+k_2)Y)$$ which is a valid ciphertext for message $m_1+m_2 \mod q$.

You can decrypt $C$, but this obviously gives you $M=(m_1+m_2)P$ and in order to recover
$m_1+m_2 \mod q$, you have to compute $\log_P M$, i.e., you have to compute discrete logarithms after
encryption. If your messages $m_i$ come from a small set, this, however, is quite efficiently feasible. However,
this clearly depends on your application, i.e., which values from which range the $m_i$'s can take.


How OR gates are garbled in recent optimizations techniques like free XOR, Half Gates?

Usually, only AND gates and XOR gates are considered in garbled circuit schemes, because they form a complete basis for boolean circuit - id est, any boolean circuit can be written only with XOR gates and AND gates. In particular, you can implement an OR gate with a single AND gate and only XOR gates, using the fact that $a \text{ OR } b = \text{not }((\text{not } a) \text{ AND } (\text{not } b))$, and $\text{not } x = 1 \text{ XOR } x$. Therefore, with the latest scheme which garbles AND gates with two ciphertexts, and where XOR gates are for free, garbling an OR gate uses only two ciphertexts, exactly as an AND gate.


How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>

The point $u$ here means that instead of sampling a point from the lattice $\Lambda$, you're sampling a point from the coset of the lattice $u + \Lambda$.
This is a "shifted copy" of the lattice (shifted by precisely $u$).

Generically though, you're looking for tail bounds of gaussian mass on lattices. You can find these a variety of places in the literature. They originate with Banaszczyk's New bounds in some transference theorems in the geometry of numbers, where Lemma 1.5(i) states:

  For any $n$-dimensional lattice $\Lambda$ and $s > 0$, a point sampled from $D_{\Lambda, s}$ has Euclidean norm at most $s\sqrt{n}$ except with probability at most $2^{-2n}$.

This citation/statement of the lemma come from another paper (so may not be exact), as I don't have institutional access to download Banaszczyk's work. If you want to see a derivation, you could look at a generalization of this bound, for example this one, which is on eprint. This includes the coset bound you want, which is stated as:
$$
\sum_{\substack{\lambda\in\Lambda\\\|\lambda + u\|_2\geq r}}\exp(-\pi \|\lambda + u\|_2^2) \leq (2\pi en^{-1}r^2)^{n/2}\sum_{\lambda\in\Lambda}\exp(-\pi\|\lambda\|_2^2)
$$
The left-hand side is the gaussian mass in the tail of the coset, which is upper bounded by the gaussian mass on the lattice.
This doesn't directly turn into the tail bound yet (for example, it doesn't include the standard deviation at all), but I imagine transforming the above inequality into a tail bound would be a quite reasonable exercise to do.


AES-CTR-256 Sub Keys With Encrypted Sub Key Index

I would advise a different solution.

You either generate a master-key (or key set) or derive one from a user password (e.g. via PBKDF2 or SCrypt). For each file to encrypt you generate a random key (file key) and nonce ad-hoc, and encrypt the file with that key, using an AEAD scheme.

The random file key is encrypted with you master key and put at the beginning of the file. Preferable you should include that encrypted key as authenticated data within the AEAD scheme.

The steps:

Generate random file key and nonce
Encrypt file key with master key (using a key-wrap spec.)
Encrypt the plaintext file data with the file key and using it enc. form as part of the authenticated data (AEAD scheme)
Store nonce, enc. file key and encrypted data as the enc. file

Your solution is dangerous. Using the same nonce with the same key (you only have 9 or so) to encrypt different data will allow an attacker to retrieve information concerning the plaintext data.


Here are some recent papers that study optimizing PSI for the case of significantly unequal set sizes. In all of these papers the primary goal is to reduce communication.

These two papers save on communication by having an offline phase with high communication. When it comes time to actually compute the intersection, the online communication is low:

Unbalanced Approximate Private Set Intersection; Amanda Cristina Davi Resende, Diego F. Aranha
Private Set Intersection for Unequal Set Sizes with Mobile Applications; Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas

This paper saves on communication by assuming that the server's large set is held by two (or more) noncolluding parties. That way, it is possible to leverage techniques of private information retrieval:

PIR-PSI: Scaling Private Contact Discovery; Daniel Demmler, Peter Rindal, Mike Rosulek, Ni Trieu

You could argue that the previous papers are "cheating" in the sense that they are not in the standard 2-party setting with a one-off computation.

There are a few papers that achieve low communication without such "cheating", and these all use expensive public-key crypto operations (proportional to the size of the large set). The most efficient one that I know of is this, which uses somewhat homomorphic encryption:

Fast Private Set Intersection from Homomorphic Encryption; Hao Chen, Kim Laine, Peter Rindal

I happen to know a followup to this work will appear at CCS 2018, but it is not available online yet.

You cannot avoid having the protocol "touch" every part of the large set, so the server cost will always be somewhat high. In PIR-PSI the cost is some number of very cheap AES operations for each item in the large set. Hence this one is the fastest that I know about (if you include the cost of the offline pre-computation in other work). The FHE-based scheme is surprisingly fast though a little slower than PIR-PSI as far as I know.

The state of the art for all of these supports 10-100 million server items and 500-5000 client items, with costs on the order of a few seconds and maybe 5-20 MB of communication.


Would the Secure Enclaves such as Keystone or Intel SGX obviate the need for cryptography

No, Secure Enclaves do not obviate the need for cryptography.

For a start, Secure Enclaves typically receive their input data integrity-protected or/and encrypted, which requires cryptography both within the enclave, and outside (perhaps in another enclave).

Even if we turn the question to "Would the use of Secure Enclaves obviate the need for unrelated cryptography", the answer is still no. Secure Enclaves aim at creating a virtual secure computer not under control of the person holding the enclave, and that does not match all use cases. Even in an Orwellian world where Secure Enclaves are the only form of secure data processing permitted, I bet both a master of that society, and any rebel, will want to use raw cryptography. And I see no practical way to prevent that, as long as programming remains a thing. We can do AES-256 or RSA-4096 in any computer language, including a spreadsheet.