The best solution is out of scope for this website. Just apply an algorithm that converts binary data to human-readable pronounceable text.

A simple solution, much like base-64 or diceware, would be to download a dictionary, split binary ciphertext into chunk, and replace each chunk by selecting the nth word in the dictionary. Join the words together using spaces as separators. Punctuation can be added randomly.

The process would be reversed by removing punctuation, splitting on spaces, looking up the index of each word, then joining the binary format of the indices together.

Format preserving encryption is undesirable in this case. English prose is not a simple data format. It would be hard to convert one message to another without leaking some information about the content and/or format of the text.

Chances are also pretty good that readers wanting to implement the same kind of thing as you would roll their own format-preserving encryption algorithm which is little more than a substitution cipher. (Replacing plaintext words with pseudorandom dictionary words, for example.)

Substitution ciphers can be broken with paper and pencil. They put puzzles in newspapers next to Sudoku and comics where people are challenged to do exactly that.

The primary reason I suggest looking at reversible methods of encoding binary data as English text is because I think it's best to work to work on the process of encrypting and of formatting data as two totally independent problems.

When you use normal strong encryption (don't forget authentication), the ciphertext will be indistinguishable from a randomly generated bit sequence. It won't matter if the binary-to-text conversion reveals something about the input because the input is ciphertext. Even side channels in the conversion algorithm wouldn't be a problem if the encryption implementation isn't vulnerable to side-channel attacks.

Therefore, I think you would have better luck if you took that half of the question to StackOverflow.

You should not have high hopes for the results. Procedural generation of text is a difficult problem. It's of interest to AI researchers, spammers, news media, anyone with customer support chat, and artists. Even the most successful algorithms produce text that seems unnatural

It's really hard to generate text which can pass for something written by a real person. Luckily (or not, if you use a spam filter) it's also somewhat hard for computers to tell the difference between human-generated and computer-generated text.

As for what kind of suggestion I would give if you asked on StackOverflow...

I would take word frequency and n-gram frequency into account if the purpose of the algorithm was steganography. "To" is more likely to appear in a normal sentence than "meteorite" is. "Go to" is more likely than "jump bread".

Think of using the auto-complete function on a phone. You could write a random sentence that might look legitimate at first glance pretty easily. You could randomly select the first one or two letters of each word and select from the options given to you. An n-gram based data encoding algorithm might produce pretty similar results.

If steganography is not required (say the purpose of making ciphertext human readable was so that you could send a message over an audio channel or less-than-reliable text channel) then the simple word list encoding method is what I would try. I would make sure the word list doesn't contain homophones or even words with similar or confusing spellings.

(See one of EFF's short diceware word lists. There is one where the first three letters of a word uniquely determines which number it corresponds to and no two words have spellings which are too close to make spellcheck hard. Something like this would be more resilient to typos and misunderstandings.)


How secure is this modified Bazeries Cylinder?

That depends on what you expect us to compare it to. I doubt you’re looking for an answer along the lines of “it’s more secure than Scytale, but less secure than AES”. Therefore, I will try to narrow it down a bit by saying that it is safe to assume it can not – in any way – provide the same security levels that modern cryptographic algorithms are able to provide. Some attacks are obvious; while others are merely a question of investing some time and effort to practically cryptanalyze the nitbits.

  My question is, could this coding system be broken by other than brute force methods ( which would be very tedious and expensive ) ?

Yes, it can. Mentioning only two of many examples: it definitely won’t hold for a second when applying a chosen-plaintext-attack or a known-plaintext-attack – which would both count as “valid breaks”.

Don’t get me wrong. It’s a nice design and it surely baffled some adversaries back in the days. Yet, in a (let’s just call it) “near-quantum” world, the cryptographic attractiveness  of this classical-cipher is nothing more than dust in the wind… a distant reminder of days where things like computers did not exist and security was easier to achieve and uphold.


How to construct a good PRF from a block cipher?

What you're looking for is often called a construction of a PRF with "beyond the birthday bound security," and you can probably find some constructions by searching on variants of that term.

For concreteness, this paper by Iwata (alternate link) almost gives a solution to your problem: The only deficiencies are that the resulting $F$ has inputs one bit narrower than $E$, and it does not achieve your definition of security for every $\varepsilon > 0$.  Specializing that construction down to your setting, and using your notation, it defines $F(x)$ for $x\in\{0,1\}^{b-1}$ as $$F(x) = E(x\|0)\oplus E(x\|1),$$
where $\|$ denotes concatenation.  Its proof applies for a number queries well beyond $2^{b/2}$, which is obviously non-trivially better than the direct $F(x) = E(x)$ construction.


why did oaep change from pkcs1 v2.0 and v2.1?

The answer is relatively simple, but I'll expand on the details of the changes from PKCS#1 2.0 to 2.1 in two additional sections below this answer.

On the padding with the zero valued byte

The I2OSP function - used during decryption - converts an integer to a statically sized, unsigned, big endian octet string or byte array. This function will always generate a number of $k$ octets as it is used, automatically left-padding with zeros. The OS2IP function is the reverse function.

However, as it is defined for PKCS#1 v2.0 / OAEP encoding, it will always operate over an octet string of $k - 1$ bytes. This isn't nicely symmetrical, and it doesn't clearly communicate to the reader that the top eight bits of the resulting number should always be set to zero. The result of the OS2IP function for $X_{k-1} || X_{k-2}... || X_0$ and $00 || X_{k-1} || X_{k-2}... || X_0$ are identical, because the big endian number is unsigned; even if the most significant bit is set, it doesn't get interpreted as the sign bit for a two complement number.

When implementing it in a language such as Java, the new description does make it clear that you can simply make sure that the encoding starts with 00 and then convert to a number using a converter that expects a signed value. In general it is also better to always operate on numbers with a known encoded size.

On the padding size

This section explains why the padding with the zero byte is required at all.

In PKCS#1 v2.0 the encoding operation for the encryption operation in 7.1.1 is mentioned in its own section 9.1.1.1 (not 9.1.1.2, I'll notify the author of the bug). In 2.1 it seems that this created too much complexity and the encoding operation has been integrated into the description of RSA OAEP encryption in section 7.1.1.

It is a requirement for the padding is to create an octet string (or byte array) that can fit into an integer of size $kLen-7$ or $kLen-8$ bits where $kLen$ is the key size in bits (not mentioned in RFC 2437).  RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. The reason why the padding must be smaller than the key size in octets is because RSA is defined for any key size, including a key size of, for instance, $kLen=1025$ bits. In that case the size of the octet strings will be $k=129$ bytes rather than $k=128$ bytes.

However, the integer calculations are still using a 1025 bit modulus. If one of the first 7 bits of the first bit would be set then the input of the calculation would be higher than the modulus, so the modular operation with the private exponent would not result in the same octet string.

Note that because of these kind of complexities many RSA implementations only handle key sizes or an 8 bit or 32 bit increment. It is strongly recommended to use a key size of 1024 bits or (preferably) higher with a key size of the form $2^x$ (e.g. $2048$) or $2^x + x^{x-1}$ (e.g. $2048 + 1024 = 3072$).

On the encoding function

This section explains another difference between 2.0 and 2.1: the use of a separate encoding function.

There was also a comment by Artjom B about the size of $dbMask$. The size of $dbMask$ is not different for the different descriptions of the encoding scheme. So this section should be seen as a supplement to the answer.

RSA signature generation already uses a padding of $kLen-7$ bits so RSA encryption uses a padding that is $kLen-8$ bits. This means that the result of the encoding must be an octet string of one octet less as the key size / modulus size in octets. This is why the encoding function is called using $k-1$:

EM = EME-OAEP-ENCODE (M, P, k-1)

and if you look carefully then you'll see that $emLen = k-1$ in the algorithms of EME-OAEP-ENCODE, for instance the message length should be $emLen-1-2hLen$.

Now in PKCS#1 v2.1 the EME-OAEP-ENCODE is missing; it has been integrated in the description of OAEP encryption itself. This has the disadvantage that other encryption schemes (for instance those based on ElGamal encryption) cannot directly reference the encoding operation within the standard. That is however not a main objective for a standard that describes RSA. On the other hand the standard is more clear because it doesn't need to mention $emLen$ at all; it can directly reference $k$, possibly avoiding off-by-one errors in implementations. Furthermore, it simplifies reading the description of OAEP, as readers do not have to switch back and forth between 7.1.1 and 9.1.1.1.


How to Prevent Correlation Power Analysis Attack on AES?

DPA-resistant cores
Masking (attempt to conceal the intermediate date processed by modifying the data such that the complete secret is never processed simultaneously)

For example you can introduce s-box shuffling in AES as a software solution to decrease the likelihood that the attack succeeds.

Pseudo Code s-box shuffling from Figure 2 of www.indjst.org/index.php/indjst/article/download/61626/48132:

Begin
// The assignment of Round Key
Byte RK[11][16]
// The generation of Random Value
shuffle = rand()%8
// The execution of Key Expansion
KeyExpansion(Byte Masterkey[16], Byte Roundkey[11][16])
// The assignment of the execution of eight-shuffling AES
(*ptr_shuffle[8])(Byte PT[16], Byte RK[11][16], Byte CT[16])
ptr_shuffle[0] = &AES_Original1
ptr_shuffle[1] = &AES_Original1_Macro
ptr_shuffle[2] = &AES_Original2
ptr_shuffle[3] = &AES_Original2_Macro
ptr_shuffle[4] = &AES_Bertoni
ptr_shuffle[5] = &AES_Bertoni_Macro
ptr_shuffle[6] = &AES_T-Table
ptr_shuffle[7] = &AES_T-Table_Macro
// The execution of eight-shuffling AES
ptr_shuffle[shuffle](PT, RK, CT))
End


Does the size of the cryptogram affect the possibility of breaking it?

Maybe you can share some more information about what the attack model is?
For all practical purposes it does not matter how much data an adversary obtains - a secure cryptosystem (when used correctly) guarantees the secrecy of the data it encrypts.


Is Quadratic Arithmetic Program NP-complete?

QAP, like QSP, are a characterization of NP. They naturally capture arithmetic programs. Their advantage over QSP is that they lead to more efficient SNARGs for statements whose verification procedure is compactly represented by an arithmetic circuit. They have at least the same power, and you can represent the verification algorithm of arbitrary NP languages (hence also NP-complete languages) using them. Note that they are a computation model, not a language, so it does not mean anything to say that QAPs (or QSPs) are NP-complete - but they do capture all of NP.


Well, this curve has 8 affine points and I would like to share the way to find them all.
First of all, we make a square table till 10 as we have  field ${\mathbb{Z}}_{11}.$  (so 11-1=10)
Below is the table(also calculate its mod 11 values) :
  ┌───────┬─────┬────┬────┬────┬────┬────┬────┬────┬─────┬─────┬────┬
  │   #   │  0  │  1 │  2 │  3 │ 4  │ 5  │ 6  │  7 │  8  │  9  │ 10 │
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴
  │Square │  0  │  1 │  4 │  9 │ 16 │ 25 │ 36 │ 49 │  64 │  81 │ 100│
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴
  │Mod 11 │  0  │  1 │  4 │  9 │ 5  │ 3  │ 3  │  5 │  9  │  4  │  1 │
  └───────┴─────┴────┴────┴────┴────┴────┴────┴────┴─────┴─────┴────┴

Re-arranging the equation so that we have $y$ on the left-hand side
$y^2 = \frac{1-x^2}{1+3x^2}$
Now we start putting form $x = 0$  until $x = 10$  in the above equation and get the value of $y$ each time. If the value of $y$ is one of the complete squares mod 11 i.e row 3rd of the table then the corresponding value in row 1 is the $y$-coordinate.
$y$ is calculated as mod 11. Even if the value of $y$ is in fractions.
For $x=0$ we get $y^=1$ which exists in row 3rd i.e it is a complete square. Now value 1 in 3rd row corresponds to value $1$ and $10$ in row 1. So we get 2 points here i.e. $(0,1)$ and $(0,10)$
For $x=1$ we get $y^2=0$  this also exists in 3rd row. So corresponding values in 1st row are 0. So here we have only 1 point $(1,0)$
For $x=2$ we get $y^2=4$ this also exists in the 3rd row. So corresponding values in 1st row are 2 and 9. So here we have 2 points i.e. $(2,2)$ and $(2,9)$
For $x=3$ we get $y^2=6$  which does not exist in the 3rd row of the table. So no corresponding value of $y$ will be there, hence no point will exist at $x=3$
For $x=4$ we get $y^2=8$   Not in the table (not a complete square) hence no points here.
For $x=5$ we get $y^2=2$   Not in the table (not a complete square) hence no points here.
For $x=6$ we get $y^2=2$   Not in the table (not a complete square) hence no points here.
For $x=7$ we get $y^2=8$   Not in the table (not a complete square) hence no points here.
For $x=8$ we get $y^2=6$   Not in the table (not a complete square) hence no points here.
For $x=9$ we get $y^2=4$   Exists in table (hence it is a complete square) So corresponding points are: $(9,2)$ and $(9,9)$
For $x=10$ we get $y^2=0$   Exists in table (hence it is a complete square) So corresponding point is: $(10,0)$
So all the affine points are
$(0,1)$ $(0,10)$
$(1,0)$
$(2,2)$$(2,9)$
$(9,2)$ $(9,9)$
$(10,0)$
Note that we can calculate solutions for $x = 0, 1, ... , \frac{11-1}{2}$ and use symmetry in $x$ in $\mod 11$ ($10 \equiv -1 \mod 11$, $9 \equiv -2 \mod 11$, etc.) as well to obtain all points, namely $(x,y) => (x, -y) \wedge (-x, y) \wedge (-x, -y)$.
In the example above you get all points calculating all solutions until $x=5$. The solution for $x=9 \equiv -2 \mod 11$ is obtained using symmetry for $x=2$ ($(2,2) => (2, -2) = (2, 9) \wedge (-2, 2) = (9, 2) \wedge (-2, -2) = (9, 9)$) and the solution for $x = 10 \equiv -1 \mod 11$ is obtained using symmetry for $x=1$.


Calculating the Min Entropy of a string of bits

If your probabilities are exact, then your math is right. But even if they are off by the slightest amount (e.g. $2^{-10000}$), it doesn't hold any more. For a practical system like timestamps in a computer, it's quite unlikely that your have exact values for the probabilities. If those probabilities are average measurements, then the resulting entropy is also only an average and not a lower bound (minimum).


Hide secrets in an article composed with Machine Learning?

To go for the low-hanging fruit, train your machine to be really good at swapping synonyms based on context.  Then just have it find suitable synonym replacements for every word of covertext located at a multiple of your magic number.

EDIT:  I don't have enough reputation to comment so I'll reply to another post here.  Someone objected that the keyspace is quite small.  For example, there are only a handful of possible keys in the OP's example, only one of which yields meaningful text.  But this can be remedied quite easily.  Instead of using simply the first letter of a word, use the letter at an arbitrary position determined by a second key, wrapping around if the word is too short.

For instance, take the key KEY as numerals derived from the position of K, E, Y in the alphabet: 11 5 25.  Choose a magic number like 3, and beginning with the first word, hide a secret letter at position 11 (wrapping around if the word is shorter than 11 characters). In the 3rd word after (since 3 is your magic number) hide the next secret letter at the position indicated by the next numeral of your key, etc.

An apple is healthy to eat. They keep doctors away. You can cook them
in pockets of bread and enjoy!
[A]n apple is heal[t]hy to eat. [T]hey keep doctors aw[a]y. You can
[c]ook them in poc[k]ets of bread and enjoy!
Word 1, position 11: A

Word 3, position 5: T

Word 6, position 25: T

Word 9, position 11: A

Word 12, position 5: C

Word 15, position 25: K

This approach is not trivially broken.


Why do we assume un-security of communication channel on every cryptography system

The goal of cryptography is to create these secure communication channels. However, keep in mind that a secure channel is more than just an encrypted channel. A secure channel should be able to provide confidentiality (using encryption), data integrity (using something like signatures), and data authentication (using something like certificates, MACs). The goal of cryptography is to create these properties to make a "secure channel" out of an unsecured channel.

Note that some cryptosystems build on top of other types of channels. For instance, in public-key cryptography, you generally need to assume that you have access to a authenticated channel for key exchanges (which is a stronger assumption than a completely unsecured channel).


Proving that a function is not a OWF (One-way-function)

To prove that a function is not a OWF, you can exhibit an inversion algorithm and show that your inversion algorithm succeeds in inverting the OWF with non-negligible probability.  In other words, if we randomly choose $x$, compute $f(x)$, feed $f(x)$ to your inversion algorithm, and let $x'$ denote the output of your algorithm, then you need to show that $\Pr[f(x')=f(x)]$ is non-negligible.  Thus, this is average-case hardness, averaging over all possible inputs to the OWF.


