What characteristics define a function to be a block cipher

The Wikipedia definition states;

  In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called a block, with an unvarying transformation that is specified by a symmetric key

  A block cipher consists of two paired algorithms, one for encryption, E, and the other for decryption, D. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits; and both yield an n-bit output block. The decryption algorithm D is defined to be the inverse function of encryption.

Your $F_k^r(m) := r(k,m)$ with $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$ is not a block cipher since:

The input block size and the output block size are not same as in the Wikipedia definition. Therefore you cannot define the inverse (decryption). With the key concerned, the input space must be $2^{2n}$, not $2^{3n}$ and output space must be $2^{n}$.


How to interpret Berlekamp-Massey algorithm?

Too long for a comment.
The Berlekamp Massey algorithm is a tour de force. It has the names of two Shannon award (top information/coding theory award for lifetime contributions) recipients attached and it is quite subtle.
The step you point to is a way of correcting the discrepancy between the sequence the current polynomial would generate and the actual sequence by modifying the polynomial.
Dilip Sarwate has a nice answer on this with somewhat different notation.
Berlekamp-Massey to construct minimal LFSR
The textbooks by Richard Blahut also explain the BM algorithm. The one called “Fast algorithms..” may be the most detailed.


Divide data into parts and restore from them

The problem you are describing is called Secret Sharing
And the common algorithm to solve the m of N is https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

It is not only computationally difficult, it is information theoretic impossible to discover the secret without the required number of shares.


How secure is ECDH if the public keys are never changed?

The following notation of $Gba$ is the $\operatorname{diffie-hellman(Gb, a)}$ or ${g^b}^a$ where we assume Alice' perspective where Alice knows $a$ and $Gb$, not $b$. Bob computes the equivilent $Gab$.

I advise against using straight static-dh where $a$ and $b$ are static and $k$ is unique per pair of users.

$$k = \operatorname{kdf}(Gba)$$

If either key is compromised then a passive adversary who records transactions may recover all messages. Worse, an active adversary may silently MiTM all sessions in real-time.

The full MiTM requires impersonating both sides, which KCI (key compromise impersonation) enables. I.e. If Mallory knows $a$, she can pretend to be Alice to Bob and pretend to be Bob to Alice.

One popular alternative is 3DH, as used in Signal and similar protocols.

$$k = \operatorname{kdf}(Gda \| Gbc \| Gdc)$$

Where $c$ is Alice' ephemeral key and $d$ is Bob's ephemeral key. Notice $Gab$ is not used because it is static and does not introduce additional security as the ephemerals are paired with the static keys providing KCI-resistant mutual authentication and paired together for forward secrecy.

If both of Alice and Bob's keys are compromised. A passive adversary is still unable to recover messages. However, an active adversary may substitute the ephemerals and do the full MiTM again.

If the client is anonymous, you may use 2DH by omitting $a$ and computing instead:

$$k = \operatorname{kdf}(Gbc \| Gdc)$$

  My question is how secured is how easy would it be for someone to figure out the symmetric key now that the same key is used for encryption/decryption?

You must always respect the security contract of any function you use. I.e. Never reuse a $k$ with a single-use AE. Never reuse a $(k,n)$ tuple with an nAE.

If you're using the symmetric key correctly or not is irrelevant to how the key was derived.

Edit: If you're asking if it is safe to shake hands with with many people? Then yes, so long that the construction is safely guarding against bad-keyshare attacks, the result should not reveal anything to an adversary, even if you shake hands directly with them.


Can Blake2 be a replacement for double SHA-256?

BLAKE2 can be used as a drop-in replacement for SHA-256d, yes. It is not vulnerable to the length extension attack. Whether or not you should use it in cryptocurrency is a more complex question, but it suffices to say that it will not be any less secure than using SHA-256d for your purposes.
Regarding the speed comparison, this will be more complex to answer as you'd need to specify if you want to encourage CPU mining, GPU mining, or ASIC mining for the cryptocurrency. The raw speed of the hash on a modern CPU will also vary, but BLAKE2 will be faster than SHA-256d. Exactly how much faster depends on the CPU's capabilities, such as SIMD features supported.


If I know the salt, can I decrypt the commitment?

No, if Bob only knows the salt, he should not be able to decrypt the message.  This is based on the assumption that the key can't be derived from the salt or some combination of the cipher text and the salt.  If that is the case, the salt would not be enough to recover the key.


What are the possible cryptographic implications of Zhang's proof of the Twin Prime Conjecture?

There are no known applications or implications to cryptography of that mathematical machinery.  I've not seen any suggestion that the machinery would plausibly have implications for cryptography.  The twin primes problem doesn't have any obvious connection to any hardness assumption or problem in cryptography.

(Yes, both Zhang's proof and cryptography have something to do with prime numbers, but that is extremely thin. Much of number theory can say it is somehow related to prime numbers, but only a small fraction of number theory has had applications to cryptography. It'd be like assuming that recent improvements in building fast sailboats for the America's Cup has implications for the possible future availability of an immortality potion, since they both involve fluids.)

In other words, this is about as close to a "No" answer as one is likely to be able to give, given the nature of the question (which makes it very unlikely that you are going to get a definite, resounding no).

Here are some surveys of the mathematics of this result and related results, if you want to take a look for yourself:

https://gilkalai.wordpress.com/2013/09/20/polymath-8-a-success/
http://arxiv.org/pdf/math/0605696v1
https://terrytao.wordpress.com/2013/06/30/bounded-gaps-between-primes-polymath8-a-progress-report/


Probability for collisions of a one-way compression function

$\left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \:$ is the number of elements that the compression function can map to.

If $\: m > \operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right) \:$ then $\;\; \left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \: = \: 2^m \: > \: 2^\left(\operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right)\right) \: = \: \frac{t^2}{2\cdot \epsilon} \;\;\;\;$.


What is the runtime complexity of the `BLAKE2` hash function?

Blake2 takes (in either variant) the input, processes it in fixed-size blocks, padding the last block with zeroes to the full block size if required. The processing operation happens in constant time (it takes a constant number of cycles, big-O notation is meaningless since the input size is fixed). The initialization and finalization steps also take constant time. Therefore, the overall operation takes $O(n)$ time.


Does passphrase length impact read-write speed?

If I had chosen a 25-character key would this process be faster?

That would depend entirely on how Diskcryptor was designed; but it appears it would not.

According to the Diskcryptor homepage, Diskcryptor selects a random symmetric (AES, Twofish or Serpent) key, and uses that to encrypt the disk; it uses the passphrase (what you call the strong encryption key) to encrypt that random symmetric key and put it in the boot sector.  When it comes time to use the disk, you'd enter your passphrase, which would allow Diskcryptor to decrypt the random symmetric key; that symmetric key is then used to decrypt (and encrypt) everthing else.

Because the vast bulk of the work is done using that random symmetric key (which is the same size independent of the size of the passphrase), the length of the passphrase doesn't matter.

Now, the page does mention that it can use Cascaded ciphers; say, AES + Serpent.  If you have it configured that way, it would be considerably slower than if you were just using AES (which would be easily the fastest because of the AES-NI instructions); that's the only thing I can think of which might be slowing you down.


Comparison Vigènere vs. Monoalphabetic cipher

a) The question seems to be about a comparison of the size of the key spaces. The hint already shows the key spaces for Vigenère with a 10-letter key ($26^{10}$) and for simple substitution ($26!$). Simple substitution has the much bigger key space.

b) Using frequency analysis simple substitution is much easier to solve. Basic frequency analysis does not help for Vigenère (at least not without additional methods). With that in mind Vigenère could be considered more secure than simple substitution. In fact: both are not really secure, don't rely on them.

c) Vigenère with a key that is exactly as long as the plain text could be considered absolutely secure. But then again, it would be highly unpractical. :-)


What does "export grade" cryptography mean? And how is this related to the Logjam attack?

"Export grade" cryptography is a result of The Crypto Wars. Laws were passed in the United States that resulted in the crippling of encryption software that was distributed outside of the United States. This section from wikipedia explains it well enough:

  The longest key size allowed for export without individual license proceedings was 40 bits, so Netscape developed two versions of its web browser. The "U.S. edition" had the full 128-bit strength. The "International Edition" had its effective key length reduced to 40 bits by revealing 88 bits of the key in the SSL protocol. Acquiring the 'U.S. domestic' version turned out to be sufficient hassle that most computer users, even in the U.S., ended up with the 'International' version,[7] whose weak 40-bit encryption could be broken in a matter of days using a single personal computer. A similar situation occurred with Lotus Notes for the same reasons

The 40-bit limit was for symmetric ciphers, where there is no (known) attack better than trying all $2^n$ keys. Asymmetric algorithms like DH and RSA need larger key sizes for the same security; see e.g. How much computing resource is required to brute-force RSA? and Security strength of RSA in relation with the modulus size . At the time 512-bit RSA or DH was rated equivalent to 40-bit symmetric, and thus export of those algorithms was limited to 512 bits. (DSA was rated the same, but was not limited because it is not an encryption algorithm.) This is why weakdh.org states that:

  The Logjam attack allows a man-in-the-middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography.

Ultimately, some software was required to be written using key sizes that were understood to be breakable; export grade cryptography refers to this form of an algorithm that uses a reduced and breakable key size. The Logjam attack works by tricking the TLS exchange into using crypto that is weaker and potentially breakable.


What is the logic behind Compress function in iterated hash function

A compression function is necessary to fulfill the requirements of a hash function. This is because hash functions are expected to be able to accept as input bit strings of arbitrary length, and output a bit string of a constant length*.

The specifics of how the compression function compresses the input string is particular to the construction of the hash function in question. For example, the Merkle–Damgård construction tends to use a block cipher as the compression function. As to how it compresses, it typically uses one block of hash input at a time as the key to a block cipher, and uses this to successively encrypt the internal state.

There is also the sponge construction, which compresses the input data in a different way. The sponge construction holds an internal state consisting of rate + capacity bytes, and "absorbs" rate bytes of hash input into the rate section of the state, either via xor or direct replacement, then mixes the state using an invertible permutation.

*technically there is a reasonable maximum in practice as to the size of the inputs, and the sponge construct is notable for being able to produce arbitrary length outputs.


What is the role of a circuit in ZK-SNARKS

Technically neither party necessarily evaluates the circuit.

The two parties share the description of a circuit $C$, an output value $y$ and potentially some input values $x_1\dots,x_\ell$. the prover than proves to the verifier that they know additional secret inputs $s_1,\dots,s_n$, such that if one were to evaluate the circuit $C$ on inputs $x_1\dots,x_\ell,s_1,\dots,s_n$ the result would be $y$. I.e.,
$$C(x_1\dots,x_\ell,s_1,\dots,s_n)=y.$$