Are SHA-2's $\mathit{Maj}$ and $\mathit{Ch}$ functions non-linear?

Theses are the "Majority" and "Choose" Boolean functions, respectively; they are linear functions by definition.  Since there is no multiplicative or exponential element in the formulae then any linear combination of these would also be linear.

As for their applicability to S-Block "Substitution" block ciphers, if you design an algorithm using the functions to generate ciphertext characters based upon plaintext, keycode and substitution alphabet inputs then, yes, they could be used.


How can we effectively compute the sqrt of some element in the group?

TL;DR: Efficient algorithm only exist in specific cases. The problem, in its full generality (finite abelian groups) is equivalent to the integer factorization problem.

  How can we effectively compute the square root of an element in a group?

One case where we can compute a square root is when the group order is known and it is odd.
Any element $g$ in a group has the following property: if $q$ is the order of the group, then $g^q=1$. This is due to Lagrage's Theorem. Equivalently, $g^{q+1}=g$. If $q$ is odd then $\frac{q+1}{2}$ is an integer, hence we can compute $h:= g^{\frac{q+1}{2}}$, which is a square root of $g$.

Another case is the following: Assume $G$ is isomorphic to the direct product group of $k$ copies of the group of order 2 and a group of order odd $q$:
$$
G \simeq \mathbb{G}_q \times  \prod_{i=1}^k \mathbb{Z}_2
$$
where $\mathbb{G}_q$ denotes a group of order $q$ and $\mathbb{Z}_2$ the group of order 2. Also, importantly, assume you know how to compute this isomorphism.

In the group of order 2, the non-unit element is its own inverse, hence it has no square root. This implies the following: Let $g \in G$. Apply the isomorphism to get the representation of $g$ as an element in the direct product above: $g = (g', g_1, ..., g_k)$, where $g' \in \mathbb{G}_q$ and $g_i$ is in the $i$'th $\mathbb{Z}_2$. If there exists $i$ such that $g_i$ is not the unit element, then $g$ does not have a square root.

On the other hand, if $g_i$ is the unit element in all copies of $\mathbb{G}_2$, then the problem reduces to the case of a group of odd order: you just raise $g$ to the power of $\frac{q+1}{2}$.

  Another question, if $m$ is an odd number, can we be sure there is no answer?

No. The above explains this too. Actually, for the above, you don't need to know $m$ (which is typically the case).

  Is it possible to find another generator $g_1$ and an even number $k$ that satisfy the element is equal to $g^k$?

The above addresses this too, since it fully describes the set of squares in the group.

EDIT:

In "Oded Goldreich, Computational complexity: a conceptual perspective" it is shown that finding square roots modulo composite numbers is a computational problem equivalent to integer factorization. Hence, don't expect any "general purpose" algorithm, only algorithm for special cases. One such case is the multiplicative group of invertible element in a field of prime size $p$ - called Tonelli-Shanks.


How to convert ECDSA P256 curve signature to SECP256K1 curve?

There is no way to convert a signature with one curve to another. If there were, one could trivially forge signatures by starting with an insecure curve and converting it to a signature in a secure curve.


How badly does disclosing an M-bit prefix of an N-bit private key compromise security?

I further assume you mean a DER-encoded unencrypted PKCS#8 RSA key, since you wouldn't care about exposing an encrypted key, and it's a conventional two-prime key with equal-size factors (each 1024 bits) and the ubiquitous e=65537 using the standard PKCS#1 CRT-form representation.

I also note that 21 bits is a really odd amount to disclose: not 2 octets, not even 2 and half octets, but 2 and 5/8 octets? Anyway ...

It compromises ALMOST CERTAINLY NOTHING.

Unencrypted PKCS#8 is a SEQUENCE that contains a version INTEGER, an AlgorithmIdentifier and an OCTETSTRING containing the encoding of the key, which for PKCS#1 is a SEQUENCE containing another version INTEGER, then the modulus, then the public exponent, and only then the private exponent and other private values. For RSA the AlgorithmIdentifier is one of two fixed values depending on whether the inapplicable parameters are encoded as NULL or omitted.

Thus at least the first 20 octets of the PKCS#8 encoding are fixed values independent of your key, EXCEPT that the length field of the outer SEQUENCE reflects the length of the inner SEQUENCE, which in turn varies slightly (up to 4 octets) depending on whether the private exponent d happens to be >= 2^2047 and the three CRT values (dP, dQ, qInv) happen to be >= 2^1024, and thus need "extra" sign octets. If an adversary knows the PKCS#1 length (and thus the PKCS#8 length) is at its minimum or maximum, it gives less than 1 bit information about d. In between the min and max I don't think there are any usable relationships between dP dQ qInv and d but I can't rule it out, so worst case up to 1 bit there also. However the length ranges 0x04BC to 0x4C0 or 0x04BA to 0x04BE and is in the third and fourth octets, so IF your 21 bits are big-endian (that is, all of the first two octets and the top 5 bits of the third octet) then it includes no information about the part of the length that could be useful.


Is there an encryption scheme that provides $Pr\{M_1 = m_1\wedge M_2 = m_2 | C_1 = c_1 \wedge C_2 = c_2\} = Pr\{M_1 = m_1 \wedge M_2 = m_2\}$

let $M_1,M_2$ be a distribution where $\exists m_1,m_2$ that $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} \neq 0$ and $m_1 \neq m_2$ it is clear that such distribution exist.