The argument of knowledge property guarantees that the prover must actually know said inputs in order to convince the verifier. The zero-knowledge property guarantees that the verifier learns nothing from the exchange except that the above statement is true. In particular the verifier learn no information about $s_1,\dots,s_n$.


AES function with 128 bit key and 128 bit input size - does it have perfect secrecy?

I don't think a block cipher can offer perfect secrecy. Perfect secrecy means that knowledge of the ciphertext doesn't give you any information about the plaintext.

However a block cipher is a keyed permutation: the key is used to choose one permutation of the plaintext to ciphertext. The number of possible permutations is almost infinite. This means that the permutations selected by the key is a (randomly chosen) subset of all possible permutations.

Now the problem is that there may be mappings of one plaintext to a ciphertext that are more common in this set than others. This means that the tiniest amount of information may be leaked by a ciphertext: a specific key or group of keys is more likely to convert a specific plaintext to a specific ciphertext. This means that a certain plaintext is more likely than another plaintext for a given ciphertext.

And this, in turn, means that a block cipher is not perfectly secret - even if the key is the same size as the plaintext / ciphertext.

As for the second question: yes, you can get the same output. Although the keys select a specific permutation, it isn't said that the same mapping of one specific plaintext to one specific ciphertext isn't part of the permutation; a permutation is different if even just one mapping in the complete set of mappings is different. The chances are of course abysmally small to find it.

In the end we just don't need perfect secrecy. If we do want perfect secrecy it makes absolutely no sense to use a block cipher while a simple XOR suffices. The trick - as always - is to generate and share the perfectly random key stream. Once you have that you don't need AES anymore.


Using two elliptic curves to do a range proof

I am going to write this as an answer rather than as a comment, since this type of mistake repeats itself multiple times on this forum.

First, specifically to this question: the question doesn't make sense. What are you trying to prove? That there exists an $a<q$; of course there does. That you know an $a<q$; of course you do. These range proofs make sense when you have a commitment to or encryption of $a$ and want to prove that $a<q$. I am not saying this to be critical but to address a mistake that is very common.

Now, to the more general issue, which is the important one. Zero-knowledge proofs only make sense when you have a well-defined statement that you are trying to prove. It is important to write down this statement clearly, and then see if it is trivial. For example, a statement that says "for all primes $q$ there exists an integer $a$ such that $a<q$" is trivial. That is; it always holds (for all primes $q$) and thus there is nothing to prove. Note that there are statements that look less obvious. For example, given a group of order $q$ with generator $g$ and a group element $h$, the statement "there exists a value $x\in\mathbb{Z}_q$ such that $h=g^x$" is also always true, and thus is trivial. This may seem confusing since this is exactly the statement of the Schnorr discrete log proof; I will explain below. Finally, any statement that can be verified in polynomial time does not make sense for zero knowledge (at least as we formulate it) since the verifier can check itself, making it trivial. In short, in order to talk about zero knowledge in a non-trivial way, there needs to be a well formulated NP statement (NP so that the prover can be polynomial time) that cannot always be verified in polynomial time without any additional information.

Having said the above, there is sometimes a need to prove that the prover knows something. For example, for every $g,h$ as above, there always exists some $x$ such that $g^x=h$ but it is not necessarily known (and cannot be found efficiently). Thus, a zero-knowledge proof of knowledge can be used in such circumstances. Another classic example is that I know the value inside a commitment or ciphertext (without revealing it). Here too there should be a clearly formulated NP statement and finding the witness should be something that cannot in general be done in polynomial time.

I hope that this helps...


Show that the equal difference property exits for a modified DES encryption system

For 1) you need to show that $S(X)$ is linear with respect to xor.

We can define $S(X)$ as:

$S(X) = (x_{7}, x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6})$

And define $A \oplus B$ as:

$A \oplus B = (a_0 \oplus b_0, a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6,a_7 \oplus b_7,)$

So we have:

$S(A \oplus B) = (a_7 \oplus b_7,a_0 \oplus b_0,a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6)$

$=(a_{7}, a_{0}, a_{1}, a_{2}, a_{3} a_{4}, a_{5}, a_{6}) \oplus (b_{7}, b_{0}, b_{1}, b_{2}, b_{3} b_{4}, b_{5}, b_{6})$

Which by definition is:

$=S(A) \oplus S(B)$

For number 2) we'll first show that if there is some difference $D = A \oplus B$ then $E_k(D) = E_k(A) \oplus E_k(B)$.

We can define $E_K(M)$ as:

$M_R || (M_L \oplus S(M_R))$

So given:

$E_k(A) \oplus E_k(B)$

$=\big[A_R || (A_L \oplus S(A_R))\big] \oplus \big[B_R||(B_L \oplus S(B_R))\big]$

$=(A_R \oplus B_R)||(A_L \oplus S(A_R) \oplus B_L \oplus S(B_R))$

And using the property proved in 1) you get:

$=(A_R \oplus B_R)||(A_L \oplus B_L \oplus S(A_R \oplus B_R))$

And because $D = A \oplus B$:

$=(D_R||(D_L \oplus S(D_R))$

$=E_k(D)$

Now we can show the equal difference property holds:

$A \oplus B = C \oplus D$

$E_k(A \oplus B) = E_k(C \oplus D)$

$E_k(A) \oplus E_k(B) = E_k(C) \oplus E_k(D)$


How many times can a key be used for HMAC-SHA256 before it needs to be rotated?

There is no known inherent weakness in HMAC-SHA256 that requires key rotation for a suitably secret key.

However, other aspects of the system in which you are using HMAC-SHA256 may make key rotation necessary. For instance if you don't want the same message to have the same hmac over time for some reason a key rotation would achieve that (but so would a salt). Or if you know your key comes from an unusually low entropy pool making it easier to brute force than one would expect.


Hashing Resource ID Into Publicly Known Value Securely

You are right thinking that using a large secret salt, such as a 256 bits value generated randomly (with a good CPRNG) should be fine.

Notice that we usually say that a salt can be known from the attack, which is not the case in your design, so you are not using a salt, but a key. Keyed-hash function are a thing (see BLAKE2, for example), but you can generally construct a keyed-hash function out of any hash function by simply hashing the concatenation of your key and your message with the said hash function.

In this latter case, which correspond to your design, the preimage resistance of the hash function would prevent the attacker from finding the "salted/keyed Resource ID" without knowing the key.

Using more than one key, like for example, one for each resource, would simply strengthen the system against potential leaks that might occur. Since then, if a key leaks, the rest of the non-leaked keys would still prevent an attacker from finding the image of a given Resource ID (or finding the preimage of a given hash by bruteforcing the possible Resource IDs, if those are known/in a small range).

Notice that the system you mention:

  a system that takes that ID as an input parameter and produces a consistent output for a given resource

is somehow similar to a pseudo-random generator, where the key would be the resource ID. Using a keyed-hash function as you propose (as long as the key has enough entropy) is a way to construct such PRG, but there are some hiccups if you let the adversary possibly control your entropy pool... I'm looking for example at the "Hash_DRBG"...

Now another way around your problem, since you've got a key already, might be to simply encrypt the resource ID with a symmetric (AES, e.g.) and that key you called "salt"... (As long as that key is generated with a good entropy, using a CPRGN, you're safe.)

Plus you'd get the two-wayness you wanted, as you could simply decrypt the resulting value using the key to obtain the initial resource ID out of it.


Are block ciphers vulnerable to “key reuse” and/or “bit-flipping” attacks?

XOR may be used internally, but that doesn't mean the resulting ciphertext is automatically vulnerable against bit flipping or key reuse attacks. XOR is used for techniques to create confusion & diffusion, over multiple rounds.

An attacker doesn't usually have any influence on those internal operations unless side channel attacks apply (or when we're talking about white-box cryptography). If the attacker does have access, then changing a bit operation for XOR is likely to affect multiple output bits.

As for AES: to create a IND_CCA secure cipher, AES needs to be used within a block cipher mode of operation. That cipher mode could e.g. be CTR or any other mode that generates a key stream. That streaming mode of operation in turn will be vulnerable with regards reuse (same IV/nonce) and bit flipping attacks.

Other modes of operation such as CBC are also vulnerable against IV reuse, although the resulting attacks are much less powerful. For instance, an attacker could distinguish completely identical starts of the plaintext, as the ciphertext will be identical as well.

The same goes for bit flipping, although for CBC mode a whole block + one bit will change. It depends on the implementation if these larger changes will be picked up. If it does, it may result in a plaintext-oracle (e.g. a padding oracle), which may further compromise confidentiality.

So in the end it is (almost) always required to create a unique IV for any cipher and mode of operation. To avoid bit flipping an authenticated mode of operation or (H)MAC could be used.


Actually, you are right and the paper is wrong.

They omitted the fact that they used a different generator and/or vector than the AES s-box. This is why you are not getting the same results.

I ran a brute force generation of all APA s-boxes, and none of them starting with $0x8C$ continued with the results of the paper. It is probable they used two different affine transformations, and it would take 65000 times longer to search that space, so I am not going to do it. There are other problems with the s-box; strict avalanche is inferior to the AES s-box, and there are 4 self inverse elements.

Here is the full report:

Iterative Periods: 2 (2)  12 (2)  26 (2)  176 (1)
Self Inverse error at index 135  0x87
Self Inverse error at index 152  0x98
Self Inverse error at index 171  0xAB
Self Inverse error at index 225  0xE1

SAC Min/Max: -16  +16  12.5%, DSAC: 452, DDSAC: 220, Avg/Dev: 128.2 8.35, Satisfied: 60.9% (39)
GA: 358.6, Dist: 0 62 242 456 544 442 222 68 12
Aval: 0.0312, Dist: 16 0 4 8 20 32 24 20, Totals 124 0.0605

HOSAC Min/Max: -16  +16  12.5%, HODSAC: 1464, HODDSAC: 724, Avg/Dev: 128.1 7.86, Satisfied: 61.2% (137)
HOGA: 1176.8, Dist: 0 242 776 1602 1940 1598 754 234 22

BIC Min/Max: -16  +16, DBIC: 1508, Avg/Dev: 127.9 7.88, Satisfied: 58% (130), BIC: 0.12856
HOBIC Min/Max: -16  +16, DBIC: 5244, Avg/Dev: 128.5 8.1, Satisfied: 57.4% (450), BIC: 0.13498

Differential Uniformity: 4 (255)
Non-linearity: 112  Delta: 16 (255)
AutoCorrelation: 32 (255)
SSI: 133120

There is a revised version of that paper from 2010 which uses $0x5B$ for the generator and $0x5D$ for the vector, and generates a different s-box.

The 2nd paper had reproducible results. It also had no self inverse elements and a full iterative period, although it still did not have fully superior statistical properties to the AES s-box.

It should be noted that APA using the Rijndael affine transformation is a complete mess of fixed points and is unsuitable for cryptographic applications. APA s-boxes within a different finite field than $0x11B$ used by Rijndael are more interesting, field reduced using $0x165$ has the best results.


What is the difference between online and offline brute force attacks?

An offline attack require work from the attacker only (or mostly), with no (or little) communication with the system (e.g. server) under attack (holding the key). An online attack requires (typically significant) work of the system under attack (including communication).

The computing power or communication bandwidth of the system under attack is typically limited compared to what a resolute attacker might use. Thus even if it requires significantly more effort, an offline attack usually is easier to perform in practice than an online attack, and stands better chance to go undetected.

Note: Online attack refers to communication with an entity under attack, that must be online (and participating) during the attack. An attack using a coalition of adversaries communicating online, with little or no communication with the entity under attack (if any), is an offline attack requiring online communication.

For example, parallel hash collision search is an offline brute-force attack. The attack against HMAC-MD5 that asks for the MAC of random messages ending with the same block until a collision is found (requiring about $2^{64}$ queries), then modifies the last block of the two colliding messages to (likely) get a new collision allowing a MAC forgery, is an online brute-force attack, since there is massive work involving communication with an entity capable of computing MACs (holding the key).


How does the Efficient Fully Homomorphic Encryption from (Standard) LWE work?

The BV scheme presented in the article works for plaintext messages in $GF(2)$ (that is $m$ $\in$ $\{0,1\}$) but can be extended to support encrypting messages that are in $GF(t)$ where $t$ is prime with the modulus $Z_q$.

This means that if you want to encrypt a message in $\{0,1\}^n$ you have to do it for each bit separately in $GF(2)$ (or in $GF(t)$ and the message $m$ $\in \{0,1,...t-1\}^n$)

The BGV scheme instantiated with the LWE problem is the same as in BV.
The main difference in BGV is that the scheme supports a more general context, namely it could be also instantiated with the Ring-LWE problem providing a more efficient circuit (inner operations are done inside a ring $R$ instead from $Z_q$ as in LWE).


Higher-Order Side Channel Security and Mask Refreshing: linear function?

Actually, it's any $\mathbb{F}_2$-linear function you want it to be.

That is, those two algorithms are generic ways, given a linear $g$ and a threshld (secret-shared) value $x$, to compute a threshold version of $x \times g(x)$ (where $\times$ is $GF(2^n)$ field multiplication).


Elliptical curve cryptography key generation time

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it.

You're missing a point; elliptic curve point addition is associative; that is, for any three points $A, B, C$, we have:

$$(A + B) + C = A + (B+C)$$

Now, why is this a big deal?  Well, we can exploit that compute $G+G+G+...+G$ surprisingly quickly.

Our first step is to compute $G+G$ (which is $2G$); that's straight-forward:

$2G = G+G$

One point addition, no improvement over the naive method.  Ok, let us compute $4G = G+G+G+G$.  By the associate law, that is:

$4G = G + G + G + G = (G+G)+(G+G) = 2G + 2G$

So, we can compute $4G$ with two point additions, one to compute $2G$ and one to take $2G$ and use it to compute $4G$.

Then, to compute $8G$, that's $8G = 4G + 4G$, just one more point addition.

In general, we can compute $2^kG$ (which is $G$ added to itself $2^k$ times) using only $k$ point additions.

And, what do we do if $d$ doesn't happen to be a power of 2?  Well, by adding in previous results at various steps (e.g. $5G = 4G + G$), we can accommodate those with some additional expense.

One straight-forward way to extend this to any $d$ is found here; we know more efficient methods (some of which are also on that page); however it is quite reasonable, and a good place to start.

With this technique, you can generate an elliptic curve private key in milliseconds (and, this method of computing point multiplication will also be used when you use the key to actually do something)


CBC-MAC: is it secure to authenticate a fixed length ciphertext?

Yes, if your encryption algorithm is reasonable secure.

Given fixed length messages (in your case the ciphertext), CBC-MAC is a secure MAC scheme, meaning that an attacker, without knowing the key, cannot produce a valid message-tag pair with non-negligible probability. Furthermore, according to this paper, Encrypt-then-MAC is the best procedure, while MAC-then-Encrypt and MAC-and-Encrypt are vulnerable to chosen-ciphertext attacks, the latter may even weaken the security of the encryption scheme itself. Thus the security of your system depends solely on the encryption algorithm you use. The ciphertexts it produces should be indistinguishable under chosen-plaintext attacks (IND-CPA). In other words, an attacker who sends two messages to an oracle and gets one ciphertext in return won't know which one of the two messages were encrypted.

AES in CBC mode with an initialization vector chosen randomly each time you encrypt a message is assumed to have this property.


If you combine two affine ciphers, you obtain one affine cipher. Say the first cipher is $e_1(x) = a_1x+b_1$ and the second is $e_2(x) = a_2x+b_2$. Then $e_1(e_2(x)) = a_1(a_2x+b_2)+b_1 = (a_1a_2)x+(a_1b_2+b_1)$.

Note that if $a_1$ and $a_2$ are both relatively prime with the modulus, then so is $a_1a_2$, so the new cipher can also be deciphered.


Diffie-Hellman based password challenge response scheme

First off, what you are trying to construct here is called an augmented or asymmetric password-based key exchange (aPAKE). As for your concrete construction:

  Does this scheme work?

Yes, it will be functionally correct.

Does it actually achieve the security guarantees of an aPAKE scheme? No, an attacker can look at the transcript, see $Q_s=[k]Q_a$ and knows both $Q_s$ and $Q_a$ and thus can just off-line brute-force the password.

The first (symmetric) scheme you mentioned suffers from the same problem.

  Could we make a public-key-based scheme for challenge response
  authentication?

This is what aPAKE schemes do, the most notable protocols are:

the Secure Remote Password Protocol (SRP), mostly because it was first to be standardized in RFC 2945.
OPAQUE which is the current state-of-the-art when it comes to (simple) aPAKEs.
If you also want to assume an auxilliary 2nd device for the user, OpTFA is the state-of-the-art.
If the user "only" has a device capable of running an (EC)DH key agreement (like a smartcard), then PTR-PAKE is the best you can get.

Example implementations (in C) of OPAQUE and PTR-PAKE can be found in libsphinx.


Think about it this way.. with AES, you only generate one key, and use that for all encryptions(of the day).., however with OTP a single key won't work and you'll need to have (say) $n$ keys to send $n$ packets securely..

Now, again, you might suggest using a seed with a PRNG to create a $128*n$ bit key for all $n$ packets.. but then here's the problem: You need to maintain states .. the $i^{th}$ packet will only make sense when decrypted with $i^{th}$ key, i.e the string  from $128.(i-1):128.i$, so suppose now you send a message, and somehow, say due to racing conditions in connection, your $(j+1)^{th}$ message reaches before $j^{th}$ message, your server won't be able to decrypt it ..

Also, even simply, PRNGs are key-ed functions (the seed IS the key) .. so you'll need to set that up anyway :)

You can probably come up with many more attacks here.. OTPs, as called, are for ONE TIME USE!! two time's a over kill :D ..


RSA problem if i choose two specific small prime numbers?

Actually, that's an expected result since $65 \equiv 10 \pmod{55}$.

You should choose $m < n$ to avoid this problem.


No, because timing attacks don't really have anything to do with errors. A timing attack means analyzing the time it takes a cryptographic operation to complete leaks secret information. That actually has nothing to do with error messages; it's just as much a timing attack to look at how long it takes the server to decrypt something in a CTR mode (where the AES primitive is run on publicly known plaintext with a secret key) by measuring delay between messages, to get information about the key. On the flipside, there are very good reasons to return an error if something goes wrong -- it means the message needs to be re-sent, because you don't know if it was corrupted in transit or if there was a problem with the message itself.

Now, there are attacks that have to do with being able to learn that there was an error in the message; the POODLE attack against TLS was one such attack, where learning that the padding was bad told the attacker valuable information about the plaintext. That may be what you're thinking about in terms of error messages, and one part of a remedy may be to not send detailed error messages (the real remedy is to use a message integrity mechanism to protect the plaintext, so an attacker can't pull a chosen-ciphertext attack). But timing attacks have little to do with this.