suppose $\Pi$(Gen,Enc,Dec) satisfy the question's statement and $|M|\neq 1$

Let $m_1\neq m_2$ but $c_1=c_2=c$

$^{(*)}$ $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}=Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $

if $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}\neq 0$
then $m_1,m_2$ are encrypted with the same key the above probability is not equal to 0 so

$Pr\{k\leftarrow Gen();c=Enc_k(m);\hat{m}=Dec_k(c):m=\hat{m}\} \neq 1$ but this is in paradox with $\Pi$ being a encryption scheme.

so $Pr\{M_1=~m_1 \wedge M_2=~m_2 |C_1=~c \wedge C_2=~c\}= 0$ and according to $^{(*)}$ $ Pr\{M_1=~m_1 \wedge~M_2=~m_2\} $ is also equal to zero $\forall m_1 \neq m_2$ which is also in paradox with the way we chose our distributions.

So no encryption scheme could satisfy $^{(*)}$


Does the IV need to be known by AES (CBC mode)?

The initialization vector is XORed against the first plaintext block before encryption in CBC mode, as shown in the Wikipedia article on block cipher modes. After the first block is decrypted, you still have an intermediate value which has been XORed with the plaintext — without this, you have little hope of recovering the plaintext. However, you do not need the IV to decrypt subsequent blocks.

You could perform CBC in a way that would remove the need to know the initialization vector (note: this is not recommended or encouraged, just pointing it out for the novelty). If you use a null IV and use a random value for the first block of plaintext, you can discard this value and only transmit the ciphertext. Note that this actually gains you nothing, because now the ciphertext is one whole block longer!


DES Encryption: Looking for results for each round of encryption/decryption to debug code

Should they be the same only backward? Decryption round 1 output = encryption round 16 output?

Yes, that is correct; the decryption subkeys are exactly the encryption subkeys in the opposite order.
I don't have the per-round test vectors you were asking for, but I can make this suggestion: if you have DES working in the encrypt direction, you can generate the test vector yourself; recording the state of the block after each round.  Then, when you attempt to decrypt the block, the per-round block state is supposed to traverse the same path backwards; for example, if the block state after encryption round 15 was X, then the block after after decryption round 1 should also be X.  If decryption isn't working, then somewhere during the cipher it went wrong; by looking at the per-round states, you should be able to narrow it down to a specific round.


A website that identifies an RNG from its output

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from.

As you correctly identified this would present an immediate and probably devastating attack to any cryptographic PRNG as it indeed would allow you to easily distinguish a random string from a PRNG output, something cryptographers try to make impossible efficiently.

However, there might be some truth to the story. Here are the two cases I know of where it would be possible:

The website identifies the output to be from the infamous OpenSSL Debian bug.
The site is given an RSA public key and can tell which implementation produced it as the prime-search strategies vary a bit in a secure way between different libraries. This was presented at Usenix Security 2016 (PDF) and perhaps someone converted this into a website.


RSA function over $Z_t^{*}$ where $t$ is prime

In RSA, $\phi(N)$ is hidden and this is why nobody could calculate private key. For a prime modulus, order of multiplicative group is not a secret. Well, this question looks like encouraging your own thinking of RSA and related arithmetic, so please keep digging in.


Common modulus attack on RSA when the 2 public exponents differ by a single bit

Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property

$\gcd(e, e_2) = \gcd(e, e-e_2)$

Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime factor.  On the other hand, we know $e$ is odd (because it is an RSA exponent), and so $e$ and $e-e_2$ do not have any prime factors in common (and hence, $e$ and $e_2$ do not either).

This result implies that the method you already have (which is effectively using the Euclidean method on the values $e$ and $e_2$ to compute $M^{gcd(e, e_2)}$) will give you $M$.


NTRU Euclidean algorithm the inverse of f modulo p

I'll try to follow a similar notation to the example on wikipedia
Our initial inputs are $p(x) = x^{11}-1$ which defines the ring and $a(x)=-x^{10}+x^9+x^6-x^4+x^2-1$ and working mod 3 rather than the mod 2 example on wikipedia.
For step 1 we have quotient $q_1(x)=2x+2$ and remainder $r_1(x)=x^9+x^7+x^6+2x^5+2x^4+x^3+2x^2+1$ so that $t_1=x+1$.
For step 2 we have quotient $q_2=2x+1$ and remainder $r_2=x^8+2x^6+x^4+x^3+2x^2+2x+1$ and $t_2=x^2$.
For step 3 we have quotient $q_3=x$ and remainder $r_3=2x^7+x^6+x^7+x^4+2x^3+2x+1$ and $t_2=x^3+x+1$.
For step 4 we have quotient $q_4=2x+2$ and remainder $r_4=x^6+2x^5+x^4+x^2+2x+2$ and $t_4=2x^4+2x^3+2x^2+2x+1$.
For step 5 we have quotient $q_5=2x$ and remainder $r_5=2x^5+x^4+2x^2+x+1$ and $t_5=2x^5+2x^4+x^3+2x^2+2x+1$.
For step 6 we have quotient $q_6=2x$ and remainder $r_6=x^4+2x^3+2x^2+2$ and $t_6=x2x^6+2x^5+x^3+x^2+1$.
For step 7 we have quotient $q_7=2x$ and remainder $r_7=2x^3+2x^2+1$ and $t_7=x2x^7+2x^6+2x^5+2x^3+2x^2+1$.
For step 8 we have quotient $q_8=2x+2$ and remainder $r_8=x^2+x$ and $t_9=2x^9+x^8+2*x^7+x^5+2x^4+2x^3+2x+1$.
For step 9 we have quotient $q_9=2x$ and remainder $r_9=1$ and $t_9=2x^9+x^8+2x^7+x^5+2x^4+2x^3+x+2$, which is the required inverse.
I'll leave the mod 32 example as an exercise (sagemath is your friend).


What are the problems with Diffie-Hellman groups 3 and 4 (RFC 2409 + RFC 2412)?

There is a relatively obscure attack, named the GHS attack after its authors Gaudry-Hess-Smart, that applies to binary curves where the exponent is not prime. In this case $155 = 5\cdot 31$ and $185 = 5\cdot 37$.

The main idea of the GHS attack is to map the discrete logarithm from an elliptic curve over, say,  $\mathbb{F}_{2^{155}}$ to a hyperelliptic curve of genus $16$ over $\mathbb{F}_{31}$.

Unlike elliptic curves, hyperelliptic curves of high enough genus have better-than-generic algorithms for computing discrete logarithms, and therefore the security of many curves over $\mathbb{F}_{2^{155}}$ and $\mathbb{F}_{2^{185}}$ is going to be smaller than you would expect from a proper strong curve. There are a few papers analyzing the $\mathbb{F}_{2^{155}}$ and $\mathbb{F}_{2^{185}}$ cases, and they largely conclude that such fields—that is, binary fields of composite degree—should not be used for elliptic curve cryptography.


Usage of pairings in proxy re-encryption algorithm

Is $Z^{ak}$ the same as $e(g^a,g^k)=e(g,g)^{ak}$?

That's correct: by the bilinearity property of the pairing $Z^{ak}=e(g,g)^{ak}=e(g^a,g^k)$.

  And is $mZ^k$ the same as $e(g^k,g^k)=e(g,g)^{k^2}$?

No it is not. $mZ^k$ is the group operation of $\mathbb{G}_2$ applied to $m$ and $Z^k$.

  I would like to understand the intermediate steps like I have for an ElGamal.

The first-level decryption algorithm, given a ciphertext $c_a=(\alpha,\beta)$, as per their specification involves computing $\beta/\alpha^{1/a}$. If the ciphertext is properly formed then $\alpha=Z^{ak}$ and $\beta=mZ^k$ and therefore
  $$\frac{\beta}{\alpha^{1/a}}=\frac{mZ^k}{(Z^{ak})^{1/a}}=\frac{mZ^k}{Z^k}=m.$$


In order for a protocol to be secure, the output of any adversary must be simulatable, including that of an adversary that just outputs its input.

Moreover, note that in this case the protocol instructs that $P_1$ send its input bit $x$ to $P_2$, so in the case where $P_2$ is corrupted, it can output the input of $P_1$, so that must be simulatable as well.


How does sending compressed points in ECC can limit the attacker's capabilities?

If the implementation is using uncompressed point exchange, The attacker gets an opportunity to supply points to Bob that are not in the Curve which was selected by Alice and Bob. The attacker will supply points to Bob that are in curves of a lower order which makes it possible to estimate Bobs secret.
Therefore if the implementation ensures that Bob has to calculate the point then he will come to know that the point being provided is not on the curve selected by Alice and Bob in the first place and will result in coming to know about the attack or the corruption.
Two basic constructs in ECC are the standard curves and Implementation by programmers. The argument is should use of compression be specified in the standard or should be left to the implementation. Since compression is so important for ensuring security it should be made part of the standard( As per the presenters ) to prevent implementation errors.


Inconsistent terminology for ciphers and algorithms

It sounds like you're basically asking for a definition of the word "cipher".  I agree that it's somewhat fuzzy and complicated — that's mainly because "cipher", on its own, is not a precisely defined technical term in modern cryptography, but a descriptive word whose meaning, like that of most other English words, has evolved gradually over time.

So, let's start from the beginning.

The word "cipher", as any good dictionary can tell you, originally comes from the Arabic word ṣifr (صفر), meaning "empty" or "nothing", and also the numeral zero.  As the Arabic numerals (notable, compared to the older Roman numerals, for their inclusion of a symbol for zero) were introduced to Europe, this word was adopted into Medieval Latin as cifra, whose meaning broadened to cover any of the Arabic number signs, or even any other strange sign or symbol.  (These senses are still retained e.g. in the French word chiffre, whose meanings include "numeric digit", "figure" and "cipher".)

It's not fully clear how the word used for Arabic digits came to be also applied to any kind of secret or obscured writing system, but given that the new number system was only adopted gradually, and long remained, in the public view, a strange and incomprehensible notation only used by a few learned men and secretive merchants (who, being also generally interested in confidentially recording and discussing matters financial and political, were also early adopters of cryptography), it is perhaps not surprising.

In any case, by the 19th and early 20th centuries, during the peak days of the "classical cryptography" era, before the introduction of computers and modern cryptographic theory, methods of transmitting encrypted messages had come to be generally divided into two broad categories: "codes", which replaced words or entire phrases with specific agreed-upon symbols (often distributed in "code books"), and "ciphers", which were based on replacing and/or rearranging individual letters in a message.
While codes were generally regarded as more secure (since a good code offered fewer opportunities for a cryptanalyst to find patterns in the message), ciphers had the definite advantage of being able to encrypt any messages, even ones that the compiler of the code book had not anticipated.

The ciphers used in the classical era were, in turn, grouped into several distinct types, such as:

substitution ciphers, which worked by transliterating the message into a secret alphabet; and
transposition ciphers, which instead used the normal alphabet, but shuffled the letters of the message into a seemingly random order according to some prearranged pattern.

Of course, an advanced cipher might combine both of these types, and there were even systems, like the French Great Cipher, which combined elements of ciphers and codes.  Also, while the simplest substitution ciphers used just a single fixed secret alphabet, more advanced schemes — like Bellaso's chiffre indéchiffrable, commonly misattributed to Blaise de Vigenère, or the later rotor machine ciphers of the 20th century — used a different alphabet for each letter of the message, making them considerably harder to break.

The electromechnical rotor machine ciphers, such as the famous German WWII Enigma machine, were the state of the art for much of the early and mid-1900s, during the transition period from classical to modern cryptography.  They (like the older polyalphabetic substitution ciphers of Bellaso, Vigenère and others) may be seen as early examples of stream ciphers, although the term "stream cipher" did not really enter the common vocabulary before the 1970s:

Graph of the relative frequencies of the terms "stream cipher", "block cipher", "substitution cipher" and "transposition cipher" between the years 1900 and 2000, generated using Google Ngram Viewer.

What happened in the 1970s was the invention of a new kind of cryptographic tool — the block cipher, developed in its modern form by Horst Feistel at IBM, who designed the Lucifer cipher that eventually became DES.  (Of course, the idea was not entirely without precedent: the Hill cipher, from 1929, had also operated on blocks of characters, as did the various earlier polygraphic substitution ciphers, and of course much of the general theory had been introduced by Claude Shannon in 1949.  Still, in many ways, Lucifer and DES did represent a strong and radical departure from earlier traditions in civilian cryptography.)

The thing about block ciphers is that, unlike stream ciphers (a term which, in its broadest sense, covers pretty much every practical encryption system capable of encrypting arbitrarily long messages), a block cipher is not really very useful on its own: it's great if you just happen to need to encrypt blocks of, say, 64 or 128 bits into other blocks of the same length, but how often is that the case?

To make a block cipher practically useful, you will need to combined it with some kind of a higher-level scheme (often called a mode of operation) to turn it into a more general-purpose encryption scheme (which will, usually, be some kind of a stream cipher, in the broad sense).
Thus, a block cipher is perhaps better regarded as a useful tool for building ciphers (and other cryptographic schemes), rather than as a general-purpose cipher in itself.

So why apply the name "cipher" to them at all, then?  Well, for one thing, that's the name the folks at IBM and NBS (now NIST) chose to use back in the 1970s, and the rest of the world simply followed their lead.  From a historical perspective, it's also a fairly understandable decision: in cryptographical parlance of the day, a "cipher" was something used to encrypt data, and that's certainly what DES did, if in a somewhat unconventional manner.  Thus, it made perfect sense at the time to call it a "cipher", but specifically a "block cipher", to differentiate it from other types of ciphers used at the time.

However, the end result of all this is that, today, we have two different kinds of "ciphers" used in modern cryptography: stream ciphers, which are used to encrypt (streams of) data, and block ciphers, which are (mostly) used to build other kinds of cryptographic algorithms (including stream ciphers).

What about asymmetric encryption schemes like RSA, then?

Well, they're certainly ciphers in the broad sense of "something used to encrypt data", and indeed several authors do use terms like "public-key cipher"or "asymmetric cipher".

On the other hand, if block ciphers are somewhat restricted in their direct applications, public-key algorithms like RSA are even more so.  For one thing, a block cipher can encrypt any string of 64 or 128 bits; RSA can encrypt a number between 0 and the recipient's RSA modulus (minus one).  This may not seem like much of the difference (since it's easy enough to map bitstrings to numbers and back), but do consider the fact that this means that the space directly encryptable messages is different for each RSA key.

Also, "textbook RSA" is only secure if the messages are unpredictable, more or less uniformly distributed between 0 and the modulus, and if the same message is never encrypted with multiple RSA keys.  If the messages belong to a small subset of the full range, an attacker can easily decrypt them by a brute force attack; if they're too small compared to the modulus, or if the same message is encrypted with too many keys, they may be able to break the encryption much more easily than by brute force.

Also, even if those problems are fixed by appropriate padding (effectively adding enough (pseudo)random bits to the messages to make them unique, unpredictable and long enough), RSA (like most asymmetric encryption schemes) is still poorly suited for directly encrypting long messages.  Thus, the standard way of using RSA is a part of a hybrid encryption scheme, where the data is first encrypted using a symmetric encryption scheme (i.e. a stream cipher, broadly speaking) with a random key, and that random key is then encrypted with RSA.

All these issues make some cryptographers (including myself, to some extent) reluctant to call RSA a "cipher", in the same sense as the term is applied to modern stream ciphers and earlier classical substitution / transposition ciphers.  In these people's minds, a "cipher" is something you could use to encrypt a normal plaintext message (and not just a random number in some interval) directly, whereas RSA would be better described as just an "algorithm" (in its "textbook" form, which is not really secure on its own) or a "cryptosystem" (with all the additional trappings needed to turn it into a secure and usable encryption scheme).

(Ps. It's worth noting that there's quite a bit of variation between different public-key encryption schemes, in terms of what they can encrypt directly.  For example, traditional ElGamal encryption is pretty flexible, and can safely encrypt any number less than the (fixed) order of the group, which may be, and usually is, shared by all recipients.  Conversely, for most elliptic curve based systems, even just efficiently and unambiguously encoding an arbitrary message as an encryptable curve point is a non-trivial exercise.)


Can you build a One Way function from a Collision Resistant Function Family?

So in fact, you can build a One-way function from a Collision Resistant Function.

Using a function family of CR functions F, we can create a one way function that works as follows:

pick function F from CRF family, F = ${f_k}$
$g =\ one\ way\ function$
$x_1\ and\ x_2$ picked from random

$g(x_1, x_2) = f_{x_1}(x_2),\ x_1$

The reason this works is because in order to break this one way function you would have to break the fact that $f_{x_1}$ is collision resistant.

Proof:

So let us assume there is an adversary A
that can invert CR function $f_{x_1}(x)\rightarrow y$.

$A(y) \rightarrow x$
What A returns is a pre-image of x so it can be the original x or a collision.
So now lets assume there exists an A' that can use A to break our one way function.
The way he will do so is by first allowing the random inputs of $x_1\ and\ x_2$.
$g(x_1, x_2)= f_{x_1}(x_2),\ x_1 \rightarrow y$

Now A' uses $A(y)\rightarrow x$ The output x is either = $x_1$ or a collision. With this A' has now successfully broken my scheme. But because we know that an adversary A that can find a collision/invert a collision resistant function does not exist in polynomial time we know our scheme is safe and one way because if one can not find a collision in polynomial time then one can not break the one wayness of my function in polynomial time.


Computational trapdoor where the problem is tractable for both parties but easier for one

Russell Impaglizzio wrote "A personal view of average case complexity" roughly 25 years ago. In this work, he describes "five worlds" that we could live in with regards to the $P\stackrel{?}{=} NP$ problem. In two of these worlds one can do cryptography, they are roughly summarized as:

Minicrypt: One-way functions exist
Cryptomania: Trapdoor one-way functions exist

To be clear, each of the five worlds describes a possibility of the resolution of the $P$ vs $NP$ problem (and various related problems). So if "we are in minicrypt but not cryptomania", it means that trapdoor one-way functions don't exist, but one-way functions do exist.

What about other cryptographic primitives? There has been a decent amount of effort to show that (roughly) "Minicrypt = private-key cryptography", and "Cryptomania = public-key cryptography". There's actually some really interesting recent work showing that there's more to the story than just this [1], but that's a separate topic.

So if we aren't in cryptomania, can we do public key encryption? Strictly speaking no (that's the point), but we can still hope for something akin to what you're describing --- while our protocols may not be impossible for a poly-time adversary to break, we can "have a computational gap" between honest parties and dishonest parties (although the gap is some polynomial). One of the initial public key schemes was actually of this form (Merkle's Puzzles). There has been some recent work revisiting this (seemingly motivated by "fine-grained complexity"), see Fine-grained Cryptography and Public-key Cryptography in the Fine-grained Setting.

[1] See Minicrypt primitives with algebraic structure and applications. Essentially all minicrypt primitives have been known to be equivalent for a few decades, but cryptomania primitives are not all known to be equivalent. There appears to be ways in which they aren't equivalent, meaning they break up into separate "continents" within the "world" of minicrypt.


Your idea lacks forward secrecy, which protocols like TLS often (in newer versions anyway) offer. Otherwise it is close to how such things are usually done.

To get forward secrecy you would instead use an ephemeral Diffie-Hellman key exchange, which you would authenticate with the pre-shared public key (which would be a signing key, not an encryption key, where that makes a difference).

There are several alternatives for algorithms, but basically you should... do what good TLS cipher suites do. E.g. ECDH or EDH with either ECDSA or RSA signatures. AES-GCM would be a good default choice for symmetric encryption.


Better understanding what big O is referring to

We write it in terms of the number of bits because it accurately models the reality of how computers work.
Computers don't natively support addition of arbitrarily sized numbers in 1 time step. Instead, they break such operations into addition of constantly-sized numbers (say bits for simplicity), and then use these as a basis for some algorithm to add larger numbers. Essentially, to measure the time complexity of some algorithm, we need to state what operations "cost" 1 time step, and any choice we make should be informed by how computers are built in practice.