The way to defend against timing attacks is to make sure the time taken to execute cryptographic operations does not depend on any secret information. It can depend on key length or message length, because that's not generally considered secret; it must not depend on the actual value of the key, or the contents of the message. This is more complicated than just doing constant-time compares and the like; you also need to worry about other factors (like caching) that you don't directly control but nevertheless affect the time to run the operation (this is one of the advantages of direct hardware implementation of crypto: it's easier to control timing when you have the total control over execution that only Intel or AMD engineers have).


RFC 5280 is the relevant standard for X.509 PKI certificates. Per section 4.1.2.7 of that standard:

The object identifiers for the supported algorithms and the methods
for encoding the public key materials (public key and parameters) are
specified in RFC3279,
RFC4055, and
RFC4491.

RFC 3279 specifies the following public key types:

RSA
DSA
Diffie-Hellman Key Exchange (DHKE)
Key Exchange Algorithm (KEA)
Elliptic curve DSA (ECDSA)
Elliptic curve Diffie-Hellman (ECDH)

RSA 4491 adds the following public key types:

GOST R 34.10-94
GOST R 34.10-2001

RFC 4055 adds some signature and other algorithms, but no additional key types.
Finally, section 4.2 of RFC 8692 adds that "certificates conforming to RFC5280 can convey a public key for any public key algorithm", so other types seem possible, although obviously certificates containing more exotic keys may not be interoperable.
Specifically for public-trust TLS certificates, the CA/Browser Forum Baseline Requirements restrict the key types to RSA and ECDSA (section 6.1.5), with additional restrictions appropriate to the type. For TLS more generally, the public key in the server certificate should be compatible with the selected key exchange algorithm.


Creating a share of a random shared secret

You probably want a stronger requirement, that no individual knows more than his share. Off the top of my head I don't know how to do that.

But the question you asked, only requiring no one to know the full secret is easier.
K participants each pick a random number to be their share, using secure multi-party-computation they compute n-k shares which they distribute.
If n>=2k you compute in groups changing the set of people computing.

This can probably be modified slightly to meet the stronger requirement without using secure multi party computation as a black box.


The source quoted says:

  The client-side master key you provide can be either a symmetric key or a public/private key pair.

In the later case, the main benefit of using a separate symmetric key is that only the public key (rather than secret information known beforehand) is needed to encrypt a file. That symmetric key is then forgotten, hence the need to make a separate one for new files. Also, the symmetric encryption (made possible by the extra key) is much faster and less size-expanding than the asymmetric one. This is hybrid encryption at its best.

There are other benefits, that still apply when the master key is symmetric:

Assuming all the encrypted files are public, using a separate key for each file gives the option to release the key allowing decryption of a single particular file, rather than the master key which would reveal all files.
Using a separate key for each file reduces the amount of data enciphered using the same symmetric key; this works towards staying below a safe limit per key after which the encryption used might become weaker (e.g. for 3DES in CTR mode, we can distinguish sizably better than random if 16GByte enciphered with the same key was originally all-zero or compressed video, including when split across multiple files with unique IV and no keystream reuse).
As pointed by Ilmari Karonen in comment, it might sometimes be desirable to change the master key, e.g. if it's derived from a user-supplied password that the user wants to change, without fully decrypting and re-encrypting all the files. Using separate file keys is one way to enable this.


Can multi-prime RSA be used to create an abuse-resistant lawful interception mechanism?

That sorts of works, but:

Whatever decrypts will need the full private key, and will be a potential single point of failure.
The system can be secure only if each of $pq$, $qr$, and $rp$ is wide enough to be hard to factor; so if you want to be as secure a 4096-bit RSA, you need a 6144-bit public modulus.
We can achieve the same functionality by using two-factors RSA (thus reducing the size of the public modulus at equivalent security), and Shamir's secret sharing for the private key (or the seed that was used to generate the private key, with the added bonus that the shared secrets can be short enough to be keyed-in).
We can achieve better functionality using two-factors RSA and a private/public key pair per entity, with each file encrypted with secret-key cryptography like AES and a random key, shared using Shamir's secret sharing, with the secret shares RSA-encrypted. That way, the number of autorities necessary to decipher, thresold... can be chosen on a per-file basis; and most importantly, the multiple private keys never need to be brought together.


Normal CBC mode cannot be parallelized during encryption; that's because CBC mode encryption is defined as:

$$C_i = E_k(C_{i-1} + P_i)$$

That is, what you encrypt during the processing of block $i$ depends on ciphertext of block $i-1$; hence you can't start the next block until you've completed processing of the previous block.  You can't do any parallelization, except for that parallelization that's inherent within AES.

On the other hand, CBC mode in decryption can be parallelized, and it's fairly straightforward.

In addition, there is a variant of CBC mode where you don't xor in the immediately previous ciphertext block, you xor in one $n$ blocks ago, as in:

$$C_i = E_k( C_{i-n} + P_i )$$

This is effectively running $n$ different CBC mode encryptions in parallel; this can be paralleized $n$ ways.


First, in a strict sense, detecting randomness by statistical tests is impossible. One can only detect absence of randomness.

Second, a perfect compression algorithm should generate an output which is indistinguishable to random numbers. A hand-waving argument goes as follows:
If the output would not be indistinguishable from random numbers, then it would contain some remaining structure. And this structure could be used to compress the input even more.

This means, the only thing you can probably do is to throw many good statistical tests to your random numbers. It cannot prove that your source is true random but it can give you some evidence that it is not broken.

A third point to mention is that NIST has already superseeded the simple test of Fips 140-2 by the far more comprehensive tests of the Nist SP 800-90B publication.


This seems quite unlikely. A recent paper has suggested a Continuous LWE problem. This problem is structurally quite similar to the standard LWE problem --- it has (quantum) worst-case to average-case reductions to hard lattice problems.
In that paper they also show that a
standard problem in ML (learning mixtures of Gaussians) reduces to the continuous LWE problem. This gives you a more concrete ML problem to attack. If you could learn mixtures of Gaussians, you could reduce this to solving continuous LWE, which you could then reduce to solving worst-case lattice problems. If you can solve worst-case lattice problems, then we do not believe LWE is hard anymore.
There have also been some results showing that a broad class of learning algorithms (ones which fit into the "Statistical Query model") cannot solve certain learning problems. The LPN problem (which you can vaguely think of as "LWE with $q = 2$) has such bounds (see for example this problem). I don't know if specific ML techniques such as backpropagation fit into the SQ model though.


EEE with $K_1$=$K_2$=$K_3$ is measurably less insecure than EDE with $K_1$=$K_2$=$K_3$, because the former has 48 rounds, but the later reduces to just one encryption E, thus 16 rounds. Two consequences:

This makes brutes force require 3 times more rounds, thus adds about $\log_2(3)\approx 1.58$ bit of practical security against brute force (security in bits grows as the base-2 log of the computational effort); however that remains way too low, and was so even in 1999. Brute force is the typical attack against single DES, and works fine including for EEE with 3 equal keys.
This regains up to like a dozen bits of security that otherwise might be lost to cryptographic weakness of DES, beyond its low key size.

On the second point: assuming $2^{42.5}$ known plaintexts and as many DES, implementations of Mitsuru Matsui's Linear Cryptanalysis Method for DES Cipher (in proceedings of EuroCrypt 1993) break 16-round DES with excellent odds and thousand times less work than brute force, but not 48 rounds (and I do not see that subkeys of rank equal modulo 16 being equal can help much).

Note: Linear Cryptanalysis of 16-round single-DES could be the least computationally costly attack in CTR or OFB mode; but in many other modes, as pointed in comment, $2^{42.5}$ known plaintexts by itself allows recovery of a sizable fraction of other plaintext, thus linear cryptanalysis is impractical.


ECC public key encryption without symmetric cipher

ECC cant really be used to encrypt and decrypt data - it doesn't have the required properties. An asymmetric cipher such as RSA would have to be used, as this can encrypt and decrypt data.

ECC can be used for bilateral key exchanges, and to sign/verify data. RSA can sign/verify data, do KEMs, and encrypt/decrypt data.


As a single transformation considered in isolation, a fixed bitwise permutation does not offer any security. If you examine the hamming weight (the quantity of '1' bits) of the data before and after a bitwise permutation, you will notice that it remains unchanged. A bitwise permutation simply shuffles the order of the bits of data. Repeated applications will not modify the hamming weight, and will just shuffle the bits more.

Since the permutation is fixed, we concede that anyone can calculate it at will, so anyone can calculate the inverse at will. This is pretty much the case for any fixed permutation. Since there is no additional variable that is kept secret (the key), anyone with the data and the permutation has all the information they need to invert it.

A single transformation is rarely "good enough" in cryptography, so that much can be said about almost anything. However, when considered in conjunction with other transformations, such as an s-box and a key addition layer, the result is equal to more then the sum of the components. Many strong modern ciphers are built from combinations of bitwise permutations combined with other operations.

Bitwise permutations are often the source of diffusion in modern ciphers, and diffusion is a critical part of the security of modern ciphers.

One potential downside of bitwise permutations is efficiency in software. Modern processors typically operate on words that are a minimum of 1 byte in size. To address the individual bits is possible via masking and shifting, but doing so requires more operations then we would like.

For example, a bitwise permutation that operates on 8 bytes (with 8 bits per byte) and spreads out each byte evenly among output bytes has good diffusion, but has a quadratic algorithmic complexity, which can easily make it the slowest single component of the cipher.


Starting stream cypher, first block (Salsa20)

I suggest you take a look at the spec of Salsa20. It is quite short and easy to understand. You even have some examples for each component of the implementation.

For more details, you can take a look at this post which explains how to handle different key size (how to treat your initial block, and feed it to the Salsa hash function).


Discrete logarithm algorithm for modulus power of 2

Suppose multiplication of two $n$-bit integers can be done in $\mathrm M(n)$ operations.

Here's an $\mathcal O(n^2\cdot\mathrm M(n))$ algorithm for discrete logarithms modulo $2^n$, which is basically the Pohlig-Hellman algorithm adapted to this specific problem. (With naïve multiplication, the runtime therefore is in $\mathcal O(n^4)$.)

First, observe that the order of the group $(\mathbb Z/2^n)^\ast$ is $2^{n-1}$: An integer in $\{0,\dots,2^n-1\}$ is invertible modulo $2^n$ if and only if it is odd. However, that group is not cyclic; in fact, its exponent is $2^{n-2}$.
So, set $k:=n-2$ and suppose $a$ has order $2^k$ modulo $2^n$. This is the maximal order one can achieve modulo $2^n$; in particular, there are no "primitive roots" modulo $2^n$ for $n\geq3$. This also implies that $b$ can only be uniquely determined modulo $2^k$.

The algorithm essentially works by repeatedly "shifting out" the higher-valued bits in the exponent until there is only one unknown bit left, and then brute-forcing that bit. "Shifting out" bits can be done by raising $c$ to powers of two:
Suppose the binary expansion of $b$ is $b=\sum_{i=0}^{k-1}2^ib_i$. Then, since $a^{2^l}\equiv0\pmod{2^n}$ for all $l\geq k$,
$$
  c^{2^i}
  = (a^b)^{2^i}
  = a^{2^ib}
  = a^{\sum_{j=0}^{k-1}2^{i+j}b_j}
  \equiv a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}
  \pmod{2^n}
  \text,
$$
which only depends on the lower $k-i$ bits of $b$.

In particular, we can start out with $i=k-1$, which will give
$$
  c^{2^{k-1}} \equiv a^{2^{k-1}b_0}\pmod{2^n}\text,
$$
and we can easily determine $b_0$ from this by trying both values $0$ and $1$ and checking which one satisfies the congruence. (Since we know it must be either of them, plugging in only $0$ or $1$ and seeing if it matches is also sufficient.)

Subsequently using $i=k-2$ yields
$$
  c^{2^{k-2}} \equiv a^{2^{k-2}b_0+2^{k-1}b_1}\pmod{2^n}\text,
$$
and since we already know $b_0$, we can compute $b_1$ by trying both (or only one of the) possible values.

Repeating this process will obtain all bits of $b$.

As for the runtime: To determine a single bit, we need to compute $c^{2^i}\bmod2^n$ and $a^{\sum_{j=0}^{k-1-i}2^{i+j}b_j}\bmod2^n$. Using fast exponentiation, powers modulo $2^n$ can be computed in $\mathcal O(n\cdot\mathrm M(n))$ operations, hence as we need to figure out $k\in\mathcal O(n)$ bits, the total runtime is in $\mathcal O(n^2\cdot\mathrm M(n))$.

In practice, one can save a few operations by computing all the values $c^{2^i}\bmod n$ and $a^{2^i}\bmod n$ in advance using repeated squaring. However, this does not improve the asymptotic complexity, as one still needs $\mathcal O(n)$ multiplications per bit of $b$ to combine the cached values of $a^{2^i}\bmod n$ according to the concrete known bits of $b$.


What is the difference between encrypting and signing in ECC asymmetric algorithm?

ECDSA is just for signing. It stands for Elliptic Curve Digital Signature Algorithm. EdDSA is another signing algorithm, with some added security. ECDH is for key exchange: it creates a new secret key shared by both parties which no passive eavesdropper can discover.

ECC is pretty much never used to directly encrypt a message. Instead ECDH is used to create a shared secret key, and then a secret-key (symmetric) algorithm such as AES-GCM or ChaCha20+Poly1305 is used to transmit the secret data. The same thing is typically done with RSA, since asymmetric cryptography is slow it's faster to create a shared secret key and use symmetric cryptography. ECIES is a standard that does this, and several variants of the "ECDH+Symmetric encryption" idea are included in TLS.

The main use of direct encryption using an asymmetric algorithm would be a PGP-like system for encrypting e-mail or other old asynchronous protocols where no prior key agreement step is possible. I am not aware of any standard that uses ECC to do this.


how to prove sequence y uphold golomb's third axiom

The full $m-$sequence (periodically repeated to avoid modular addition in the subscript} with $$C_{xx}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{x_k+x_{k+\tau}}$$ satisfies $C_{xx}(\tau)=-1+\delta(\tau)(2^n),$ where $\delta$ is the dirac delta function. Now, one might define an $m-$symbol partial correlation function, whose average is proportional to what you want, if the average is taken over all starting points in one period. But this function itself is nearly binomially distributed and not constant over nonzero $\tau,$ for $m\leq n$. To be clear, I am referring to a function of the form
$$
C_{xx}(i,m,\tau):=\sum_{k=0}^{i+m-1} (-1)^{x_k+x_{k+\tau}}
$$
and its average
$$
\overline{C_{xx}(m,\tau)}=\frac{\sum_{i=0}^{2^n-2}C_{xx}(i,m,\tau)}{2^n-1},
$$
which arises in communication applications.

Finally if you just take the $y_k$ to be an integer in $\{0,\ldots,2^m-1\}$ by letting the vector $(x_k,x_{k+1},\ldots,x_{k+m-1})$ be the binary representation of the integer $y_k$, then due to equidistribution of $m-$tuples under the Golomb postulate the correlation function
$$
C_{yy}(\tau):=\sum_{k=0}^{2^n-2} (-1)^{y_k+y_{k+\tau}}
$$
will also be two valued since tuple equidistribution implies equidistribution of $y_k$ modulo 2, and the exponent might as well be reduced modulo 2. So you get the same distribution as that of the correlation $C_{xx}(\tau)$. Was this the point of your original question?


Could the reversibility of adding function be considered a weakness to secp256k1?

If $Q=\operatorname{adding}(P,R)=P+R$, then $P$ can be computed from $Q$ and $R$ as $P=\operatorname{adding}(Q,-R)=Q+(-R)$ where $-R$ is easy to compute from $R$ (just change the $y$ coordinate of $R$ from $y_R$ to $p-y_R$ where $p$ is the order of the prime field). This property follows from $\operatorname{adding}$ being a group law.

If $Q=\operatorname{doubling}(P)=P+P=2\times P$, then we can efficiently compute $P$ from $Q$. One method is to use that $P=\displaystyle\frac{n+1}2\times Q$ (where $n$ is the order of the curve's group). This property follows from $n$ being odd.

Neither property is considered weakness, because it follows from having a group (of odd order), which is necessary for the applications thought, including ECDSA.

By definition of secp256k1, for that curve $p=2^{256}-2^{32}-977$ and $n=2^{256}-432420386565659656852420866394968145599$.

  What is the major strength of secp256k1?

It forms with point addition a group of known 256-bit prime order $n$ with a generator $G$, such that we do not know an algorithm requiring much less than $\sqrt n$ steps to compute $a$ from $a\times G$, for random $a$ in $\Bbb Z_n^*$ (Discrete Logarithm Problem).
Note per comment: $G+G=2\times G$ in a group noted additively becomes $G*G=G^2$ in that same group noted multiplicatively. Similarly $Q=a\times G$ in a group noted additively becomes $Q=G^a$ in that same group noted multiplicatively. This is why solving either equation for $a$ is called the Discrete Logarithm Problem in the group considered.

More strongly, we know no algorithm requiring much less than $\sqrt n$ steps to tell sizably better than random if a triple what obtained as $(a\times G,b\times G,c\times G)$ or as $(a\times G,b\times G,ab\times G)$ for random $a$, $b$, $c$ in $\Bbb Z_n$ (Decisional Diffie-Hellman assumption).

secp256k1 is preferred over simpler groups with the same properties, notably Schnorr groups, because a point can be expressed much more compactly and the group law is much faster. secp256k1 is preferred over other groups with the same properties also built by point addition on an elliptic curve over a prime field, notably secp256r1, because the special form of $p$ for secp256k1 allows slightly faster calculation, with no known decisive drawback.

  Does that rely on the functions we choose for adding and doubling?

Yes it has to do with the group and its law, that is the functions we choose for adding and doubling.

  Taking any arbitrary functions $Q=f(P)$ and $Q=g(P,R)$ and then performing the multiplication function as long as the multiplication function is Surjective and Injective over the field $\Bbb F_p$, will we get the same level of security?

No, even with added constraints making the operation defined by $f$ and $g$ a finite group law. As a counterexample, take the group $(\Bbb Z_p,+)$ for some prime $p$: that defines point doubling $f$, point addition $g$, and we can take any non-zero element as $G$ with $n=p$. Point multiplication reduces to multiplication modulo $p$. That allows construction of the group as stated, yet the DLP is trivial, giving no security: given $Q=a\times G$ we can compute $a$ as $(G^{-1}\bmod p)\times Q$ where $G^{-1}\bmod p$ can be computed by the Extended Euclidean Algorithm.

Note: When restricted to point addition and doubling as in an axiomatic construction from $f$ and $g$, we can compute $-R$ as $(n-1)\times R$.


Can I switch out a private RSA Key, so that when decrypting a message, it is decrypted to a different message?

Update: This other answer (temporarily hidden on request of the organizer of a CTF) details a different approach to the problem, working for all values of $m$ and $c$, yielding valid keys, that even are plausible except for a larger-than-customary $e$. These private keys will work nicely for those RSA implementations (including OpenSSL, pycrypto, and many others) accepting values of $e$ up to about $N/2$ (which is well within PKCS#1 limits). That's what the OP was asking for, rather than the following exploration.

In both crypto Catch-The-Flags and actual security attacks, it is important to determine what makes values accepted or not. Here two things matter most:

Will something check that $c<N$ (which is often a requirement in actual uses of RSA). A comment by the OP suggests there's no such check.
What makes a private key unacceptable. Practice varies widely from most¹ to less stringent.

It happens that pycrypto (last indicated as applicable in a comment by the OP) is lenient on imported RSA keys, at least when using it's reference _slowcrypto.py code. See _importKeyDER and rsa_construct: as long as $N$, $e$, $d$, $p$ and $q$ are given, they are accepted as is. $d_p$, $d_q$, $q_\text{inv}$ are recomputed if imported from a key file or missing.

With such freedom, and $c^d\bmod N=m$ the only constraint involving $c$, if in the givens $m<c$ (which I'll assume) then we can choose $N=c-m$ and $d=1$ (with other key parameters 42). The condition $c^d\bmod N=m$ gets met, success!

However, that can fail if the RSA private key is used in CRT form (using $p$, $q$, $d_p$, $d_q$, $q_\text{inv}$), which is common². We may be able to improve on this by searching a small $k\in[1,c/m)$ dividing $c−m$ and making $N=(c−m)/k$ odd and composite (if these are requirements). For $p$ and $q$, any decomposition as $N=p\,q$ with $p>1$, $q>1$, and $\gcd(p,q)=1$ should do. We'd set $e=d=1$, passing a test $e\,d\equiv1$ for any modulus. The key import will recompute $d_p=d_q=1$ and $q_\text{inv}=q^{-1}\bmod p$ as needed. The key should now work with or without using the CRT. I do not rule out that we could get away with $p=1$ or $q=1$ (with the other equal to $N$); or that, if we got blocked by a test that $e\ge3$, it could be circumvented with $e=p\,q-p-q+2$ or $e=\lambda(N)+1$.

¹ Testing that the key was generated per FIPS 186-4 would include verifying that $N$ has exactly 1024, 2048 or 3072 bits, $N=p\,q$ with $p$ and $q$ primes each in interval $\left(2^{\left(\left\lceil\log_2(N)\right\rceil-1\right)/2},2^{\left\lceil\log_2(N)\right\rceil/2}\right)$, $e$ is odd and in $\left(2^{16},2^{256}\right)$, $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, $d_p=e^{-1}\bmod(p-1)$, $d_q=e^{-1}\bmod(q-1)$, $q_\text{inv}=q^{-1}\bmod p$. For 1024-bit $N$ the standard sets some extra requirement about $p\pm1$ and $q\pm1$, but these are never tested when accepting a key (contrary to the previous ones), because that would be very compute-intensive.

² We must however suppose that the advisable and common check that no fault crept in the computation of $m$ is skipped. That's performed by verifying $c=m^e\bmod N$, and that would fail even if we set an appropriate $e$ like $e=1$ or $e=\lambda(N)+1$. That would insure $c\equiv m^e\pmod N$, but not $c=m^e\bmod N$, since $c\ge N$ with our choice of $N$.


What's is the simplest possible example of using cryptography to sign a message?

It will be a bit of a journey to get to the answer for your question, but check out Khan Academy's crypto series: https://www.khanacademy.org/computing/computer-science/cryptography
They do a nice job of explaining how all the maths work with pretty small numbers. Even colors, which is an awesome analogy.


You have the classic problem of establishing a common secret key between the two parties before they begin exchanging any sensitive information. Consider Diffie-Hellman or - since you're dealing with a client/server setup and the risk of a MitM - a private key on the server side and then use public key encryption to establish the session key before communicating the password. This can be achieved with RSA, authenticated DH, ElGamal, and a few other methods.


Indistinguishability in the presence of an eavesdropper attack scenario

It's CTO, you are trying to figure out the plaintext given two ciphertexts. M1 and M0 are just bits of either 1 or 0.


Hardness assumption: Extracting $g^y$ from $g^x, g^{x+y}$?

No, this is (nearly) never hard.

To recover $g^y$ from $g^x,g^{x+y}$ all you need is a fast (ie polynomial-time) group operation (which is a given, because otherwise you'd have a hard time to come up with either value) and the ability to inverse fast (ie in polynomial time).

This follows from: $$g^y=g^{x+y-x}=g^{x+y}\cdot g^{-x}=g^{x+y}\cdot (g^x)^{-1}$$, where on the right you only have known values and fast operations and on the left you have your desired value.

Also note:

If you know the group order $q$, you can efficiently inverse as $a^{q-1}=a^{-1}$.
If you don't know the group order you likely still can invert quickly. For example you can still quickly find $a^{-1}\bmod n$ for composite $n$ (as is the case for RSA).
Inverting (finding $b$ such that $g^x\cdot b=1$) is not the same as computing the discrete logarithm (finding $b$ such that $g^b=X$).


On the Acceptability of a Naive Pseudo Random Number Generator

Why such naive and simple thing is not appealing

If you're talking about a method that internally generates 500,000 0 bits and 500,000 1 bits, shuffles them (by some method), and then outputs them, that would not be considered a CSRNG.

What is the "real" compass?

The compass is "can we devise an efficient test that distinguishes the output of the proposed CSRNG from the output of a truly random number generator (e.g. generated by someone flipping a fair coin)".  This test would take a sequence (generated by either the CSRNG or the random source) and generate a 0 or 1 answer; it is considered a distinguisher if it generates a 1 answer with a nontrivially different probability when given a sample from the CSRNG versus a sample from the random source.
In the shuffle-rng case, yes; one can ask for the output of 1,000,000 bits and count the '1' bits.  For the shuffle rng, you're get exactly 500,000 '1' bits; for the truly random source, you're get exactly 500,000 '1' bits rather rarely (with probability $c 10^{-3}$ for some $c$ not too far from 1 that I'm too lazy to look up).  That gives us a distinguisher, and hence the shuffle RNG is not a CSRNG.
In addition, you state:

the aforementioned tests [NIST, Dieharder, Next Bit Test] (which are extremely used as an evidence of the proposed algorithms in the literature).

Actually, when it comes to CSRNGs, those tests will rarely be used as evidence (and, quite frankly, when we come across a proposal which states them as evidence, that'll be taken as evidence that the authors are clueless when it comes to cryptography).  It's quite easy to make a generator that passes all those tests, but for which it is easy to make a distinguisher (and hence is not a CSRNG).
Those tests might be sufficient if you want to make sure that the RNG you're considering has good statistical properties, and so might be reasonable for noncryptographical work; however in crypto, we have considerably stricter requirements.


Encoding is Little-Endian ( section 5.1.2.)

All values are coded as octet strings, and integers are coded using
little-endian convention, i.e., a 32-octet string h h[0],...h[31]
represents the integer h[0] + 2^8 * h[1] + ... + 2^248 * h[31].

Key Generation (section 5.1.5)

Hash the 32-byte private key using SHA-512, storing the digest in
a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
used for generating the public key.

Therefore you have 32-byte private key that needs to be hashed with SHA-512.

Prune the buffer: The lowest three bits of the first octet are
cleared, the highest bit of the last octet is cleared, and the
second highest bit of the last octet is set.

This is for the lower 32-byte output of the SHA-512

Interpret the buffer as the little-endian integer, forming a
secret scalar s.  Perform a fixed-base scalar multiplication
[s]B.

Public key (5.1.5)

The public key A is the encoding of the point [s]B.  First,
encode the y-coordinate (in the range 0 <= y < p) as a little-
endian string of 32 octets.  The most significant bit of the
final octet is always zero.  To form the encoding of the point
[s]B, copy the least significant bit of the x coordinate to the
most significant bit of the final octet.  The result is the
public key.

Python Sample (Section 6)

   # Points are represented as tuples (X, Y, Z, T) of extended
   # coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

    def point_compress(P):
        zinv = modp_inv(P[2])
        x = P[0] * zinv % p
        y = P[1] * zinv % p
        return int.to_bytes(y | ((x & 1) << 255), 32, "little")

    def point_decompress(s):
        if len(s) != 32:
            raise Exception("Invalid input length for decompression")
        y = int.from_bytes(s, "little")
        sign = y >> 255
        y &= (1 << 255) - 1

        x = recover_x(y, sign)
        if x is None:
            return None
        else:
            return (x, y, 1, x*y % p)

    ## These are functions for manipulating the private key.

    def secret_expand(secret):
        if len(secret) != 32:
            raise Exception("Bad size of private key")
        h = sha512(secret)
        a = int.from_bytes(h[:32], "little")
        a &= (1 << 254) - 8
        a |= (1 << 254)
        return (a, h[32:])

    def secret_to_public(secret):
        (a, dummy) = secret_expand(secret)
        return point_compress(point_mul(a, G))


AES256-GCM - can someone explain how to use it securely (ruby)

Before answering your questions:
GCM is an authenticated encryption mode of operation, it is composed of two separate functions: one for encryption (AES-CTR) and one for authentication (GMAC).
It receives as input:

a Key
a unique IV
Data to be processed only with authentication (associated data)
Data to be processed by encryption and authentication

It outputs:

The encrypted data of input 4
An authentication TAG

The authentication TAG is an input to the decryption, if someone tampered with your associated data or with your encrypted data, GCM decryption will notice this and will not output any data (or return an error and you should discard the received data without processing it)

Now:

  Which implies that the IV still needs to be randomly generated and supplied for each encrypt with GCM, so why does the user in the
      StackExchange answer post say that we are not required to provide
      the IV?

GCM requires an IV, it is used both by AES-CTR and by AES-GMAC, so no matter what you are doing with GCM, you need to pass an IV.
It is required to be unique not necessarily random. Usually, implementations take a 96-bit IV and this is the recommended way to use GCM according to NIST.

  In OP's post in that StackExchange thread, OP uses tag = cipher.auth_tag. Is this by default 96? If so, is there a way to
      change it? Are there significant performance issues in using 128
      than 96?

By default, the authentication tag is 128 bit. You should provide the authentication TAG to the receiver of your message, so in some applications make sense to use a smaller tag. Keep in mind that the smaller tag you have, the more collisions you might get. If bandwidth is not an issue, use 128.

See also the detailed section on auth_tag([ tag_len ] → string here

  Does both the Associated Tag (cipher.auth_data) and the Authentication Tag (cipher.auth_tag) need to be kept secret? Or can they be kept open like the IV?

The associated data (incorrectly you wrote Associated Tag) is used for data to be publicly known. Examples are headers or destination address. So it's not required to be secret, but if need to encrypt everything, then set the associated data to "".
The authentication Tag is not required to be secret and in fact, it must be provided to the receiver unencrypted (like the IV).

  Finally, can someone explain further what is meant by the Associated Tag? The example in the answer that was given in OP's thread was that we can use a database id to ensure that the data belongs to a certain database user. Let's say that a user has the following database fields:

It looks like you confuse the authentication data and authentication tag.
The authentication data (or associated data) is something that you want to protect with authentication (if somebody modifies it you will know) but don't need to be encrypted. As stated above this is usually the case for headers which must be read by intermediate routers that can't decrypt the encrypted message.

The authentication Tag will depend upon the data you encrypt and on the associated data. So in decryption, you will need to process also the associated data or you will fail.

In your example, which is not very clear to me, you authenticate the primary id and the email and you encrypt the email. If you store in your DB both the IV and the TAG then you can decrypt the email if needed.
Without an authentication tag an attacker could copy the email of user1 to the email of user2, if he also copies the IVs, then when you will lookup for the email of user2 you will successfully decrypt the email of user1 without noticing anything.

Instead, if you also use a TAG and process as associated data the id of the corresponding user, then an attacker could not do the previous attack, because in decryption will we notice the associated data wasn't the one used in encryption and the operation will fail (you will know someone tampered with user2 data).


Implementing CBC Encryption Using Decryption

Your mode is essentially equivalent to CFB mode, except that:

you've reversed the order of the blocks in the message, and
you're using the block cipher in the opposite direction than usual.

Neither of those differences should have any direct security implications (since all standard block ciphers have the same security properties in both directions), so your scheme should be just as secure as CFB mode.


Efficiency of computing $e(P,Q)$ Vs $g^a \pmod{p}$?

Firstly, there is not one definition of a pairing.

A pairing is a bilinear function: you have three finite groups $G_1$, $G_2$ and $G_3$; a pairing is a function $e$ such that, for all $(g_1,g_2) \in G_1\times G_2$ and all integers $a$ and $b$, then $e(g_1^a,g_2^b) =e(g_1,g_2)^{ab}$ (I am here using multiplicative notation for the three groups). Why would you want such a function, in a cryptographic setting ? Basically, if you can have the following properties together:

$G_1$, $G_2$ and $G_3$ have known, finite orders.
Computations on these groups is easy.
The computational Diffie-Hellman assumption holds on the groups.
A pairing function $e$ can be defined and easily computed on these groups.

Then we can use the groups and the pairing function to power some interesting cryptographic protocols, in particular Identity-Based Encryption, which would be hard to obtain without pairing-friendly groups. To state things in a very general way, "normal" groups are for protocols which involve interactions between two parties (e.g. Diffie-Hellman) while pairing-friendly groups are for protocols which involve interactions between three parties.

So the cryptographic question is: do we know pairing-friendly groups ?

Right now, the only practical candidates we have for pairing-friendly groups are some special elliptic curves, which allow for a few distinct pairing functions (Weil, Tate, Ate and Eta pairings, the last two being subvariants of the Tate pairings). So we don't use pairings to "solve things" on elliptic curves; we use elliptic curves so that we can have computable pairings, which open the possibility of nifty advanced protocols.

(Note that initially, Weil and Tate pairings were first investigated as mechanisms to break elliptic curves. Fortunately, usual elliptic curves don't allow for computable pairings -- if you try to apply Weil or Tate pairing on a "normal" curve, you will find that it entails computations on integers which would not fit in the RAM of any computer, even if the computer was as big as the Moon. Pairing-friendly curves are in fact "slightly weakened curves" specially crafted so that pairings are computable, but not to the point that they allow a fast break of the said curves.)

Then there are details. For instance, in some protocols we want a symmetric pairing where $G_1$ and $G_2$ are the same group; while in other protocols we want the opposite: $G_1$ and $G_2$ shall be distinct groups, with, for instance, a one-way morphism from $G_2$ to $G_1$ (but not in the other direction). You will not use the same curves and the same kind of pairing for all cases.

So your question cannot have any simple answer except that "it depends". We can still give orders of magnitude: for a given security level (e.g. that of 2048-bit RSA), usual pairings will entail a computational cost which is about 8 to 12 times the cost of decryption with 2048-bit RSA. Don't try to read too much in that figure, though. What must be remembered is that, for instance, the BLS signature scheme allows for short signatures (shorter than DSA or ECDSA) but implies a computational overhead (for signature verification) which is not necessarily negligible.


From what I understand, I can use the IV as a counter, and the IV only has to be unique for each key (generating unique IVs isn't a problem). Correct?

Not exactly. The IV needs to be unique for each block per key. You can use a message counter for the Nonce component of the IV, then the block counter component is incremented from 0 in CTR.
IV = [96-bit Message NONCE][32-bit Block COUNTER]

Since the Nonce does not to be random or unpredictable, a message counter is appropriate. I use a combination of message counter, time code, and random number, all 32-bits, which helps against accidental nonce reuse if the counter gets maliciously reset. The key needs to be changed before the message counter overflows.
IV = [32-bit RANDOM][32-bit Timecode][32-bit Message CTR][32-bit Block CTR]

There are other methods that can be used. You may not want timecode information to be sent with a message, or have an attacker know how many messages you have sent. You can even encrypt the nonce with another key before using it in CTR mode, but you will need a custom setup for that because it can be done VERY wrong and break security.

Is it a problem for HMAC SHA256 if I construct a SHA block using a 32 byte key, 16 byte counter and 16 zero bytes for padding, or is it better to generate a 64 byte key so it fits in one SHA block and make another block for the counter and pad that block with zero bytes?

That will change how HMAC operates, which is to only have the key as the key input. HMAC per spec will only hash the key input if it is larger than the blocksize, so you can input 512-bits of "key" data, although it is not necessary to include a counter as part of the input. Appending the nonce to the key should not have any negative effect on security, it may even strengthen it, but I will not say that with any certainty. It is probably better to prepend the nonce to the message input if you want it to be authenticated, rather than adding it to the key. Including the counter with the key also eliminates a specific kind of performance optimization you can use.
You may want to consider SHA-512/256 or SHA-3-256 instead. If you have 64-bit code and CPU available it is faster, and should be more secure against current and unknown attacks. MAC using SHA3 is different, it prepends the message with the key.

If I want to add a salt to anything, I assume the salt is stored unencrypted. Correct?

A salt is a non-secret piece of cryptographic information, so it does not need to be encrypted. You may want to add some kind of redundancy check or rebuild parity (such as Reed-Solomon) to be associated with it, if you feel there is a chance it can be altered accidentally. Keep a backup somewhere, a password without the salt will mean a lost key.
Finally, make sure you are using different keys for your cipher and your MAC. The reason is that an attack on one of them can break both. While that may be unlikely, it is still a good idea to use separate keys, and is FIPS compliant.


Security of one-time-pad without $\bmod $ operation?

Given $c'$, can client $B$ learn anything about $b$ after decrypting the ciphertext before it performs $\bmod p$ operation?
Given $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ without involving $\bmod p$ operation can a semi-honest party learn anything about $b$ ?

These would appear to be the same question; it's just that in the first question, $B$ is handed a ciphertext for which he has the decryption key for;.
The answer: obviously, yes.  If $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ happens to be relatively prime to a prime $q$ (for example, $q=3$), then the attacker knows that $b$ also is relatively prime to $q$.  This doesn't immediately tell him the value of $b$; however it allows the attacker to deduce what $b$ is not.
If the attacker can factor $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$, he can then put together a short list of plausible values for $b$; however it is likely that $b$ and either $r_1$ or both of $r_2, r_2^{-1}$ have large enough prime factors to make this intractable (this assumes that $b$ was ultimately chosen in a way that didn't favor smooth numbers).
However, if the attacker is given two such encodings of the same $b$, $r_1 \cdot b \cdot r_2⋅(r_2)^{−1}$ and $r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1}$, then he is in luck; he can compute $\gcd( r_1 \cdot b \cdot r_2⋅(r_2)^{−1}, r'_1\cdot b \cdot r'_2⋅(r'_2)^{−1})$, and that's $r$, multiplied by a (likely small) integer.


Is there a feasible preimage attack for any hash function (no matter how deprecated) today?

Any hash function? Yes, certainly. In fact, most hash functions are not even designed to be resistant to preimage attacks. This includes CRCs and standard checksums like Fletcher. Creating preimages with them is trivial. The oldest popular hash algorithm is MD2 which has a preimage attack with a complexity of 273 and a memory requirement of 273 memory blocks. The complexity is low enough that modern technology could achieve the preimage, but memory requirements make it impractical.
There have certainly been older hashes that have not gained traction which were intended to be cryptographically secure but which ended up exhibiting preimage attacks. For example, there is a 233 operation second preimage attack on the very old 3-pass Snefru hash function.
If you want a more specific answer, you'll need to narrow down what kinds of hash functions you are talking about. I could give you a dozen old or experimental hashes that were either dropped or underwent tweaks which were vulnerable to practical preimage attacks. I could also list every non-cryptographic hash I know of, but I have a feeling you aren't asking for a list of standard checksums.


Security of non-standard use for AES-256-CTR?

This is insecure if more than a single secret is processed with the same password. Plus, OpenSSL has abysmally insufficient key stretching in its processing of the password, making brute force password search a concern.

The first (and worse) problem is because AES-CTR is a stream cipher, and thus malleable; and with no IV (-nosalt) it reduces to bitwise exclusive-OR with a key-dependent value. Knowing any secret $S_i$, the encrypted secret $E_i$, and another encrypted secret $E_j$, allows to find the other secret using $S_j=E_i\oplus S_i\oplus E_j$ (where $\oplus$ is bitwise exclusive-OR with arguments converted from Base64, and the result converted back to Base64).

Insecurity extends to changing a secret: knowing the old secret, its encrypted form before and after change, the new secret is revealed.

I have checked for key stretching built into OpenSSL enc in openssl-1.1.0f, that is the process by which the argument to -k is turned into an AES-256 key. What I found is not pretty. The man page rightly says "There should be an option to allow an iteration count to be included". If I did not got lost in the maze of C code with terse variable names and few helpful comments, there's an iteration count permanently set to 1 and in the case at hand, the AES key ends up as the SHA-256 of the argument to -k. That other answer is right to point that a better password hashing scheme is missing.

In addition, usual warnings apply: the argument to -k must be kept secret, and of course the hardest: it must be entered only on machines trusted from a hardware and software perspective.

Ah, a boring detail: openssl enc -base64 -A -d processes its input by multiple of 4 characters, and will ignore the last 2 characters of its 38-character input; correspondingly, the output of the script shown is only 36 characters. I see no fix to get the full 38-character capacity asked.

What's really needed is a 228-bit block cipher with a tweak (the slot index in the Yubikey), and a conversion of password to key with modern key stretching. Perverting openssl enc do that would be extremely hairy.


Create a bijective and invertible table that are depending on the cipher key

This is not secure, of course, but your proposal has many problems even as a bijective lookup table.

You have 16 bit keys but you use effectively only 2 bits to select one of $2^2$ rows. You have essentially only 4 distinct keys.
You have 8 bit inputs but you use effectively only 3 bits to select one of $2^3$ columns. This gives you many inputs ($2^5=32$) mapping to the same entry in the lookup table so no bijective map is possible.


How long would it take for a sha256 digest loop to reach the original hash or start cycling?

What is the shortest time it would take before it started cycling in a loop or back onto the same value if at all?

Well, strictly speaking, it's possible (albeit unlikely) that the first hash output would happen to be the initial value, and so the "shortest time possible" would be one hash.

However, lets do some analysis to see when it's likely to happen.

Let us assume that SHA-256 acts as a Random Oracle (it has no known ways it doesn't act like a Random Oracle on fixed length inputs).  Then, for a hash chain of length $n$, you have $n+1$ outputs, and hence $(n+1)(n+2)/2 \approx n^2/2$ pairs of outputs, and for each pair, we have a probability of $2^{-256}$ of them happening to collide (actually, this isn't exactly correct, but it's close); hence, if $n \ll 2^{128}$, we have a probability of circa $2^{-257}n^2$ of there being a collision (again, this isn't precisely correct, because the probabilities are not independent, but it's close).

So, to get a probability of $2^{-30}$ of falling into a loop, we would need a chain of length $n$ where $2^{-30} \ge 2^{-257}n^2$ or $n \ge 2^{113.5}$ long.  If your hardware can compute $2^{30}$ SHA-256 hashes per second (real hardware can't go this fast), then it'll take around 30 million times the current estimate of the age of the universe.

  How long would this take using modern GPU cracking techniques?

Well, a quick Google search finds the fastest GPU doing about 3 billion SHA256 hashes per second.  Let us assume that you have a GPU farm with a million of these GPUs, and let us also ignore the issue that computing a hash chain is an iterative process (and GPUs want to compute things in parallel).  Then, using the above estimates, to get to a 1-in-a-billion probability of finding a collision, we get the expected time down to about 10 times the age of the universe.

  For Extra marks - What is the probability this question would be asked in this forum 60 billion years ago?

Probability is 0; this forum didn't exist 60 billion years ago :-)


Is truncating a hashed private key with SHA-1 safe to use as the symmetric key for AES for data at rest?

I see no reason why that wouldn't be secure.
If you want to be sure, though, you could use a standard key derivation function such as HKDF or PBKDF2 to derive the symmetric key from the RSA key.

These functions are primarily designed for deriving encryption keys from low entropy-per-byte sources such as passphrases, but there's no reason why you couldn't use an RSA key as the "passphrase".  In any case, what they're designed to accomplish is to distill the entropy from a long but not entirely random input down into a pseudorandom output suitable for use e.g. as a symmetric encryption key.

(Many KDFs also include features such as adjustable work factor parameters for key stretching, useful for slowing down brute force attacks on low entropy passphrases.  However, for your application, you may safely choose a KDF without such features, or just set the parameters for maximum performance.)


Correction to Henricks answer: collisions are impossible (unless someone did something wrong).  That is, if:

$e$ is a proper RSA exponent (that is, relatively prime to $p-1$ and $q-1$, where $p$ and $q$ are the factors of $N$), and:
$m_1 \neq m_2 \mod N$ (that is, you're not trying to encrypt the same message twice),

Then we will always have $m_1^e \neq m_2^e \mod N$

This is rather implied by the fact that the RSA operation can be inverted using the decryption exponent; if two different messages collided, then that couldn't be inverted uniquely.


Yes, obviously if the CA generated your private key, they might keep it and share it with anybody.
Yes on both counts.

In fact, the normal way to generate a certificate -- whether for a Web server (TLS) or for yourself (S/MIME or TLS client) -- is to create a "Certificate Signing Request" and send it to the CA. The CSR includes your public key, not your private key; the private key never leaves your own computer.

See http://www.howtoforge.com/how-to-encrypt-mails-with-ssl-certificates-s-mime for step-by-step instructions using OpenSSL. Note: That page has instructions for creating a self-signed certificate, but further down it shows how to create a CSR and then sign it with a private CA. In practice you just send the CSR to the CA and pay them to sign it.

Assuming this is how you get your signed certificate, the only thing you lose when the CA is compromised is that somebody else could pretend to be you. That does sacrifice one of the purposes of S/MIME (authentication). Such forgeries are very easy to detect after the fact, so even if our security services have this capability, they could not use it very often without getting caught.


Why must s be kept secret in pedersen commitments?

I wonder why this is a requirement?

If the prover knows what $s$ is, they can open the commitment to any value they want.
Suppose that the commitment was $c = g^x h^r$, where $x$ is the originally committed value.
Then, if the prover knows $s$, then he can take an arbitrary value $y$ and compute $r' = r + s^{-1}(x - y)$; then, he can open the commitment as $c = g^y h^{r'}$
This would be accepted as a valid opening, because $g^xh^r = g^{x+sr} = g^{x + s(r' - s^{-1}(x-y))} = g^{y + sr'} = g^y h^{r'}$, and so he has successfully opened the commitment to a value selected after the commitment was published.


Can a MITM attack be applied to this construction?

Let $K^1,K^2$ be the key-streams generated by $k_1,k_2$.

Now define $E^1_{k_1}(m):=m\oplus K^1$ and $E^2_{k_2}(m):=m\oplus K^2$.

Note that $E^1_{k_1}(E^2_{k_2}(m))=m\oplus K^1\oplus K^2$.

You now have a straight double encryption and can apply the standard meet-in-the-middle attack now.

The implementation would use a known-plaintext pair $(m,c)$. You would now tabulate all $E^1_{k_1'}(m)=m\oplus K^{1'}$ and then try all $D^2_{k_2'}(c)=c\oplus K^{2'}$ and look for matches between $E^1_{k_1'}(m)$ and $D^2_{k_2'}(c)$.


How does the index of coincidence work in the Kasiki test?

Kasiki's test and the index of coincidence are used to attack a Vigenère cipher (or other polyalphabetic ciphers with small alphabet and small key size) - they both try to get the length of the keyword.

Kasiki's test gets probable prime factors of the keyword length, while the coincidence index test gets us an estimation of the absolute length of the keyword.

The original Kasiki test

This is what was done with CHR in your example: We look at repeated sequences of three or more characters, and at which distances they occur. We collect all these distances, and look at the prime factors of these.

The idea is that probably such a repeated sequence comes from the same plain text sequence, which then randomly hit the same keyword position. They will only hit the same position if their distance is a multiple of the keyword length.

Of course, we also can get random hits here (where different plaintext sequences got encrypted by different key sequences to get the same ciphertext sequence) - so be careful which prime factors to select. Either combine this method with Friedman's test mentioned below, or try different keyword length's for further analysis.

The coincidence index

The coincidence index of a text is defined as

Here n is the size of the alphabet, ml the number of occurrences for the character l, k the total size of the text. (δ(xi, xi) = 1 if the characters at position i and j are equals, else 0. But for calculation the second sum is more convenient.)

The coincidence index of a totally random text would be $1/k$ (and this is also the total minimum), while for natural language texts it is higher (0.067 for english, a bit higher for German). For a ciphertext encrypted by a monoalphabetic cipher it is still the same as for the original plaintext, for polyalphabetic ciphers (like Vigenère) it is between those.

(Actually, there are different definitions of coincidence index, but the values you have seem to use this one.)

Column-wise coincidence index to get the keyword length

You now take guesses at the key length h, and writes the cipher text in h columns. Then (if we guessed right) effectively the letters in each column are encrypted with the same key letter, e.g. monoalphabetically. We now calculate the coincidence index of each column individually. If we had a good guess at the key length, the coincidence index is near the coincidence index of the original plaintext column (which, if long enough, is a good approximation for the coincidence index of the used language).

In your example, for the lengths 1,2,3,4 the coincidence indices are only around 0.045, which is not much higher than 0.385, the expected value for a random 26-letter distribution. For length 5, you see a sudden jump: the indices are around the value for English (0.067). For 6, it will likely get lower again.

This will get you quite similar results as the Kasiki test, but is easier automated.

Friedman's method

Actually, Friedman derived from this a formula which spares us the calculation of each column's coincidence index - we just need the global coincidence index of the ciphertext (and the one of the natural language) to get an estimation of the keyword length.

While the English Wikipedia page does not mention this formula, the german language Wikipedia shows this:

Here $E_S$ is the expected coincidence index for our natural language, $\phi(T)$ the total coincidence index of our text, n the alphabet size, k the text length.

Your example

Using your value for m = 1 (which is the global coincidence index) and 26 for n, we get approximately

$$h ≈ \frac{(0.067 - 0.0385)\cdot k }{  (k-1)\cdot 0.045 - k\cdot 0.0385 + 0.067} = \frac{0.0285·k}{0.0065·k +0.022}$$

For example, for k = 1000 we would get h ≈ 4.36.  This is (together with the previous check from the column-wise coincidence index) a good hint at a keyword size of 5.

When we have the keyword length, we can use other methods, like frequency analysis on each "column", to crack the whole cipher.


Word size is not a term originating in cryptography. Rather it is a term which came from the area of computer architecture. Here it specifies either how many bits are transferred over a bus at a time or the size of a register.

When used in the description of cryptographic primitives (such as a compression function or a block cipher), it covers the size of the variables in the definition of the primitive. Ideally these variable sizes line up with the register size of the CPU they are going to be executed on.

In case of the SHA-2 family, the internal state is always 8 words, and the block size is always 16 words. The word size is either 32 bits or 64 bits.

This is why on a 32 bit CPU SHA-224 and SHA-256 are faster than the other variants, but on a 64 bit CPU they are slower than the other variants.


The Professor has really confused me here on this one on what the
  $\log 2$ mean? formula: $\text{Entropy} = \log(\text{Phrases})/\log 2$

If I understand the problem correctly, you are asking what the $\log 2$ is doing there in the denominator. This is essentially to ensure that the base of the logarithm (whether it's $10$ or $e$ or $2$) doesn't matter and you always get the computation result as a base-2 logarithm.

As a quick reminder: The base in a logarithm is the $b$ for which you are looking to find the $x$ such that $b^x=a$ for $x=\log a$.

  How many bits [are needed to] represent $x$ [phrases]?

So you have $x$ values and you want to know how many bits you need to have in order to identify all of them. Well, first note that 1 bit can address 2 values, 2 bits can address 4 values, 3 bits can address 8 values, etc. $n$ bits can address $2^n$ values. Thus we are looking for the smallest value $n$ such that $x\leq 2^n$. So we first compute a logarithm, to an arbitrary base, on both sides of the inequality, which yields $\log x\leq \log(2^n)=n\cdot \log 2\Leftrightarrow \log x/\log 2\leq n$, thus $\log x/\log 2$ bits are sufficient.


Is it safe to use MD5 in a proof of work system?

Currently, it is probably safe. There are preimage attacks on MD5 but they are only slightly better than brute force. With a proof of work that only requires the initial bits of the hash to match it would likely be easier to use brute force than try to apply any attacks on it.

However, I cannot see a good reason you would do that instead of using a more secure hash function, like SHA-256 – or SHA-256/128 if the output length must match.


How long would it take to brute force a 32 or 16 bit integer and which type of processor would brute force this in the shortest period of time

$4,294,967,296ops/4,000,000,000ops/s=1.07s$
$65,535ops/4,000,000,000ops/s=16.4μs$
2GHz twice that.
That's per-core. So 8 cores = 1/8 of a second or so. 64-core/128 thread 2GHz Threadripper = about 16ms.
A GPU will be even faster. It's recommended to brute force the entire 2^32 space for testing various numerical functions, it's fast and catches all the edge cases you might not have thought about. Brute forcing 2^64 values takes a month or so on a fast GPU, easily doable faster on a GPU cluster.
Edit, thanks to kelalaka: a Tesla V100 can run about $2^{47}$ SHA-1 hashes/hour. SO $720hours/month\times2^{47}Hashes/hour\approx2^{56}Hash/month$. That's about 182 months total, but each hash is substantially more work than just incrementing an integer, so a faster operation can likely be brute-forced in a month on such a GPU. Slower operations need a cluster, but such clusters can be rented from various cloud providers.


Which public key cryptosystem has the highest security/keysize rate?

Every public-key system that I have seen in the constrained space was based on elliptical curves instead of the classic RSA scheme.  This is primarily because cycle time is not as important as memory footprint and the 160-bits in ECC is believe to be roughly the same strength of 2048-bit RSA.

There seems to be some specific papers relevant to the MSP430 already.  If you wanted to explore the space, you should start by looking at the cost in memory of storing the long binary words and the cost of each operation in memory.  This will give you a good feel for the total memory, but not the calculation time.  You also will find that things will be much smaller if you do it in assembly.


Why does NIST want 112-bit security from 128-bit key size for lightweight cryptography?

From the security perspective, they should require 128-security.

Why?
NIST has a requirement for a minimum security strength of 112 bits for all things cryptographic, at least for the present.  You see it everywhere in their documents.  For example, in Transitioning the Use of Cryptographic Algorithms and
Key Lengths it says

For the Federal Government, a security strength of at least 112 bits
is required at this time for applying cryptographic protection (e.g.,
for encrypting or signing data). Note that prior to 2014, a security
strength of at least 80 bits was required for applying these
protections, and the transitions in this document reflect this change
to a required security strength of at least 112 bits.

Apparently, the cryptographers at NIST believe that 112 bits of security is sufficient for now.  128 bits is coming though.

SP 800-57, Part 1 includes a transition to a security strength of 128
bits in 2030; in some cases, the transition would be addressed by an
increase in key sizes.

Do note that this is their minimum requirement for the US Federal government, your requirements may be different.