You're also slightly misunderstanding the complexity of sorting. Things like quicksort state that you can sort an $n$-element array using $O(n\log n)$ comparisons. But how much does each comparison cost? If all elements in the array are assumed to be constant-sized, this is $O(1)$, so the overall time complexity is $O(n\log n)$.

But what if the size of elements in the array grows with the overall array? If you have an array of $n$ elements, each of which is an $n$-bit number, quicksort still works in $O(n\log n)$ comparisons. How much does each comparison cost though? In terms of bit operations, it should be $O(n)$ time. So one has that the complexity of sorting this array is:
$$
O(n\log n) \text{ comparisons} \times O(n) \frac{\text{time}}{\text{comparison}} = O(n^2\log n)\text{ time}
$$
So sorting this array is actually $O(n^2\log n)$ time.

In your example, you're right that it takes $O(p)$ trials. If $p$ is $2^k$ bits, why should this be "exponential"?
Consider the very basic part of your algorithm, which is setting some counter $i = 0$, and incrementing it all the way up to $p$. How many bit operations does this simple part of the algorithm take? While this sounds like a dumb question, actually designing an algorithm and evaluating its cost (in terms of bit operations) may be useful for your understanding.


Does re-transmission really reduce security?

Your colleague is wrong; assuming that the GCM nonces are generated correctly (that is, never repeats for the same key), there is no risk to GCM in repeating the VCC.

GCM has the property that, as long as you never repeat the nonce for the same key, GCM guarantees both the privacy and integrity of the encrypted plaintext (assuming that AES is a strong block cipher and that the AES key cannot be guessed).  This remains true even if you repeat the same region (such as the VCC) for multiple plaintexts.  Actually, the guarantee is even stronger; you could let the attacker choose the plaintexts for you to encrypt, and he still cannot learn either the AES key, or the plaintext for an encrypted message that he did not choose.


Is including the key as AAD actually dangerous?

One potential issue with GCM is that it can potentially make the problems you get from repeating nonces worse; instead of allowing you to forge, and revealing the plaintext for the packets with the repeated nonces, it can become a key recovery issue.

Here's one way it can happen; suppose the AAD is the 128 bit key, and you repeat the nonce with three different messages of different lengths (a 1 block, a 2 block and a 3 block message).  Then, the three GCM tags are computed as:

$$KH^3 + C_1H^2 + C_2H + Y = T_1$$
$$KH^4 + C_3H^3 + C_4H^2 + C_5H + Y = T_2$$
$$KH^5 + C_6H^4 + C_7H^3 + C_8H^2 + C_9H + Y = T_3$$

where $K$ is the unknown key, $H$ is the unknown $H = E_k(0)$ value, $Y$ is the unknown value $Y = E_k(nonce)$ used to protect the tag (and because all three messages use the same nonce, they have that value in common), and $C_1, ..., C_9$ and the tag values $T_1, T_2, T_3$ are values known to the attacker.

These are three polynomial equations in three unknowns; they can be combined into a single fourth degree polynomial in $H$ (and not $K$ or $Y$); it can be solved for $H$ (giving up to 4 possible solutions), from that, you can recover the secret key $K$ value as one of 4 possibilities.


Encrypt a small amount of data with a password derived from PBKDF2

Is it fine to do that?

Yes, it should be fine, as long as you do not reuse the key/salt-pair for encrypting another piece of data.

  Or is there a more standard construct?

Any authenticated encryption algorithm would work. E.g. AES-GCM with the PBKDF2-derived key.

If you are going to use the same password for encrypting many such pieces of data there are more efficient ways to do it, so that you do not need to compute PBKDF2 anew for each of them. For example, have a constant salt for it and also a message-dependent nonce you use for the encryption algorithm.

There are also alternatives for PBKDF2 that you might prefer, like bcrypt, scrypt, argon2, if you happen to have them available. They make it more difficult to test password guesses, which you might want if you are unsure about the strength of the password.


in Bilinear pairings, what is the difference between Type 2 and Type 3?

Note that you do not have an efficiently computable homomorphism from $G_1$ to $G_2$, but in Type-2 you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$ and in Type-3 you do not have one.

  But what I don't understand is what is the use of the homomorphism in cryptography?

Well, if you have a tuple $(aP',bP',cP')\in G_2^3$ with $P'$ being a generator of $G_2$, you can check if $e(\psi(aP'),bP')=e(\psi(P'),cP')$ holds. Consequently, the decisional Diffie Hellman (DDH) problem is easy in $G_2$, but remains hard in $G_1$. In cryptography, this is typically formalized as the so called external Diffie Hellman (XDH) assumption.

In a Type-3 setting, as you can not map between $G_2$ and $G_1$, the DDH seems to be hard in $G_1$ and in $G_2$. In cryptography, this is typically formalized as the so called symmetric XDH (SXDH) assumption.

So if you have a Type-2 pairing, then you have the XDH setting and if you have a Type-3 pairing, you have the SXDH setting.


Encypted comms between two parties with facilitating middleman

Yes, there is a simpler approach: radio. You could use a symmetric cipher--just take your pick according to your security needs.

Over VHF, for example, you set up a repeater for the signal between Alice and Bob, otherwise known as a relay station. In this case, the traffic is collected and forwarded by Charlie.

A repeater is usually set up to increase the working distance and maintain signal strength between two parties.

But one must be careful about sending encrypted radio messages. Doing so is often illegal, no matter your frequency band/modulation, depending on local/state/federal laws. Get informed before you try this at home.

The symmetric encryption method you choose--out of those available--might not matter that much in this scenario, but you now have other problems:  an integrity check, authentication, and jamming (otherwise known as denial). Furthermore, how will Alice know that her message was forwarded?

In practice, such a system may result in Bob getting two messages: first from Alice, then from Charlie, depending on atmospherics (even for VHF); that is, the occasional strangeness of wave propagation, which can result from many factors--some variable, some not.

By the way, one reason that sending encrypted radio transmissions is commonly illegal (even over a legal frequency band), even though it can be cheap and work very well indeed, is that this is an effective way to communicate while staying off of a collection platform.

For example, a VHF radio signal using a directional antenna on relatively low power from Alice to Charlie and then Charlie to Bob might make sense in certain situations.  One could even use a one-time pad.  Charlie then has no chance to break your traffic--if he ever had that in mind.  There are simple programs that send ciphertext from a GUI on your computer over an attached VHF radio.


Can a message encrypted with one AES-256-GCM implementation always be decrypted with another?

Yes.

HOWEVER....

An implementation may put the content of the encrypted message wherever it wants, and format the encrypted message any way it wants, including different text encodings such as Base64

You will need to take that into account, when decrypting the message, the input must be formatted in the way that an implementation is expecting, and that may be very different than what you have, or that a different implementation may output.

There may also be other things which are not part of the message, such as the expected size of the auth tag or nonce, but all implementations following the spec will deal with variations in size correctly, as long as they are told to do so.

For example, implementation A may output the data in this way [nonce][message][tag], and it may expect 3 inputs for decryption, output data stream, auth data, and key, then extract the nonce and tag from the message automatically, since that implementation only uses 96-bit nonce and tag sizes.

Implementation B may output the message, tag, auth data, and nonce as a Base64 formatted strings inside an XML file, and only take the same XML file and the key as inputs, and will detect the size of the nonce and tags from their specified lengths in the file, decode from B64, and decrypt the message.

As long as you can translate the encoding from one to another, you should be able to make them compatible. The dev documentation of those projects should show what output format they use, and if there are runtime options to modify that format.


Is the scheme $(r, Mac_k(r) \oplus m)$ CPA-secure?

Your first approach was almost correct. Your question says nothing about the shape of the secure MAC except the length. The secure MAC only says that you cannot forge a new tag from the previous ones.

Let $MAC_1$ be a secure map with output length $n-1$ than

$$MAC_2(m) = MAC_1(m)\|0$$
will be a secure MAC with output length $n$.

Now, put $MAC_2$ into your scheme and use 0 to distinguish the messages. The adversary sends two messages $m_1$ and $m_2$ such that $\operatorname{lsb}(m_1) \neq \operatorname{lsb}(m_2)$. When the messages returned he can distinguish just by observing the lsb's of $MAC(r_i)\oplus m_i$


Does the relationship between plaintext and ciphertext moduli affect the security of BGV/BV SwHE?

This is necessary for security. Consider if $q$ was a multiple of $t$, so $q = v\cdot t$. Take your ciphertext $(a, \langle a, s \rangle + t\cdot e + m)$ and multiply through by $v$. You now have
$$(v\cdot a, \langle v\cdot a, s \rangle + v\cdot t\cdot e + v \cdot m) = (v\cdot a, \ \langle v \cdot a, s \rangle + v\cdot m) \mod q$$
Suppose you're playing the CPA game, so there are only two possible values for $m$, which you know, so just try subtracting $v\cdot m$ from the second element and solve the "learning without errors" problem using your favorite algorithm to solve a linear system of equations (Gaussian elimination will work for BV & BGV).

For a more general answer, if $t$ is a zero-divisor in the ring $\mathbb{Z}_q$, the above attack will work, since you can kill the error by multiplying through by a non-zero value. By mandating that $t$ and $q$ be coprime, the only way to kill the error is to multiply by a multiple of $q$, which is 0 in the ring $\mathbb{Z}_q$.


You can compute an $f(g(m))$ in which $g(m)$ is your encryption method and $f$ is a meaningful mapping function. As an example of $f$ I can mention a dictionary codebook mapping.
For example if your output is 11101000 you can see it as 1110 and 1000 then map 1110 to "apple" and 1000 to "grape". Your codebook here must consist of all inputs of 4 bits and the name of fruits as output.
In the receiver side, you must clearly first compute $f^{-1}$ and convert the name of fruits to predefined codes and then decrypt it.


How to calculate the bias of cryptographic hash output from biased input?

Let's call the output of your TNRG $X$—this is a random variable taking the values 0 and 1, with $\Pr[X = 0] = 0.4$ and $\Pr[X = 1] = 0.6$, so that $H_\infty[X] = -\log_2 0.6 \approx 0.737$ bits.  This induces the random variable $Y = \operatorname{SHA-256}(X)$, which has

\begin{align*}
  \Pr[Y = \operatorname{SHA-256}(0)] &= 0.4, \\
  \Pr[Y = \operatorname{SHA-256}(1)] &= 0.6.
\end{align*}

Since $\operatorname{SHA-256}(0) \ne \operatorname{SHA-256}(1)$, we clearly have $H_\infty[Y] = H_\infty[X]$.

What if we have a set of observations $\{X_i\}_i$, which are independent and identically distributed?  Then, e.g.,

\begin{align*}
  \Pr[X_0 = 0, X_1 = 0] &= 0.4^2 &&= 0.16, \\
  \Pr[X_0 = 0, X_1 = 1] &= 0.4 \times 0.6 &&= 0.24, \\
  \Pr[X_0 = 1, X_1 = 0] &= 0.6 \times 0.4 &&= 0.24, \\
  \Pr[X_0 = 1, X_1 = 1] &= 0.6^2 &&= 0.36.
\end{align*}

I leave computing the entropy of the tuple $(X_0, X_1)$ as an exercise for the reader.  What about $\operatorname{SHA-256}(X_0 \mathbin\Vert X_1)$?  Since SHA-256 has no collisions on $00$, $01$, $10$, $11$, once again the entropy is preserved.

In fact, the entropy is not preserved only if there is a collision in the possible inputs.  Obviously the entropy is at most 256 bits for the output of SHA-256 on a single input.  How many distinct outputs are there?  Nobody knows for SHA-256, but for a uniform random function $F\colon \{0,1\}^{256} \to \{0,1\}^{256}$, the expected fraction of distinct outputs is about half the total output space—specifically, $1 - e^{-1}$.  So you might estimate a maximum min-entropy of about 255 bits, in the best case of a perfectly uniform input.

However, you're not limited to feeding in 256 bits; you could feed in 512.  If you feed in $256 + k$ bits to a uniform random function 256-bit function, the expected fraction of distinct outputs is about $1 - e^{-2^k}$ which very rapidly approaches 1 as $k$ grows.  The min-entropy of $(X_0, X_1, \dots, X_{511})$ is obviously $-\log_2 0.6^{512} \approx 377 \gg 256$ bits.  While passing 512 bits through SHA-256 may not necessarily cover the entire 256-bit output space and may not attain the full possible entropy of 256 bits, it's probably a pretty safe bet that the entropy is close enough to 256 bits that the difference doesn't matter to you.  This is plenty to use as a key for a PRNG for cryptographic work.


how to calculate the average key search for AES-128bit?

Since key search is "embarrasingly parallel", i.e., you can have different ASICs searching different parts of the key space, you have $$20{,}000\approx 2\times 10^{11}$$ processors and the keyspace is of size $2^{128}$.
There are $$3600\times 24\times 365.25\approx 2^{24.9}$$ seconds in a year so you can check $$2^{11} \times 2^{24.9} \times 2^{28.9}\approx 2^{64.8}$$ keys per year, the last factor being $2^{28.9}\approx5\times 10^8$. So this gives
$$ 2^{127} \times 2^{-64.8} =2^{62.2}\approx 10^{18.72} \approx 5.25 \times 10^{18}$$years if I haven't made a mistake somewhere.

Also I interpreted your

  can search 5.108 keys per second

as $5\times 10^8.$

Edit: Fixed computation. Thanks, @dave_thompson_085


Notion of Security in case of Covert Adversaries

What do we mean exactly by quantifying covert adversaries?

This means in the security definition (e.g., Definition 2.4.1 in that book), we say something like this "...for every non-uniform probabilistic polynomial-time (PPT) covert adversary, there exists...".

  While quantifying the covert adversaries, how did we make it so that the probability of catching the "non-covert" adversaries is equal to statistical distance from the honest party's distribution?

No, we didn't. The probability $10^{-6}$ is not a statistical distance, but just a non-negligible risk that a "non-covert" adversary has to take.

  Moreover, on page 32, why did we decide to quantify over all adversaries (including malicious), and how did that fix the problem we were dealing with?

If we quantify only covert adversaries, then the resulting security definition tells nothing about "non-covert" ones. That is, for a protocol that is secure in this sense, we are only guaranteed that no covert adversary can reveal additional information about the honest parties' inputs (except that implied by the function's output) by executing the protocol, but a "non-covert" adversary could still break this security. By quantifying all adversaries, the final definition (about secure computation in the presence of covert adversaries with $\epsilon$-deterrent) guarantees that every non-uniform PPT adversary $A$ can be caught with probability at least $\epsilon$ if $A$ chooses to cheat.


Safe Elliptic curves of prime order according to "safecurves"

Are there any 'safe' and well-established elliptic curves of prime order?

Depends on what you mean by 'safe'.  If you use Dan Bernstein's definition of "safe curve", no; the curves they list as safe are Edwards curve, which always have a point of order 2 (and hence can't be of prime order).

As for proposed curves that are of prime order, there's the NIST curves that you know about, there's the Brainpool curves, and there are the Weierstrass flavor of the NUMS curves.  Whether they are 'well-established' is questionable; they each certainly have their proponents.

Also, it's not clear that you really need a prime order curve. The multiplicative group $Z^*_p$ you're using isn't of prime order either, you manage to work in a prime order subgroup.  The elliptic curves we use for cryptography have large prime order subgroups (to make the discrete log program hard), perhaps you can use the same trick to use, say, Curve25519.


How does one implement the Inverse of AES' MixColumns

It's pretty much the same as the forward Mix Column direction; it's a series of multiplications in $GF(2^8)$, however, instead of multiplying by 1, 2 and 3, you're multiplying by 9, 11, 13 and 14.

The multiplication rule isn't that complex; however, it is a bit fancier than the quick rule we got for $\times 2$ and $\times 3$.  If you're happy with doing a table lookup, this wikipedia page gives tables of values for $x\times 9$, $x\times 11$, $x \times 13$ and $x \times 14$.

Another way to approach it is to take the rule you already know for $x \times 2$, and use it several times, as in:

$x \times 9 = (((x \times 2) \times 2) \times 2) + x$

$x \times 11 = ((((x \times 2) \times 2) + x) \times 2) + x$

$x \times 13 = ((((x \times 2) + x) \times 2) \times 2) + x$

$x \times 14 = ((((x \times 2) + x) \times 2) + x) \times 2$

(where $+$ is addition in $GF(2^8)$; you know it better as "exclusive-or")

Further explination would require me to get into the technicalities of what multiplication in a finite field actually is; I'm not sure you're quite ready for that; if you think you might be, you might want to start in on this article.


Hiding identifying data while allowing matching?

Any transformation of the identifier, including those in the question, is bound to have at least one drawback: after a transformation of cryptographic quality, it will be next to impossible to re-agregate identifiers that refer to the same person but have been slightly garbled (perhaps because there are two common spelling of the mother's name).

Even ignoring that, I do not see a convenient and bulletproof solution, basically because you start from a very short identifier.

One improvement would be to encrypt the identifier using a secret key, with format-preserving encryption, so that the encrypted result remains short, compatible with existing practice, and the encryption demonstrably can't introduce more collisions than there is originally. A most serious problem then is protecting the secret key, and limiting its use (which is necessary since it is enough to encipher a few chosen inputs to break the system).

Better than nothing is making this key passphrase-protected (like a PGP key is), with the passphrase entered on the laptop by the legitimate user at the beginning of data-collection activities. Standard key stretching techniques can make that quite safe against passphrase search, while still robustly detecting an accidental mis-keying. While we are at it, all data collected should be kept encrypted with standard techniques (using a different key, possibly protected by the same passphrase for convenience).

Even better is moving the key in a Smart Card, protected by user PIN with consecutive errors counter. Next step (recommendable, and quite easy even with standard Smart Cards) if moving at least a building block of the format-preserving encryption into the Smart Card itself, so that the key never leaves the Smart Card (said building block could be AES or a MAC, and the corresponding key, used in the round function of a Feistel cipher). Ultimately, the sensitive data could be held in the Smart Card itself and inaccessible without the PIN.

Beware however that nothing in the above can resit an active compromise of the laptop (e.g. key logger) performed before sensitive data is entered.


Is PyCryptodome's export_key with passphrase secure?

Well, it's sort of secure. There are no serious issues, but there are a few problems:

3DES - A cipher composed of three rounds of the DES cipher. DES has a key size much too low at only 56 bits, but running it three times (first in the encryption direction, then the decryption direction, then the encryption again, hence the acronym "EDE") brings the key size up to 168 bits, although the effective keyspace is only 112 bits due to a meet-in-the-middle attack that applies to this type of construction. Although it's deprecated, 3DES is not considered breakable like DES. It's just that there are faster and more secure alternatives.
The other issue with 3DES is the fact that it has a small block size of 64 bits. This causes severe security issues to open up as more data is encrypted under a single key. Because a private key is small (the size is measured in mere kilobytes), the small block size is a non-issue.

Small salt - The salt size is too small at only 8 bytes (64 bits). This is unlikely to be a serious issue in practice. An attacker would need to build an incredibly large rainbow table to attack a 64-bit salt. Building a rainbow table for hashes with a random salt was possible back in the days when a 12-bit salt was used, but not today with a 64-bit salt.  I'd recommend 128 bits though.

Low PBKDF2 iterations - PBKDF2 is a function that hashes a password slowly, forcing anyone trying to crack the hash to use the same slow function. 1000 iterations of PBKDF2 is not much. It's far better than using a hash of the password directly, but it's not ideal. It would be better to use at least 100,000 iterations, or even to switch to a superior memory-hard KDF like Argon2.

Overall I'd say it's likely secure enough, but it's not ideal and isn't something I would use if I could help it.


IV (initial value or initialization vector) is a vague term that describes some kind of starting value for a mode of operation that is known to both parties, and generally sent in the clear with the encrypted data (and known to the attacker)

IVs in many modes of operation have specific requirements to that mode. In some modes the requirement is that is unpredictable and (with high probability) not reused. For those modes the easiest method for IV generation is a CSPRNG, with this method IV reuse can occur due to the nature of random numbers. For CTR and derivatives, the IV must be a nonce, which is a very specific type of value, and is commonly referred to us such for these modes, as to prevent confusion regarding the requirements. NIST uses both names in the GCM spec document, but is clear on the requirements.

A different way of generating IVs that are unpredictable and also unique is to encrypt a counter value with a different key. These are the length of the block size.

A nonce (number used only once) must NEVER be reused with the same key (hence the name), since it is the plaintext input to the block cipher. Modes that use a nonce rather than a random number include OFB, CTR, and CFB. CTR has no requirement for nonce unpredictability. The nonce for CTR is generally a sequential message counter starting at 1. This also allows easy verification in some applications that a message is not received multiple times (replay attacks). The block counter is for the blocks within each message. If the nonce were chosen randomly, the probability of overlap increases with each encrypted block; this is not a problem if a record of each nonce was kept and verified to ensure it was not reused.

CTR mode generally uses a 96-bit nonce, leaving 32 remaining bits for the block counter. This gives 64GiB of output blocks per nonce before the nonce must be incremented, which is enough for the majority of uses. The secure limit on output for CTR is the secure limit for block cipher output with a given key, which for AES is a maximum of $2^{128/2}$ blocks.

The other requirement for nonces specific to GCM is that it is not all 0 bits, as that is used for GHASH, and using it can possibly allow forgeries of all authentication tags. This value is essentially the IV to the GHASH function, which is unique to each key/block cipher combination.

When used with GHASH in GCM, CTR mode has a more limited secure output, and this depends both on the size of the nonce as well as the size of the authentication tag. The smaller the tag, the fewer messages can be transmitted before attacks become successful. Additionally, using different tag lengths with the same key can lead to a loss of security. See Authentication weaknesses in GCM for details on attacks on short nonces. For GCM The maximum plaintext length is $2^{39} - 256$ bits for a given nonce.

I do not see any problem with using the same key in GCM and CTR, as long as there is no nonce overlap, and you stay within the safe block limit for AES, as well as the safe limit for the GCM authentication tag generation with a single key, and never encrypt an all 0 input. The GCM special publication (800-38D) from NIST regarding key and nonce generation however does specify that the key shall only be used with GCM and no other mode, I would be inclined to follow this advice.


3DES over Galois Counter Mode (GCM) for authenticated encryption

According to Wikipedia,

  GCM is defined for block ciphers with a block size of 128 bits.

So no, you can't use GCM with 3DES or DES, because of the 64-bit block size. You could use something similar to GCM, but it wouldn't be GCM.


Is there a standard way to implement AES 128?

There are several implementation strategies to AES (SIMD-based, plain-C, table-based, side-channel resistant, bit-sliced, AES-NI, ...). The "standard" way depends on your platform and goals, depending on the answer to questions such as "do yo have hardware support?", "do you want constant-timeness", "do you want maximal speed", "how much RAM / code space do you have?", "is your mode parallelized?", ...

  Is it uncommon to implement your own version of AES?

Yes, it is, because there are already so many good open-source implementations, however people still do it every now and then. For example re-implement AES "just for fun" and sometimes they have a different set of optimization goals than all previous implementations like "minimize code-size, work everywhere in C, runs in constant-time".

  I'm familiar with the AES algorithm and it seems like it would be
  possible to implement your own way of scrambling the bits in the
  individual rounds.

No. If your implementation doesn't result in the same encryption and decryption functionality as described in FIPS 197, you do not get to call it "AES", because it's some custom scheme you made up.

  I also noticed the NIST gives out certifications to individual
  companies for their AES encryption (ie. Google, Cisco, HP, AWS, etc.)
  Is this because it's a custom implementation?

The only actual evaluation and certification program that I'm aware of that is run by NIST is the cryptographic module validation program, which well, validates cryptographic modules according to FIPS 140-2. These validations are usually carried out by certified validators (certified by NIST). The modules may use AES but they usually do much more and the main aspect usually is on key management, role management and user authentication, but also of course on the correct implementation of the algorithms, so yes, you can get your AES implementation validated by this program, if it is part of a cryptographic module.


Do aes_256_gcm IVs just need to be unique for that key?

For GCM, IV can be predictable (contrary to some other modes such as CBC, there is no unpredictability or uniformness requirement), but they must not be reused. You are free to use any method you wish to ensure this uniqueness. If an IV is reused, then the "authentication key" is revealed, and the encryption itself becomes an instance of the "two-times pad", i.e. may leak a lot of information on the plaintext, depending on its format.

A timestamp is sort-of fine. The problem with timestamps is that they depend on a local clock, and since there is no such thing as a perfect clock, computers routinely include ways to adjust clocks, either manually or automatically. Note that automatic clock adjustment over the Internet uses NTP, which is usually unprotected (no authentication or encryption). Therefore, remote attackers may feed a connected system with fake NTP packets to force a clock adjustment and possibly an IV reuse.

Using a random value is a common way to achieve uniqueness with a high probability; with 96-bit IV, if you encrypt no more than $2^{32}$ messages with a given key, then probability of an IV collision (assuming a strong random source) will be at most $2^{-32}$, which is low enough to deter attackers (i.e. it's less worthwhile to wait for such an event than to simply buy lottery tickets).

Some extra notes:

GCM actually supports all IV lengths, not just "12 bytes". An IV with length exactly 12 bytes is used "as is" and lets you know exactly if you have a collision or not. If you use a 64-bit timestamp (assumed non-repeating), you are encouraged to "pad it" with 4 extra bytes (e.g. zeros) so that the GCM implementation receives a 12-byte IV (even if you do not actually transmit the padding bytes in the message on the wire).
Conversely, you could use a longer random IV. 16-byte random IV are arguably "better" than 12-byte random IV (it makes risks of collisions lower as long as individual messages are substantially shorter than 64 gigabytes, and collisions are less immediately detectable by attackers). But since you try to reduce on-wire size, I suppose you'd prefer not to do that.
In some contexts, you can get a non-repeating IV "for free". E.g., in a TLS connection, each connection has its own key, so that IV collisions matter only within a given connection. But then, messages ("records" in TLS terminology) are successive; thus, a simple sequence number can be used (first record gets number 0, second record gets number 1, and so on). The sequence number is implicit and thus needs not be transmitted at all.
There may be other solutions. For instance, a possible method would be to replace GCM with the following mode:

Let x be the IV (see below for its length) and m the plaintext to encrypt.
Compute HMAC/SHA-256 over the concatenation of the IV and the plaintext, and truncate it to the AES block size (16 bytes). This yields the authentication tag t.
Use AES-CTR encryption over m with t as IV; this yields the ciphertext m'.
Transmit x, t and m'.

With such a mechanism, you could use a very short IV x, even an empty one (of length 0). Note that this saves space, compared to GCM: with GCM, the encrypted message is sent along with an authentication tag (16 bytes) and an IV; here, I suggest use the HMAC-derived authentication tag as IV for encryption.

If you use that kind of mechanism with an empty IV x, then the whole thing becomes deterministic: if you encrypt twice the exact same message with the same key, then you get the exact same encrypted message. However, this should be the full extent of the leak. A small but non-empty IV x can help in hiding that.

Note that this is an encrypt-and-MAC setup, usually frowned upon for theoretical reasons. It is reasonably safe in this case, because HMAC/SHA-256 also protects confidentiality of the input (this is not necessarily the case of any other MAC mechanism), and CTR decryption implies no padding, and thus can be safely implemented even over unvalidated input data.

Summary: if your timestamp are really unique, then they are enough for GCM, and you can pad them to 12 bytes with zeros (that need not be transmitted along with the message). However, if clocks can be adjusted or rewinded, then you should probably use random IV instead, to get "probabilistic uniqueness"; and, in that case, don't go lower than 12 bytes. If you are desperate for size, then there are other possible avenues, but they are outside of existing published standards, which means that you need more external review and development care.


Key Check Value standard practice for asymmetric cryptography?

PKCS10 looks like relevant industry practice for private keys.

See "Note 2" at page 4,
Certification Request Syntax Specification - RFC 2986:
The signature on the certification request prevents an entity from requesting a certificate with another party's public key.

That is, soneone requesting a certificate on a public key demonstrates his knowledge of corresponding private key by producing a signature verifiable with the public key from PKCS10 request.

Another technique could be found at Join protocol,
Direct Anonymous Attestation
for Trusted Platform Module chip.
It could be considered a proof that TPM "has access" to "keys" $f_0$ and $f_1$.


Is it possible to perform a rudimentary asymmetric key encryption algorithm by hand?

Yes, you can perform rudimentary asymmetric encryption or signing by hand, but no it won't be secure.

Textbook RSA with small enough numbers is easy to do by hand. Diffie-Hellman to exchange a symmetric key is even easier. However, the kinds of numbers for which this is feasible are far from those needed for real security.

There are a lot of other asymmetric systems, but those tend to use even more complicated (to humans) math. Generally asymmetric encryption on a computer is something like an order of magnitude slower than symmetric and like the question you linked shows even secure symmetric encryption is barely doable, maybe, by hand.


19 out of 24 words of BIP39 passphrase (brute-force last 5?)

When you say that you have lost the last 5 words, are they completely gone or just difficult to read or invalid?

If you use a 48 vCPU Linode VPN, you can use BTCRecover can be used to recover 3 completely missing words in 6 hours, 4 missing words in about a 1.5 years. 24th word is actually just a checksum, so it isn't really missing...

I have a YouTube video on how to use BTCRecover and will be releasing one in the future that looks at the limits for 3-4 missing words, etc.

BTCRecover doesn't currently support using a GPU, but if that were implemented, that could easily speed things up by a factor of 10 and bring a 4 word recovery into a manageable time frame.

Either way moore's law in on your side, so you may just have an enforced 10 year HODL. Don't throw out the 24 word seed and keep the public addresses and their derivation paths that you know about. (keeping an xpub for a known account is even better)


Why shouldn't I use ECB encryption?

The main reason not to use ECB mode encryption is that it's not semantically secure — that is, merely observing ECB-encrypted ciphertext can leak information about the plaintext (even beyond its length, which all encryption schemes accepting arbitrarily long plaintexts will leak to some extent).

Specifically, the problem with ECB mode is that encrypting the same block (of 8 or 16 bytes, or however large the block size of the underlying cipher is) of plaintext using ECB mode always yields the same block of ciphertext.  This can allow an attacker to:

detect whether two ECB-encrypted messages are identical;
detect whether two ECB-encrypted messages share a common prefix;
detect whether two ECB-encrypted messages share other common substrings, as long as those substrings are aligned at block boundaries; or
detect whether (and where) a single ECB-encrypted message contains repetitive data (such as long runs of spaces or null bytes, repeated header fields or coincidentally repeated phrases in text).

There's a nice graphical demonstration of this weakness on Wikipedia, where the same (raw, uncompressed) image is encrypted using both ECB mode and a semantically secure cipher mode (such as CBC, CTR, CFB or OFB):

While this scenario is somewhat artificial (one would not usually encrypt raw images like this), it nicely demonstrates the problem with ECB mode: repetitive areas in the input image result in repetitive patterns in the encrypted output, so that many large-scale features of the image remain recognizable despite the encryption.  In the real world, a cryptanalyst attacking an ECB-based encryption scheme would be more likely to look for such patterns in a hex dump of the ciphertext, but the principle is the same.

An actual case of this weakness of ECB encryption contributing to a real-world data compromise is given by the 2013 Adobe password database leak, as described in this answer.  Here, one element contributing to the severity of the leak was that, instead of hashing them properly, Adobe had encrypted the passwords using ECB mode.  This allowed the attackers to quickly locate passwords shared by multiple accounts, or sharing a common prefix with other passwords (like password1 and password2), and also revealed the approximate length of each password.

The ECB encryption mode also has other weaknesses, such as the fact that it's highly malleable: as each block of plaintext is separately encrypted, an attacker can easily generate new valid ciphertexts by piecing together blocks from previously observed ciphertexts.

However, the malleability is only an issue if ECB encryption is used without a message authentication code, and, in this situation, is shared (to some extent) by all other non-authenticated encryption modes, like the aforementioned CBC, CTR, CFB and OFB.  Thus, it cannot really be considered a specific weakness of ECB mode, even though it does tend to be an additional issue whenever ECB mode is used.

What should I use instead?

You should use any authenticated encryption mode, such as GCM, EAX or OCB.

Personally, for short messages, I'm rather fond of SIV mode (RFC 5279), which provides an extra layer of misuse-resistance.  (Many other encryption modes will break rather badly if the same IV / nonce is accidentally used to encrypt multiple messages.  SIV mode retains all its security properties in this situation, except for leaking whether the encrypted messages are identical.)

You can also use any traditional semantically secure encryption mode (such as CBC or CTR), combined with a message authentication code (such as HMAC) using the Encrypt-then-MAC construction.  (That is, you should first encrypt the message, then compute a MAC of the ciphertext, and append it to the ciphertext.)  As long as you make sure to verify the MAC before attempting to decrypt the message, this construction will protect you from the various vulnerabilities of these modes to active (chosen-ciphertext) attacks.

For disk encryption or similar applications that require the ability modify parts of the ciphertext without re-encrypting all the data, you should use a cipher mode designed for that purpose, such as XTS.  Note that such modes generally lack resistance to active attacks, and may have other weaknesses that should be understood before using them.  If possible, they should be combined with some form of integrity protection, such as a MAC on a hash tree.


Why is the Keyspace of a Substitution Cipher not 2^26 but 2^88

The key space of a cryptographic algorithm whose key length is $n$ is given by $2^n$

No. There is confusion between:

keyspace (or key space) $\mathcal K$, which is the set of possible keys.
keyspace size (or size of the keyspace) $\|\mathcal K\|$, which is the number of possible keys (an integer).
key length (or key size) in bit, which can be defined as the base-2 logarithm of the keyspace size (not necessarily an integer). If we note $k$ for the key length in bit, the keyspace $\mathcal K$ has $\|\mathcal K\|=2^k$ keys, and $k=\log_2(\|\mathcal K\|)$.
number of symbols used for a representation of a key. If the key is represented as $n$ symbols which each can take $s$ values, then $\|\mathcal K\|\le s^n$ and $k\le n\log_2(s)$. These inequalities turn to equalities when all combinations of symbols yield valid keys (which is typical in modern symmetric ciphers).

This is a slight simplification: often, and always when effective is added before key, equivalent keys (that is keys yielding the same effect on decryption) are aggregated and counted as one. However this distinction is not useful for a mono-alphabetic substitution cipher.

In a mono-alphabetic substitution cipher for an alphabet of 26 letters, with the key represented as a list of ciphertext letters for each plaintext letter in alphabetical order:

The keyspace is the set $\mathcal K$ of all permutations of the alphabet.
The keyspace size is the number of elements in that set, that is the integer $\|\mathcal K\|=26!=403291461126605635584000000$.That's because plaintext letter A can correspond to any of 26 ciphertext letters, plaintext letter B can correspond to any of the 25 ciphertext letters other than the one corresponding to plaintext letter A, plaintext letter C can correspond to any of the 24 ciphertext letters other than the two corresponding to plaintext letters A or B, and so on until plaintext letter Y corresponding to 2 possible ciphertext letters, and Z corresponding to the one remaining ciphertext letter.
The key length in bit is the base-2 logarithm of that: $k=\log_2(26!)=\log(26!)/\log(2)\approx88.38$ bit.
The number of symbols in the key is $n=26$, with $s=26$ possible symbols.

  Assuming the key length is 26, why is (keyspace size) not $2^{26}$ ?

That $2^{26}$ seems to be built as $2^n$, where $n$ is the number of symbols (not key length), when $2$ would be for the number of possible values taken by a single bit. The discrepancy makes $2^{26}$ irrelevant.

A relevant number is $s^n=26^{26}=6156119580207157310796674288400203776=2^{\approx122.21}$ : that's the number of character strings of $n=26$ characters each chosen among $s=26$ characters. But this is much larger than the keyspace, because the key of a mono-alphabetic substitution cipher must use different letters (otherwise decryption would be ambiguous).


Is there practical Attack on A5/1 Cryptosystem?

Elad Barkan has(Possibly had) a company called KeySee Software.
In Elads's words: "KeySee supplies software for off-the-air interception of GSM communications, as well as consulting services for computer security and encryption."

Knowing Elad, and the literature, I have every reason to believe they deliver what they promise.

As others mentioned in comments, Rainbow tables are available for download, the computational requirements don't seem all that difficult to do it yourself in 2019. Obviously there is a difference between having the Rainbow tables and a functioning attack.


Adjust the problem if at all possible.

The parameters envisioned in the question's

  For example: $n=33, d=7, e=3$

are terminally insecure, because $n$ is way too small: only 6-bit, when 512-bit is routinely broken my amateurs, 768-bit was experimentally broken in a public attack 8 years ago, 1024-bit is considered breakable by well-funded and capable adversaries, and 2048-bit the recommended baseline. See this. As an aside, publishing $d$ makes $n$ insecure.

As noted by Yehuda Lindell in comment, MD5 is very seriously broken, and using it is mostly unjustifiable.

For example, we know how to prepare different PDF files with the same MD5 but showing about any text desired (including chosen after the hash is frozen). With most common RSA signing schemes, this means a signature for a PDF chosen by the adversary (at least in its beginning) and telling something is also a signature for a PDF telling anything else, that the adversary can adjust as wanted (without practical limit for something decided before signature, subject to size limitation of the PDF for something decided after: the best current attacks require an additional 512 octets in the PDF per octet in the text displayed that must be chosen after signature, or a few times less with compression).

Use SHA-256 instead, if that's allowed.

When $n$ is at least 1-bit wider than the hash, we can hash then textbook-RSA-sign. That's considering the hash as an integer (per e.g. big-endian convention), computing the signature as $S=\big(H(M)\big)^d\bmod n$ , with verification by $S^e\bmod N\;\stackrel{?}{=}\;H(M)$. But even with large $n$ and an otherwise secure hash, this is vulnerable to the Desmedt-Odlyzko attack, if some messages legitimately signed can be chosen by the adversary. See this for the method and references.

The correct way is to use a much wider $n$; not publish either its factorization or $d$; use a better hash; and use proper RSA signature padding. A modern such scheme with a security argument, available from a library in most modern programming languages, is RSASSA-PSS of PKCS#1v2.

As noted here with references, coupled with MD5, RSASSA-PSS has been practically attacked in some contexts. But it can be modified to become quite secure in practice until a better break of MD5, or we consider somewhat brute-forcing MD5 for preimage (hard but not inconceivable). In RSASSA-PSS with MD5 we can replace $\operatorname{MD5}\big(\mathrm{padding_1}\|\operatorname{MD5}(M)\|\mathrm{salt}\big)$ with $\operatorname{MD5}(\mathrm{padding_1'}\|\mathrm{salt}\|M)$ or $\operatorname{MD5}\big(\mathrm{padding_1}\|\operatorname{MD5}(\mathrm{padding_1'}\|\mathrm{salt}\|M)\|\mathrm{salt}\big)$ (say, with $\mathrm{padding_1'}$ of 384-bit so that $M$ starts on a block boundary); the random unpredictable $\mathrm{salt}$ before the message $M$ mitigates the worst known weaknesses of MD5.

Addition: RSASSA-PKCS1-v1_5 suggested by this answer is slightly simpler, also easily available in libraries, and is secure as far as we know when used with a secure hash; but needs more transformation to be practically secure with MD5, and does not come with a security argument.


Break HMAC-SHA256 of PAN with known hash?

Only for a trivial key.
You have HMAC(<key>, <secret₁>) = <hash>. The attacker knows <hash> and certain <secret>. Having a small search space, different <secret> values might be bruteforced.
However, with a proper (long, random) <key> the attacker won't be able to recover the other values. The HMAC-SHA256 itself is not reversible, and a long random <key> won't let them bruteforce them during their lifetime.
The real risk would be that during the data breach, in addition to the hashed values, the attacker also stole the <key>.


Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated).

In the simplest case, you could generate 3 words, and just AND them together into a single one.  In C, this would be:

     r1 = rand();
     r2 = rand();
     r3 = rand();
     return r1 & r2 & r3;

This gives each bit set with probability 0.125, which is close to 0.1

If that's not quite close enough, you can get a closer approximation by using more bits; for example, r1 & r2 & r3 & ~(r4 & r5) results with bits set with probability $3/32 = 0.09375$

With this technique, you use $n$ random words to generate bits set with probability $k 2^{-n}$ for some integer $k$; this can be made arbitrarily close to 0.1.

This obviously uses minimal memory; the computation time isn't too bad (assuming your rand implementation is cheap), unless you insist on a quite good approximation to your target probability.

And, while I said 'words', your implementation would use whatever size it finds most convenient; for an 8 bit CPU, each word might be 8 bits (and you just do it 4 times to generate the required 32 bits).


"Short" and "long" are relative terms.  If I secretly make 128 coin flips and write down the results, that sounds like a lot of coin flips, doesn't it? There's $2^{128} > 10^{38}$ combinations I could get, a number bigger than 1 with 38 zeroes after it, so you have no hope of guessing what results I got.

Yet that unguessable result fits in $128 ÷ 8 = 16$ bytes, which almost everybody would call short byte string.  That is, it's short if you're trying to store it in a computer, but impossibly long if it was picked at random and you're a bad guy trying to guess it.

Modern symmetric cryptographic algorithms come in 128-bit and 256-bit strength, whose keys fit in 16 and 32 bytes respectively, and there's no need for their keys to be any longer.  Many public key algorithms do use longer keys (for technical reasons) but even there we're talking about kilobytes at most for popular ones.


A length extension attack doesn't let you find a collision. It lets you predict the hash for an input with an unknown component in the prefix. If you have $h = H(x)$ for unknown (or partially unknown) $x$, you can generate $h_y = H(x \vert\vert y)$ for arbitrary $y$ (this is not strictly correct; I've ignored padding, but for the purposes of this discussion it's a minor detail). However, you still can't find $z$ such that $h = H(x \vert\vert z) = H(x)$ faster than brute force.