Attacks on the RawCBC-MAC if the final step of encrypting with a second key isn't done

Is this also a valid attack on RawCBC [...]?

Yes. Writing down the expressions, we get $t=F(k,m)$ and $t'=F(k,w\oplus t)$ - while abusing notation and meaning RawCBCMAC for multi-block invocations of $F$. Now the actual tag for $(m\|w)$ would be $t''=F(k,F(k,m)\oplus w)=F(k,t\oplus w)$ which is equal to $t'$.


HKDF - Generating a new, random salt per user?

By HKDF, I guess you mean HKDF-Expand, which takes as input a pseudorandom key, a label, and the output length. A public label is OK, but it is better unique rather than random due to HKDF-Expand's pseudorandom function security. I think using UUID only as the label is good enough.


Decrypt Base64 Encoded Monoalphabetic Cipher

You will probably not get any (even partially) readable text out until you've figured out the decryption of the most common characters in at least two adjacent base64 positions (1 and 2, 2 and 3, or 3 and 4).

That's because the eight bits of each plaintext byte get spread across two adjacent six-bit base64 characters during the encoding process.  Thus, even if you manage to correctly decrypt one of these two characters, you've still only recovered at most six of the eight bits.  That leaves at least two bits whose value you'll just have to guess.

That said, the difficulty of guessing those two missing bits depends a lot on which bits happen to be missing.  In particular, the ASCII codes for all letters (A-Z, a-z) have their highest two bits out of eight set to 01.  (The third-highest bit is 0 if the letter is uppercase, and 1 if it's lowercase.)  So, if your plaintext is actually ASCII text, you may be able to get some partially readable output just by trying to decrypt the last base64 character in each group of four, and just assuming that the previous character decodes into something that ends in the bits 01.

(However, do note that the most common plaintext byte, if your plaintext is indeed ASCII text, is most likely not a letter at all, but the space character, whose ASCII code 32 = 00100000 in binary begins with 00, not 01.  The same is true of numbers, line feeds and most but not all punctuation.)

More generally, you will likely want to exploit the structure of the ASCII code, which makes the highest two or three bits of each plaintext byte quite predictable.  In particular, if you take any group of three eight-bit plaintext bytes (representing three ASCII characters) and split them into four groups of six bits (as base64 encoding does), you'll end up with something like this:

ABC??? ??DEF? ????GH I?????

where the bits ABC, DEF and GHI (corresponding to the highest three bits of each plaintext byte) can be:

000 only if the byte represents a control character (of which the only ones likely to appear in plain ASCII text are the line feed = 00001010, the carriage return = 00001101, which is usually always followed by a line feed, and possibly the tabulator = 00001001);
001 for spaces (00100000), numbers (for which the next bit is always 1) and most punctuation characters;
010 for uppercase letters (and the characters @, [, \, ], ^ and _); or
011 for lowercase letters (and the characters `, {, |, } and ~).

Note that, in plain ASCII text, the highest bits of each eight-bit byte (i.e. bits A, D and G above) are always 0.  (That said, they could be 1 if your plaintext was actually written in some "extended ASCII" encoding like ISO Latin 1, or perhaps Unicode in the UTF-8 encoding, and contained some non-ASCII characters.)

For example, let's say that you guess that the most common byte in your plaintext is probably an ASCII space (binary 00100000), and therefore that the most common base64 character (let's arbitrarily say it's X) at the end of each 4-character group probably encodes the bits 100000.

This means that this base64 character X should basically never appear as the first character of a 4-character group (since that would make bit A above 1), and should only rarely appear as the second character (since that would make bits DEF be 000, which should be pretty rare unless the plaintext is full of line breaks).  If that's indeed the case, you can be pretty confident that you've guessed correctly.

Also, you can then look at the base64 characters that precede X in the ciphertext, and be pretty sure that they all represent six-bit base64 codes that end in 00 (since bit G must be 0 in ASCII text anyway, and if bit H was 1, that would decode to the rather uncommon plaintext byte 01100000 = `), which (together with their frequencies in the four different positions) should help narrow down their possible values.

Similarly, you can guess that the most common base64 character in the first position of a four-character group probably encodes the bits 001000, and that the two most common characters following it in the second position probably encode 000100 and 000101 (assuming that a space is most often followed by a lowercase letter; of course, the bit sequences 000110 and 000111 are also likely to be fairly common, since they arise from a space followed by an uppercase letter).

And the most common base64 character in the third position most likely represents the bits 000001 (i.e. a space followed by a letter), especially if it does not usually precede the most common fourth-group character (i.e. X above), as that would again yield a rather unlikely plaintext sequence involving the backtick character ` = 01100000.*

Also, assuming that your plaintext is indeed English ASCII text, another approach you can use to get started is to look for common repetitive sequences of base64 characters in the ciphertext, and assume that they likely correspond to common sequences of characters in English text.

For example, probably the most common five-byte sequence in English ASCII text is  the  (i.e. "the" surrounded by spaces on both sides).  When broken up into three-byte groups for base64 encoding, depending on where the group boundary happens to fall, you can end up with either:

 th and e ?;
? t and he ; or
?? , the and  ??,

where ? stands for some variable byte (most likely a letter).  Thus, the 4-character base64 groups encoding  th, the and he  should all be pretty common, and appear with roughly the same frequency (although note that the frequencies can be skewed not only by random chance, but also by the presence of other common English words sharing the same beginning or end, such as "that", "this", "those", "these", "they", "there" and "then", as well as "he" and "she", and of course the capitalized form "The").

Furthermore, you can distinguish the base64 groups encoding these different 3-byte sequences by looking at the surrounding encrypted base64 characters.  For example, the group that encodes the should very frequently be preceded by the base64 character that encodes the lowest six bits of an ASCII space (i.e. 100000) and followed by the base64 character that encodes the highest six bits of an ASCII space (i.e. 001000).  Furthermore, since they encode spaces, which are common in general, these two base64 characters should usually each be the most common ones in that position of a 4-character group.

(Of course, the group the won't always be preceded or followed by a space, since it can also appear as part of a longer word, or possibly at the beginning or the end of a line.  But the most common plaintext bytes before and after it should still be spaces.)

Similarly, the four-character group encoding  th should begin with the base64 character that encodes the first six bits of an ASCII space (and is thus rather common in the first position of a group), and should be commonly followed by a specific sequence of three base64 characters that encodes e  followed by a letter.  And, correspondingly, the group that encodes he  should end in the common character that encodes the last six bits of a space, and should typically be preceded by the two base64 characters that correspond to  t at the end of the previous group.

Some other fairly common byte sequences in English text that you may want to look for include  a  and  I  (i.e. "a" and "I" surrounded by spaces), both of which can be quite easy to recognize if you've already determined which base64 characters corresponding to spaces at the beginning and the end of a group, as well as  and  (another fairly common three-letter word surrounded by spaces, occurring in a similar pattern as  the  above, but typically sufficiently less common to be fairly easily distinguishable) and the four-byte sequences  to ,  of ,  in ,  at , etc.  You'll probably want to mostly ignore the latter until you've managed to decode at least some common letters, though, since there are rather many common two-letter words in English, and their relative frequency can vary a lot based on the topic and style of writing.

*) That said, everything always depends on what the plaintext actually it.  For example, the Markdown source code of this very answer is full of backticks, most often following or followed by a space, since that's the Markdown syntax for inline code.


How is Twofish flattening the result of Reed-Solomon MDS matrix multiplication into a 32-bit result?

In crypto diffusion layer design the MDS matrix is usually used in the following form:

$$ X_{n+1}=M X_n,$$

where the actual codewords are $(X_n | X_{n+1}).$ So it's a rate $1/2$ MDS code. It need not be Reed Solomon, and optimisations with respect to speed and other considerations are made. This is done in Twofish as well.

In particular $X_n$ is made up of the 4 words that are the outputs of sboxes $(S_0,S_1,S_2,S_3)$ and $X_{n+1}$ is the result of multiplying this vector with the MDS matrix $M$.

See the answer to this question as well.


Single string producing two different hash results with SHA-256

No.  This doesn't make sense.  SHA-256 is a mathematical function on bit strings.  As such, it doesn't give different answers at different times of day or under different phases of the moon.  It gives different answers only for different inputs.


o(1) in time complexity of number field sieve

Summary: it is common, and arguably safe, to assume that the $o(1)$ term is positive, and take it at zero, in circumstances where the formula is then used to estimate a lower bound of the ratio of work for larger value of $n$ to that for smaller values of $n$.

The formula given, with $o(1)$ term, gives the complexity of NFS. If modified by assigning a real value (say, zero) to the $o(1)$ term, it yields a function of $n$ without unit, thus insufficient to calculate the time (or effort, or cost) needed to run the algorithm for a given $n$. The $o(1)$ term happens to encompass the very order of magnitude of the cost (as a consequence of the outer exponential and the positive exponent to the $\log n$ term).

However, a common and legitimate use of that formula is to evaluate how the effort to run the NFS scales with $n$, by computing the ratio of what the formula gives for different values of $n$ (and taking the base-2 log for a security variation in bits). In that sense, it makes sense to ask which value of $o(1)$ should be used for a given $n$.

I don't know, and likely that depends on the variant of NFS (which also has a huge influence on $C$), and the hardware at hand.

However, a common approach is to hypothesize that this $o(1)$ term is positive, and take it as zero when extrapolating how larger $n$ needs to be, thus (if the hypothesis is correct) erring on the safe side from a key-holder's point of view.

Addition commenting the self-answer: an example of the practice in the previous paragraph is the formula given by the NIST in Implementation Guidance for FIPS PUB 140-2 and the Cryptographic Module Validation Program (updated August 1, 2016), computing the conventional bit strength $x$ of an RSA public modulus of $L$ bits as
$$x\;=\;{1.923\times\sqrt[3]{L\log(2)}\times\sqrt[3]{(\log(L\log (2)))^2}-4.69\over\log(2)}$$
which is obtained by

straightforward transformation of the GNFS complexity formula using $C=\sqrt[3]{64\over9}$ rounded to 4 significant digits;
ignoring the $o(1)$ term, thus obtaining an $x$ such that $2^x$ is an estimation of work in unknown unit;
solving the above issue by introducing the additive constant $-4.69$ (which really is a multiplicative constant of $2^{-4.69/\log(2)}$ on the involved work $2^x$), determined so that when $L=1024=2^{10}$, the result obtained is $x=80.000\dots$, because that fits the FIPS 140-2 normative context, and anecdotal evidence suggests that the cost of breaking common 80-bit symmetric cryptography would be smaller than the cost of factoring a properly generated 1024-bit RSA modulus.

That formula thus arguably errs on the safe side from the key-holder's point of view if used to estimate the security given by an RSA modulus of $L\ge1024$ bits properly generated from true randomness, under the assumption that GNFS roughly as practiced now remains the best factoring algorithm.


After more Googling I found a paper called "A note on high-security
general-purpose elliptic curves" which contains some "legacy strength" Edwards curves that might work. Thought I'd self-answer in case anyone else ever needs something like this.


Is HTTPS encryption using the RSA algorithm?

What is the difference between the two?

That question feels like the question "what is the difference between a truck and an 8 cylinder engine?"

They are different, in the sense that they serve different goals.  HTTPS may use RSA (just like a truck may use an 8 cylinder engine), however HTTPS has a lot more to it (just like a truck consists of a lot more than the engine).

RSA is a cryptographical primitive; it can be used to implement public key encryption (as the page mentions); that is, someone can have a public key (which they can distribute); anyone can use that public key to encrypt messages that only the holder of the private key can read.  RSA can also implement signatures; someone with the private key can 'sign' messages, and anyone with the public key can verify that that message was 'signed'.

HTTPS is a cryptographical protocol; in particular, it tries to be a method of implementing security for transit HTTP traffic.  It makes sure that the HTTP traffic you get is actually from the web server you think it is, and that no one can read it or modify it in transit.  It can use RSA as one of the cryptographical primitives it relies on, but it doesn't have to (actually, the current trend is to get away from RSA public key encryption in favor of other primitives).  In addition, it also relies on other cryptographical primitives as well.


Converting Ciphertext to a Number in RSA

The ciphertext of RSA is actually just a number in the range 0..N that has been encoded to an octet string (another name for byte array) of the same size as the minimum modulus N. To be precise, the ciphertext is an unsigned, statically sized, big endian integer.

The PKCS#1 standard defines it this way, both for PKCS#1 as well as OAEP padding:

  Convert the ciphertext representative c to a ciphertext C of
          length k octets (see Section 4.1):

  C = I2OSP (c, k).

Where I2OSP - integer to octet string primitive - is defined here. I2OSP is just a mathematical way of defining how the number is encoded as described in the first section of the answer. Stupid implementations actually perform these kinds of calculations, most implementations require some resizing / reversing (in case little endian is used internally) and smart implementations already keep the numbers in the correct format in memory.

Now for textbook RSA, you can, of course, argue that pointing to the PKCS#1 specification is unfair because textbook RSA is not defined in that standard, and textbook RSA isn't required to follow the conventions specified in it. However, the fact that the ciphertext is just an encoded number remains. Sometimes the minimum length and / or little endian encoding is returned and of course, some implementations will simply return the number without performing encoding at all. However, in all cases, it should be easy to get the numeric value of the ciphertext - which is just the result of modular exponentiation with the public exponent after all.

Note that many languages - notably the C language - unfortunately handle bytes and characters as being the same type; they are not. The bytes generated by encoding a number can have any value and may not be printable. If you need a printable text that contains these bytes you will have to encode the bytes to a string, e.g. base 64 or hexadecimal encoding. Some libraries allow you to specify this as output size, and some bad ones even default to performing an encoding over the ciphertext bytes. To convert those back you need to first decode back into bytes and then perform the bytes-to-number conversion.

Despite the possible output values, you should never ever have to perform calculations on the individual bytes unless you cannot load any kind of library that does this for you and you will have to define your BigNum yourself (and yes, I have been there). Usually the cryptographic libraries themselves contain this kind of library; they need the functionality after all. They are quite often in the "hazmat" part of the library or not directly present in the API however.


Using salted hash as password for easy memorization without reuse?

This is better than password reuse, but still not cryptographically strong, for it is vulnerable to (extensive) brute-force search of the relatively short key (your 11-character kFnU7Ra%P1_, which is optimistically worth 66 bit of entropy) for someone who knows the salt (your stackexchange) and a password. As a theoretical aside, although we know no practical attack if the key was longer, we have no strong argument that there is not.

Critical: each user should have a different salt for each site, thus you really should add the user's name in the salt.

If you want the key to remains short, what you want is a key derivation function purposely slowed-down for use with a short key. That could be scrypt, bcrypt, or PBKDF2. It brings you vastly improved, and parameterizable resistance to that attack.

If the key can be long and high-entropy, you could use HMAC-SHA256, with the salt as the message.

Also, a minor, tractable problem is that hashes, KDFs, and MACs, produce arbitrary bytes, some of which are not acceptable in a password by many sites. You need a post-processing to turn that into something acceptable, but the rules vary from site to site: different minimum and maximum length, different (and occasionally incompatible) caveats on the required or prohibited presence of certain special characters.

Note: the idea, and the variations suggested, are well known.

Update: using a 21-character string with each character chosen at random among a set of $64=2^6$ gives you $126=21\cdot6$ bits of entropy, which is ample even if you use a non-slowed-down KDF, or MAC, rather than scrypt/bcrypt/PBKDF2.

It is an entirely different thing if you are using a 21-character string that Joe User can choose. A significant fraction of Joes will choose terrible keys, and be unsafe. A compromise is something like diceware, that Joes can not choose (or can only choose among a few hundred random choices), but can be asked to memorize (he will likely write it down or store it in a "secret" clear text file; also, some Joes will forget the key, loose the paper, or/and accidentally destroy the file). In this way, you can hope to pack 48 bits of entropy in 21 characters. I would recommend a longer string that can be memorized over a shorter that can not, see the obligatory XKCD cartoon. Combined with scrypt or even the lesser bcrypt, and settings resulting in 0.2 second of CPU work per use, this is good enough for most uses: if an attacker manages to be $2^5$ times more efficient than the legitimate Joe, the expected work per attack is still $2^{48-5-1}\cdot 0.2$ CPU.second, that is $>130.000$ CPU.year; and sizable RAM (resp. some, little) for each CPU during the whole attack time, if scrypt (resp. bcrypt, PBKDF2) is used; for scrypt, RAM is where a lot of the investment cost of the attacker would be.


Highest prime factor that is Safe for a particular scheme

There is some confusion here. The definition of prime numbers states that cannot be factored (see Definition of prime numbers)

You seem to be talking about RSA modulus which is the product of two prime numbers (see RSA cryptosystem).

As far as keylength is concerned 768 bits is not considered safe today. Note that the keylength choice is a compromise between speed and security, basically we're trying to estimate the shortest keylength that is beyond the cryptanalytic capabilities of any attacker (that needs to stay true as long as the data is valuable). Since we base that estimate on the best publicly known attacks against the cryptosystem (namely here factoring) running on publicky available hardware we add a cushion to take into account increase in computing power, entities that know or will know more than we do.

To answer your question, new RSA public keys should be at least 2048 bits long so slightly larger than your 1600 bits initial proposal here. For further reference you can refer to the keylength website.


If the keys are all independent and near-uniform random, then an chosen-plaintext attacker has near-zero advantage in the IND-CPA game.

In the IND-CPA game, the attacker can ask for the ciphertexts of any plaintexts of their choice (CPA, Chosen-Plaintext Attack), and then submits two challenge messages, and, given the ciphertext for one of challenge messages, wins the game if they can tell which one (IND for indistinguishability).  The attacker's advantage is their probability above 1/2 of winning this game.  This is the standard notion of security for an unauthenticated cipher.

Of course, this only thwarts an eavesdropper who can listen but not touch the messages.  A MITM could easily transform one ciphertext into another, forging messages without raising any alarms, even if they can't learn anything about the plaintext given the ciphertext—they may know a priori what the plaintext will be and may want to replace it by something else.

So this is usually not enough security for applications that involve, say, the internet: you need an authenticated cipher for that, for example a one-time pad with a one-time authenticator appended, which is the model that AES-GCM and NaCl crypto_secretbox_xsalsa20poly1305 make practical with short keys expanded pseudorandomly into message-length pads.


I have recently detailed the use of Itoh-Tsuji in the article on Curve9767 (section 3.6).

In the description below, I write elements of $GF(p^m)$ as polynomials in $GF(p)[z]$, taken modulo a given irreducible unitary polynomial $M$ of degree $m$ (since all finite fields with the same cardinal are isomorphic to each other, the choice of a specific $M$ has no importance for security, but some choices of $M$ allow for better performance, as will be shown below). We consider the problem of computing the inverse $a^{-1}$ of a given element $a \in GF(p^m)$ (with $a \neq 0$).

$p^m-1$ is a multiple of $p-1$; in fact, the quotient is:
$$ r = \frac{p^m-1}{p-1} = 1 + p + p^2 + p^3 + \cdots + p^{m-1} $$
For any $a \in GF(p^m)$ distinct from zero, we can express the inverse of $a$ as:
$$ a^{-1} = \frac{a^{r-1}}{a^r} $$
This is true for any integer $r$, but for $r = (p^m-1)/(p-1)$, this leads to fast inversion thanks to two main facts, detailed below.
Fact 1: $a^r \in GF(p)$. Indeed, $(a^r)^{p-1} = a^{p^m-1} = 1$ (since $p^m-1$ is the order of the group of invertible elements in $GF(p^m)$). Thus, $a^r$ is a root of the polynomial equation $X^{p-1} - 1 = 0$. However, all non-zero elements of $GF(p)$ are roots of that polynomial (by Fermat's Little Theorem), and there are $p-1$ non-zero elements in $GF(p)$, and $X^{p-1} - 1$, being a polynomial of degree $p-1$ in a field, cannot have more than $p-1$ roots. Therefore, the roots of $X^{p-1}-1$ are exactly the non-zero elements of $GF(p)$, and $a^r$ is one of them.

This implies that inverting $a^r$ is much easier than inverting in general an element of $GF(p^m)$, since we can work in $GF(p)$. There are various methods for computing inverses modulo $p$, but if $p$ is small, Fermat's Little Theorem works well (i.e. raising $a^r$ to the power $p-2$).
Fact 2: computing $a^{r-1}$ is inexpensive, thanks to the Frobenius automorphism. The $j$-th Frobenius automorphism (for $j >= 0$) is:
\begin{eqnarray*}
\Phi_j : GF(p^m) &\longrightarrow& GF(p^m) \\
a &\longmapsto& a^{p^j}
\end{eqnarray*}
i.e. $\Phi_1$ is just "raising to the power $p$", and $\Phi_j$ is "applying $\Phi_1$ exactly $j$ times".

This operator is a field automorphism: $\Phi_j(ab) = \Phi_j(a) \Phi_j(b)$ and $\Phi_j(a+b)$ = $\Phi_j(a) + \Phi_j(b)$ for all $a, b \in GF(p^m)$. This makes it linear (if we interpret $GF(p^m)$ as a vector space of dimension $m$ over $GF(p)$) and thus reasonably easy to compute: if:
$$ a = \sum_{i=0}^{m-1} a_i z^i $$
then:
$$ \Phi_j(x) = \sum_{i=0}^{m-1} a_i \Phi_j(z^i) $$
Moreover, if $GF(p^m)$ is defined with a modulus of the form $M = z^m - c$ for some constant $c \in GF(p)$ (there are constants $c$ that ensure that $z^m-c$ is irreducible, as long as $m$ divides $p-1$), then $\Phi_j(z^i) = c^{ij(p-1)/m}$, and applying $\Phi_j$ on any value $a$ becomes a matter of multiplying the $m$ coefficients $a_i$ of $a$ by $m$ constants that are easily precomputed. This makes $\Phi_j$ inexpensive (much cheaper than a single multiplication in $GF(p^m)$).

For any $a \in GF(p^m)$, we can compute $a^{r-1}$ by using a few multiplications and Frobenius operators:
\begin{eqnarray*}
t_1 &=& \Phi_1(a) &=& a^{p} \\
t_2 &=& t_1 \Phi_1(t_1) &=& a^{p+p^2} \\
t_3 &=& t_2 \Phi_2(t_2) &=& a^{p+p^2+p^3+p^4} \\
t_4 &=& t_3 \Phi_4(t_3) &=& a^{p+p^2+p^3+p^4+\cdots+p^{8}} \\
& & \ldots & &
\end{eqnarray*}
With about $\log m$ multiplications and applications of a Frobenius operator, one can obtain $a^{r-1}$.

Using all of the above, the complete inversion algorithm of $a \in GF(p^m)$ is then:

Using multiplications and the Frobenius operators, compute $a^{r-1}$.
Multiply $a$ by $a^{r-1}$ to get $a^r$ (this multiplication is made easy because we know that the result is in $GF(p)$, so we have only one coefficient to compute; the other ones are all zero).
Invert $a^r$ in $GF(p)$ (using for instance Fermat's Little Theorem).
Multiply $a^{r-1}$ by $a^{-r}$ (this multiplication is also easy, since $a^{-r} \in GF(p)$).

In Curve9767, which uses the field $GF(9767^{19})$, I can get the complete cost of the inversion down to about 6 to 7.7 times that of a multiplication in $GF(p^m)$, which is fast enough to seriously contemplate the use of affine coordinates for the operations on the elliptic curve. By comparison, usual algorithms for inversion modulo a 256-bit integer $n$ will take between 50 and 300 times the cost of a multiplication modulo $n$.

All of that is said in the generic context of $GF(p^m)$. Itoh and Tsuji first described it for $GF(2^m)$, i.e. with $p = 2$, in which case the Frobenius operator $\Phi_1$ is simply "squaring". Moreover, with $p = 2$, inversion in $GF(p)$ is a no-operation (since $GF(2)$ has only a single non-zero element, which is $1$, and $1$ is its own inverse), so $a^r = 1$; the inversion of $a^r$ and the multiplication by $a^{-r}$ can then be skipped. On the other hand, with $p = 2$, the modulus $M$ cannot be $z^m-c$ for some $c \in GF(2)$ because neither $X^m$ nor $X^m-1$ is irreducible over $GF(2)$, and you need an irreducible modulus to get a field. This makes the Frobenius operators somewhat more complex to compute (but still quite efficient).


Under what conditions did a Bletchley bombe stop?

After a year I have managed to find a suitable solution to the problem. My understanding is based on the following picture that I created, based on a simplified version that I found online (at present I cannot find the reference, if I do I will edit it in).

It is supposed to be a bombe and can be understood in two parts.

The top contains 26 columns, one per letter of the alphabet. Each column is made of 26 connections one from each letter to each other. That what gives the triangular effect.
The bottom half are what would be the bombe connections depending on the menu derived from the crib. Each block that we can see spans and connects two columns are based on the crib and the corresponding position of the rotors.

The idea is that in the real bombe all these lines are wires and a current is introduced arbitrarily somewhere. Then the current flows through the diagram making lines 'live' and others not.
A live connection between two letters means that either there is a Steckerverbindung between them else they are not Steckered together. Although this sounds like a tautology, we do need to consider the picture as a whole. For example: if at the A column only the F connection is live, then it means that it is consistent that A and F are Steckered together; if at the A column more both F and G are live, then it means that A is not Steckered with either F or G; if at the A column all connections are live, then this means we have a definite contradiction, and that means the bombe position is false - and in such a case the bombe, I assume, would have just continued.
We can test the information above with such a diagram as above. The following diagrams are all close ups of the diagram above (the top right part of the bottom half):

The bombe is in the correct position and the current is sent into a correct connection, as in the picture below. Here the current is sent to the X connection in the R column. I indicated in red the live current. It flows through the diagram and as can be seen. Eventually we see that the L wire of the T column s live, as is the E wire of the V column. Nothing else in this block becomes live. So it is consistent that we have the three Steckerverbinugen RX, TL and VE.
The bombe is in the correct position and the current is sent into a false connection. Again we can use the picture above but now we concentrate on the blue. Here I assumed the current was sent in at the A wire of the T column. In this case eventually every wire is live except the correct wires as given above (at least in the given part of the picture). When I say eventually, this means that one has to follow in and out of all the connections, and up through the top part of the diagram when necessary. Hence when the bombe is in a correct position and viewing the diagram as a graph, we would have (ideally) two connected components: the correct component (where there is at most one live wire per column) and the false component (where we would have at least one non-live wire pre column). I say ideally since there would be at least one extra component of information that is unobtainable from the rest (i.e. letters that are not part of the steckers we can find and don't appear in the crib).
If the bombe is in a false position, then it shouldn't matter we the current is sent in. I did this in the following diagram, which is the same as the original but all rotors have been shifted by one position. Here the current enters at the L wire of the T column. In this case, eventually, everything becomes live, which gives the contradiction.

We also learn from this set up the importance of the loops in the crib. This enables a lot of feedback, which is particularly important when the current is sent into the false wire.
Hence to answer my original question: when did the bombe stop? It seems that it should not stop when one column is completely live. And therefore perhaps it stopped when there was at least one non-live wire per column. If your crib had no loops, and therefore no feedback, then this condition would be easily satisfied, and there would be far too many bombe stops to deal with.
Edit after 4 years: I found in the book The Hut Six Story from Gordon Welchman first published in 1982 (although my copy seems to be first published in 1997) Appendix I p241 it says: Thus, in order to detect a "drop", the bombe needs to look for one of only two situations: a case in which current does not get back to any test register terminal other than A, or one in which there is some terminal other than A to which current does not get back.


I believe it would match the relaxed RCCA security, but it looks like it wouldn't be of much use because reencryption would not be secure.  You could generate reencryptions of any ciphertext, but they would not be indistinguishable from each other, i.e. given $c_1$ and $c_2$ you can determine easily whether $c_2$ is a reencryption of $c_1$.


Linear Feedback shift register over integers

I'm not sure I understood your question correctly, but what Solinas is doing is shifting the input polynomial by multiplying it by $t$ and reducing modulo $f(t)$

To compute the reduction it subtracts $f(t)=t^3-t+1$.
So, for example, after shifting the first line (where shifting means multiplication by $t$) what you obtain is: $t^3$ from which you subtract the modulus, so $t^3-t^3+t-1=t-1$ which is what you obtain in the second row.

And so on for the other rows.

In the table, the top row identifies the constant term, degree-1 term, and degree-2 term of the polynomials, while the second row (-1,1,0) identifies the value used for the modular reduction. The third row is the initial value of the LFSR which is $t^2$ by Solinas' construction.


The equivalence of exponentiation and multiplication over elliptic curves

So this is more a question of notation than anythig else. So let's examine the notation.

$$\left(g^{a}\right)^{i^2}\bmod p$$

which is equivalent to

$$g^{a\cdot i^2}\bmod p$$

means the following: Consider the group $\mathbb Z _p^*$, that is the set of non-negative integers smaller than $p$ along with the neutral element $1$ and the group operation of multiplication modulo $p$ and write this group multiplicatively with $g\in\mathbb Z_p^*$ and $a,i$ being normal integers.

Now if, instead we wrote the above as an additive group (which is merely a change of notation!), we would replace $\cdot$ with $+$ and exponentiation $g^x$ with multiplication by a scalar $x\cdot G$. So the above expression immediately becomes $(a\cdot i^2)\cdot G$ (up to commutativity and associativity). And the commutativity is a given on elliptic curves (because otherwise DH key exchanges wouldn't work).


Combining multiple symmetric encryption algorithms - implications?

I can see based upon your question that you're not already a crypto-expert.  Given that, I think the single most useful answer I can give you is this:

  Multiple encryption addresses a problem that mostly doesn't exist. Modern ciphers rarely get broken -- at least, not in the Swordfish sense. You're far more likely to get hit by malware or an implementation bug than you are to suffer from a catastrophic attack on AES.

That's a quote from http://blog.cryptographyengineering.com/2012/02/multiple-encryption.html, which is an excellent article on this topic.

Moreover, if you have to ask this question, you should not be using multiple encryption.  It's a little bit tricky, and you're more likely to screw something up than to get any meaningful security gain.

Bottom line: No, you can't add more security by using multiple encryption.  The block cipher isn't the weak link, and strengthening the strongest link in a system does not add more security.  Modern block ciphers appear to be effectively unbreakable; if that's correct, multiple encryption is pointless.  So, my recommendation is: don't do it.  It doesn't solve any real-world problem, it doesn't add much benefit, and it adds the extra risk that you might screw something up.  Use standard well-vetted cryptographic solutions, like TLS, Truecrypt, GPG, etc.


How the degree reduction in BGW protocol works?

I refer you to a full proof of the paper with all of the details on how the protocol works. See: http://eprint.iacr.org/2011/136.pdf.


A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B.

Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number.

See: Quadratic residue problem on composite integers


Is Rabin's cryptosystem secure against known-plaintext attacks?

Both Rabin and RSA rely on padding for security. Proper padding prevents chosen-ciphertext attacks since modified ciphertext has a negligible chance of producing valid padding.

If you claim Rabin (or RSA) is vulnerable to CCA attacks, you should limit that to the unpadded/textbook variants. Most deployed implementations use padding, though some paddings are still vulnerable (e.g. PKCS#1v1.5 padding for RSA).

Another important property of padding is randomization to prevent plaintext guessing attacks, which would otherwise break low entropy messages.

=> Rabin without padding is only a building block, not something that should be used directly as secure encryption.
The most basic property asymmetric encryption needs to provide is security against chosen plaintext attacks, since the attacker can encrypt arbitrary plaintexts. Security against chosen plaintext attacks trivially implies security against known plaintext attacks.

=> Any secure asymmetric encryption is secure against known plaintext attacks, this includes Rabin.


How large is the Playfair cipher keyspace?

The Playfair key matrix contains a permutation of the 25-letter cipher alphabet.  The total number of such permutations is

\begin{aligned}
25! &= 1 \times 2 \times 3 \times \dots \times 25 \\
&= 15{,}511{,}210{,}043{,}330{,}985{,}984{,}000{,}000.
\end{aligned}

However, as I noted in a previous answer, the Playfair cipher has equivalent keys: moving a row or a column from one side of the matrix to the opposite makes no difference to the Playfair encryption process.

By repeatedly moving rows and/or columns around in this way, we can pick any of the 25 letters and move it to any desired position in the matrix.  Doing so fixes the positions of the remaining letters, though, so in effect each key matrix belongs to a class of 25 equivalent matrices.  The total number of such equivalence classes is therefore

\begin{aligned}
\frac{25!}{25} = 24!
&= 1 \times 2 \times 3 \times \dots \times 24 \\
&= 620{,}448{,}401{,}733{,}239{,}439{,}360{,}000.
\end{aligned}

Ps. For what it's worth, $24! \approx 2^{79}$.  That is to say, the number of distinct (equivalence classes of)  Playfair key matrices approximately matches the number of distinct 79-bit bitstrings — comparable to, say, the 80-bit keys of the modern Skipjack cipher.  Even so, in practice, Playfair encryption can be broken using just pencil and paper, whereas breaking Skipjack by brute force (though perhaps nowadays possible for large state actors) would require a massive and expensive computing cluster.

The difference is, in large part, due to the fact that a Playfair key can be attacked incrementally: the encryption of each letter pair is determined by only a small part of the key matrix, and does so in a relatively simple way, allowing that specific part of the matrix to be determined just by comparing individual pieces of the plaintext and the ciphertext.  And since the parts overlap, it's possible to join them together piece by piece, like a jigsaw puzzle, until the whole key matrix (up to equivalence, anyway) has been reconstructed.

Modern ciphers, in contrast, are designed so that every bit of the key affects the encryption of every part of the plaintext, and changing even a single bit of the key changes the ciphertext completely in a seemingly random way.  Thus, such incremental attacks are generally not feasible against modern ciphers, so that the fastest possible attack becomes brute force testing of all possible keys one by one.

(Or, at least, that's how it's supposed to be; every once in a while, modern ciphers do get broken by new cryptanalytic attacks — the fancy modern descendants of the kind of statistical and combinatorical attacks that cryptologists of old employed against ciphers like Playfair.  Still, nowadays, the existence of any practical attack against a cipher that is faster than brute force is generally considered to mean that the cipher in question is broken.)


Is there any better algorithm ?

Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient.  You say that it's trial and error (and it is), however it's about as efficient as the traditional algorithms we use to search for primes; if you're looking for an $q$ bit prime, then you'd expect to need to try an average of $\log(2^q) / 2 = q \log(2)/2$ sets of primes before finding one that makes up a prime (actually, a bit less, because you know apriori the numbers you generate won't have $q_1, q_2, ..., q_n$ as a factor).

An alternative approach to creating a weak DLog problem is to make $g$ weak; that is, generate a $p$ of the form $2qr + 1$, where $q$ is a small prime and $r$ is a large one (and the same algorithm can be used to seach for it).  Then, you select $g$ to be of order $q$ (that is, you select a random value $h$ and set $g = h^{2r} \bmod p$, and check that it's not 1); if $q$ is an $m$-bit prime, then the discrete log problem will take $O(2^{m/2})$ time; for example, $m=32$ makes this solvable in milliseconds.

Of course, the use of either approach can be fairly easily detected by someone examining $p$ and $g$...


AES is a block cipher, a cryptographic primitive that is meant to be used in a larger framework. Its sole purview is encrypting a single block of data given a certain-sized key. In the case of AES-256, the key size is 256 bits.

Notably, there is no password involved in AES. So, there is no password length to discuss. AES itself just uses keys.

If you are using a service which claims it uses AES-256, and you are forced to enter a password, what is likely happening is that your password is used to derive a key. This is often done using a key derivation function, like PBKDF2, which stands for "password-based key derivation function 2". (Some KDFs are meant to expand real, uniformly-random keys, while others are intended to have "human"-like passwords for inputs.)

So, in this hypothetical scenario, the direct key used for AES-256 is likely the output of the KDF given your password as an input. If this is the case, then your password can be whatever length you so desire, although longer passwords are more difficult to guess (i.e., stronger). The job of a KDF is take the input and produce a "good" key from it.


How to find the keyword of the Playfair cipher, given the plaintext and the ciphertext?

First of all, you cannot uniquely determine the keyword of a Playfair cipher, or even the key table constructed from it, simply because there are multiple equivalent key tables that will produce the same ciphertext (and multiple keywords that will produce each table).

In particular, the following key tables are all equivalent:

Original:        Row shift:       Column shift:
                                     <--
A B C D E        F G H I K        B C D E A
F G H I K      ^ L M N O P        G H I K F
L M N O P      | Q R S T U        M N O P L
Q R S T U        V W X Y Z        R S T U Q
V W X Y Z        A B C D E        W X Y Z V

We can shift any Playfair key table like this to obtain another different table that produces the same ciphertext.  The row and column shifts can be repeated and combined to move any letter of the grid into the top left corner, yielding 25 distinct equivalent tables.

In principle, we can never tell which of these equivalent tables was used just by examining the plaintext and ciphertext.  Of course, in practice, if the original table was constructed based on a keyword, it may be possible to recognize one of these equivalent tables as being more likely than others, but in principle each of them could be obtained from some keyword.  (Trivially, just take the keyword to be all the letters in the table, written out row by row.)  And of course, since repeated letters in the keyword are ignored, each table has a limitless number of possible keywords that can produce it (although, again, some may appear more likely than others in practice).

OK, so we can't uniquely determine the key table.  What can we do, then?

If we have a piece of ciphertext and know the corresponding plaintext, we can just break them up into two-letter groups and compile a list of which plaintext pair corresponds to which ciphertext pair, like this:

Plaintext:  AT TA CK AT DA WN
Ciphertext: DQ QD EH DQ EB XM

Pairs:
  AT -> DQ
  CK -> EH
  DA -> EB
  TA -> QD
  WN -> XM

In principle, with enough known plaintext / ciphertext pairs, we can just compile a (nearly) complete dictionary of letter pairs like this, and use it to decrypt unknown messages.  Basically, by doing this, we're just treating the Playfair cipher as a simple substitution cipher on letter pairs.  Even if we never figure out the actual key table, having such a dictionary is basically as good as having the key.

The only problem is that, while common letter pairs like TH, HE or AT are likely to occur pretty often both in our known plaintext and in any unknown messages we might want to decode, other less common pairs of letters might not happen to appear in our known plaintext.  Of course, we can infer some new pairs directly, e.g. from the letter exchange symmetry of the Playfair cipher: if we know that XY encrypts to PQ, then we also know that YX encrypts to QP.  But it would be nice to do more than that.

In fact, we can learn quite a lot about the structure of the key table just by applying some simple logic to the observed letter pairs:

Generally, any time we observe that a letter X encrypts (or decrypts) to some other letter Y in any letter pair, we know that X and Y must belong either to the same row or to the same column.
If we observe any two pairs of letters that encrypt to each other, like AX ⇆ BY, then we immediately know that:

A and X do not belong to the same row or column (and neither do B and Y),
A and B belong to the same row (and so do X and Y),
A and Y belong to the same column (and so do B and X).

(Of course, using the exchange symmetry, observing that AX → BY and YB → XA yields the same information as well.)
If we observe that the plaintext and the ciphertext pair share a letter, like XY → YZ, then we know that all these letters must belong to the same row or to the same column, and in particular, that this row or column must contain the (left-to-right or top-to-down) letter sequence X Y Z (which might, of course, wrap around the edge).
If we observe that XY encrypts to PQ, but PQ encrypts to, say, YA (or to BX) then we know that all these letters must also belong to the same row or column, and that this entire row or column must be some shifted version of X P Y Q A (or Y Q X P B).

(If XY encrypts to PQ, the encryption of PQ must contain at least one of X and Y; the only way in which an encryption chain like XY → PQ → AB would be possible in Playfair would be if all those six letters shared the same row or column; but, of course, a standard Playfair key table only has five letters in each row or column!)
Similarly, if we observe e.g. that XA encrypts to YB, and XB encrypts to YC, then all these letters must belong to the same row or column, and their order must be X Y A B C.
Finally, if we observe that X encrypts to Y both in AX → BY and in PX → QY, where all the six letters are distinct, then we know that all these letters cannot all belong to the same column (since they would not fit), and so X and Y must be in the same row (and so must A and B, and also P and Q).  Since all six letters also cannot fit into a single row, we can further deduce that they must be arrange in one of the following three patterns:

X Y            X-Y A-B            X-Y P-Q
A B                               A-B
P Q            P-Q

where the rows and the columns can be rearranged in any order, and the remaining rows and columns of the key table inserted at any position around or between them, except that the columns joined with - in the last two patterns must be adjacent in the key table and appear in the order shown (possibly wrapping around the edge, of course).

(Of course, this is not an exhaustive list; other similar rules can also be deduced from the constraints of the Playfair key table structure and the encryption rules.)

The rest is just basic puzzle solving, not entirely unlike, say, solving a sudoku.  Since any shifted version of the key table yields the same encryption, we can arbitrarily place any letter we want in, say, the top left corner of the table.  It's of course most convenient to pick one of the letters for which we've already figured out a complete row or column using the deduction rules above, if we have any, because then we can immediately fill it in (or make two candidate tables, if we're not sure if the sequence we've figured out is a row or a column) and proceed from there.  Then we just keep filling in more and more letters (possibly sometimes tentatively at first, until our guess is confirmed) based on what we can deduce from the known ciphertext / plaintext pairs, until the entire table is solved or until we run out of clues.

For example, let me encrypt a piece of text using the (trivial) key table given earlier above, and try to reconstruct the key table from the result:

Plaintext:  EX AM PL EA QU IC KB RO WN FO XI UM PS OV ER TH EL AZ YD OG
Ciphertext: CZ BL LM AB RQ HD GE TM XM IL YH RP NU LY BU SI AP EV DI MI

Let me first look for cases where the plaintext and the ciphertext pair share a letter (since those always mean that all the letters must share a row or a column).  We find a bunch of these near the beginning (PL → LM, EA → AB and QU → RQ) and one more near the end (YD → DI).  So we know that the sequences P L M, E A B, U Q R and Y D I must occur (horizontally or vertically, possibly wrapping around) in the key table.

The next thing to look for would be letter pairs that occur both in the plaintext and the ciphertext, but alas, in this case there aren't any, not even reversed.  There's a few near misses (like the ciphertext pair EV, which occurs reversed in the plaintext, but split between two pairs) but those don't really help.

So let me next look for common letters and their en/decryptions, to see which letters they share their row and column with.  The letter E, for example, encrypts to C, A and B and decrypts to B and A.

We already know that the sequence E A B occurs horizontally or vertically in the table, and therefore that A is below or to the right of E.  The only way in which AZ can thus encrypt to EV is if the sequence E A B is horizontal, and the sequence Z V ? (where the letter marked by ? is yet unknown) occurs at the same position in some other row.

Arbitrarily fixing E to the top left corner (because why not?), we thus already have two partial rows:

E A B ? ?
Z V ? ? ?

Can we expand them somehow?  Looking for the letter B next, we find (besides the EA → AB pair we already considered) the pairs AM → BL, KB → GE and ER → BU.

The AM → BL pair tells us that L M must occur in some row at the same position as A B.  It doesn't fit into the rows we already have, so we end up with yet another partial row.  In fact, we can also place P on the same row, based on the known sequence P L M.  The pairs KB → GE and ER → BU (and the known sequence U Q R) give us two more partial rows, yielding:

E A B ? ?
Z V ? ? ?
P L M ? ?
K ? G ? ?
U Q R ? ?

That's half the table filled in already!  Note that the order of the rows is still unknown, but we can leave that for later.  (It actually affects only a relatively small fraction of the ciphertext / plaintext pairs, since it only matters when both plaintext letters happen to be in the same column.)

To fill in the rest, we can try to look for pairs where one of the already placed letters appears in the plaintext and another letter from the same column appears in the corresponding ciphertext.  (Due to the way Playfair encryption works, that's actually really common.)  For example, the very first plaintext / ciphertext pair is EX → CZ, where we already know that E and Z share a column, letting us tentatively place C and X in the corresponding rows:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?
K ? G ? ?
U Q R ? ?

Note that I've placed them off to the side for now, since we still don't know which of the last two columns they belong in.  The next pairs with two letters that we know to belong to the same column are RO → TM and PS → NU, giving us:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?  +    O N
K ? G ? ?
U Q R ? ?  +    T S

Again, I still don't know which of the remaining columns these letters belong to, so I've also set them off to the side as partial columns.  The next pair OV → LY is interesting, though, since besides the letters V and L (which we know belong to the second column) it also includes the letter O, meaning that Y must belong to the same column as O.  This in turn leaves no place in that column for C and X, so they must belong to the same column as N and S, giving us the following table (with the order of the rows and the relative order of the last two columns yet to be determined):

E A B ? C
Z V ? Y X
P L M O N
K ? G ? ?
U Q R T S

Next we have the pair TH → SI.  We know that T and S belong to the same row, and there's no room in that row for H and I, so they must belong to the only other row where both of those columns are still free:

E A B ? C
Z V ? Y X
P L M O N
K ? G I H
U Q R T S

Now we have two letters from the consecutive sequence Y D I that we determined earlier in the same column, so we can finally start to figure out the order of the rows (and to fill in the missing letter D in the only place it can go):

Z V ? Y X
E A B D C
K ? G I H
P L M O N
U Q R T S

We now know the order of the first three rows and the first three columns, and have two letters (F and W) yet to be placed.  At this point we could even start simply guessing, since we really only have three two-way choices left (order of last two rows, order of last two columns, position of F and W), for a total of 2 × 2 × 2 = 8 possible key tables.  Or we could try to narrow down the choice further, say, by looking for letter pairs with F or W in them, of which we find two: WN → XM and FO → IL.  These let us confidently place W in the first row and F in the third, giving us the full (but still partly unsorted) table:

Z V W Y X
E A B D C
K F G I H
P L M O N
U Q R T S

Can we figure out the order of the remaining two rows and columns?  For that, we'd need to find some more pairs where all the letters share the same row or column.  Alas, it turns out that there aren't any in this example plaintext / ciphertext pair, so we're left with four non-equivalent key tables (and all their shifted equivalents) that all could have produced this ciphertext:

Z V W Y X    Z V W X Y    Z V W Y X    Z V W X Y
E A B D C    E A B C D    E A B D C    E A B C D
K F G I H    K F G H I    K F G I H    K F G H I
P L M O N    P L M N O    U Q R T S    U Q R S T
U Q R T S    U Q R S T    P L M O N    P L M N O

Of course, by visual examination, we might be able to notice that one of these key tables shows a simple pattern that is broken in the others.  Or, if we're more systematically inclined, we could try shifting all of them so that the letters X, Y and Z are in the bottom right corner (where they're most likely to end up, using the standard method of constructing a Playfair key table based on a keyword) and then checking which of the tables could be generated by the shortest keyword (which, or course, in this example turns out to have been a zero-length one).


What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption".

‘Standard assumption’ broadly means an assumption that has withstood the scrutiny of many smart cryptanalysts for a long time.  Examples:

We think that, for uniform random 1024-bit primes $p$ and $q$, solving $y = x^3 \bmod pq$ for uniform random $x$ is hard given $pq$ and $y$.

Why?  The best way anyone has been able to figure out how to do it is by factoring $n$ to recover $p$ and $q$, and the best known methods—ECM and NFS—cost more than anyone has the budget for.
We think that solving $y = \operatorname{AES}_k(x)$ for uniform random $k$ is hard given $x$ and $y$.

Why?  The best way anyone has been able to figure out how to do it is essentially by a generic search, and the best known methods—parallel rainbow tables, parallel distinguished points—cost more than anyone has the budget for.

Half-examples:

Pairing-based cryptography.  Pairings are highly popular in academic cryptography at conferences but see very little use in the real world, outside exotic cryptocurrency applications.  The security story for pairing-friendly elliptic curves is nowhere near as stable as the security story for elliptic curves for more traditional DLOG applications like Diffie–Hellman key agreement and Schnorr signatures.
SVP, LWE, and other lattice problems.  Lattices are a promising area for post-quantum cryptography, but there is a large design space with a complicated security story that has not stabilized yet—no matter how many completely incomprehensible arguments Chris Peikert and Dan Bernstein have about average-case/worst-case reductions on Twitter.

Non-examples:

Conjugacy search in a braid group.  Braid cryptography is not widely studied by cryptographers and most existing proposals turn out to be broken.
SIMON and SPECK.  These block ciphers are popular among spooks trying to muscle their way into international standardization, but it turns out standards bodies are no longer happy to accept the word of spooks without technical justification these days, and also block sizes smaller than 128 bits are foolish.

  The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions."

This is an example of academic obfuscation, and evidence that Wikipedia is a terrible resource for learning about cryptography.  What it means is:

We proved a theorem,1 and the theorem involves pretty number theory2 and asymptotic growth curves!3

1 This is what provable security means.  It does not mean that the theorem has any real-world consequences whatsoever.

2 This is what ‘standard assumptions’ means here: ugly problems like inverting DES are not allowed, but pretty problems like factoring a product of uniform random primes are allowed.

3 Not formally stated: We are only interested in asymptotic growth curves of attack costs for families of problems, so DES is doubly disqualified both because it's ugly and because there's only one DES, whereas you can consider the problem of factoring as a function of the size of the factors.  (‘Provable security’ treatment with concrete parameter choices, sometimes called ‘exact security’, didn't come until a decade later with the help of Bellare and Rogaway.)

To be fair, the GM paper was helpful for setting down some formalizations like semantic security for public-key encryption, which is essentially equivalent to the modern standard of ciphertext indistinguishability which we use today.  But the GM encryption scheme?  Completely useless, even if there is a theorem.

This kind of obfuscation—and fetishization of number-theoretic prettiness—leads people down regrettable paths like adopting Dual_EC_DRBG, which admits proofs of ‘number-theoretic-based security’, as major national cryptography standards simply by virtue of being number-theoretic, propelled by prestidigitators like Dan Brown whose principal area of expertise is obfuscating gaping back doors among reams of analytic prose that nobody can get through.

  Is RSAP also commonly supposed to be hard? Is thus RSA provably secure?

The RSA problem—computing $e^{\mathit{th}}$ roots modulo a product of large secret primes—is commonly supposed to be hard.  There are public-key encryption schemes and public-key signature schemes built out of RSA that have theorems—e.g., RSAES-OAEP, RSA-KEM, RSASSA-PSS, RSA-FDH—which are even somewhat useful in relating the difficulty of breaking the security of the cryptosystem (distinguishing ciphertexts, forging signatures) to the difficulty of computing $e^{\mathit{th}}$ roots modulo a product of large secret primes.

But I recommend that you stay away from the dishonest term of art ‘provable security’ because it obfuscates what you're actually saying—especially in the form ‘X is provably secure’.

Whether a scheme has ‘provable security’ or not is irrelevant to users or engineers making decisions about building systems—the conclusions of cryptanalysts about what cryptography will withstand attack are what's relevant to them.  ‘Provable security’ is really about guiding cryptanalysts to focus their effort.  There's no point in analyzing AES-CTR separately from AES, because any way to break AES-CTR either (a) depends on on misuse of CTR, (b) is based on AES's nature as a permutation rather than arbitrary function, or (c) implies an attack on AES.  That's because there is a useful theorem relating any attack on AES-CTR to an attack on AES itself.

Similarly, there's not much point trying to forge RSA-FDH signatures without trying to compute $e^{\mathit{th}}$ roots, because—thanks to a useful theorem—we know that any work done on one problem translates immediately to the other, as long as the hash function doesn't interact in any interesting way with RSA (which would be quite astonishing).  So cryptanalysts can ignore the details of RSA-FDH and focus on computing $e^{\mathit{th}}$ roots to give us confidence in the security of RSA-FDH.


RSA padding and Least Significat Bit Oracle Attack

Actually, the "Least Significant Bit Oracle attack" isn't actually an attack.

Instead, it is the observation that, if you were given a magical black box (an Oracle) that is able to take an RSA encrypted ciphertext, and give you the lsbit of the plaintext, you could use that Oracle to decrypt the entire ciphertext.

What we can conclude from that observation is that determining the lsbit of the plaintext is as difficult as doing a full decryption.  We use the phrase "hard bit" when discussing this (and similar) situations.

Since we don't actually have such a magical Oracle, we can't actually perform this in practice.

Since this is not specifically an attack (and in fact, is proof that the lsbit is not specifically weak), padding methods don't need to defend against it.


Why do we use multiple rounds of encryption?

Using the same scheme multiple times will allow for efficient crypto-analysis. If the cipher cannot be analysed then this will be considered detrimental to security. The cipher itself doesn't need to be hard; it just must be hard to reverse without the key. The rounds themselves do not provide enough confusion to be considered a full cipher themselves.

Having rounds where the same scheme is repeated allows for efficient implementation, making the code size much smaller and easier to protect against side channel attacks.

Yes, the required number of rounds can be limited to the best attack available. Generally any cipher with rounds will have successful (if theoretical) attacks over a number of rounds. The problem is that you don't know which attacks will be devised in the future.

So in the end some kind of margin is in order; there is a non-trivial balance between future proofing an algorithm and performance. To what number of rounds an algorithm is tweaked is often subject to discussion.

Having at least 3 "spare rounds" is probably advised. That doesn't take into account the complexity of each round (Threefish is used with 80 lightweight rounds while AES uses a minimum of 10, more complex rounds). You'd expect more "spare rounds" when a lot of rounds are required in the first place.

Generally block ciphers will use rounds, but stream ciphers may use different ways of generating a key stream. Asymmetric encryption such as RSA generally doesn't use rounds at all.

It's certainly not a theoretical security requirement to use rounds.


Security of key bits under indistinguishability for randomized encryption

If you could guess the key, you could decrypt the challenge ciphertexts and figure out which plaintext is which.

Conversely, if the cryptosystem has ciphertext indistinguishability in this attack model, then you obviously can't figure out which plaintext is which, so you can't guess the key.


Can someone give me an example of a Merkle–Damgård transformation?

You get it wrong when saying

  Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits

because you have a

  …compression function that takes inputs of 4-bits and outputs 2-bits

You don't split the message in half and then fiddle with some initialisation factor to make all pieces fit. That's not how it works.

Instead, if the bits you feed to the compression function are too many, you split them up in according pieces; in your example 4 bit inputs. If you end up with the final piece not being 4 bits, you pad it with the number of missing bits so that you can again feed the expected 4-bit length to the compression function.

So, you would feed those 6 bits into your compression function like this:

You take the first 4 bits of the message, which you feed to the compression function.
Next, you take the remaining 2 bits of the message, followed by 2 bits of padding to fill it up to 4 bits so that you can again feed 4 bits to the compression function-

Simplified example: Let your message be 6 bits 111111, the padding be 0, and the compression function takes a 4-bit length input. You first feed 1111 to the compression function, finally, you feed 1100 (notice the two padding bits) to the compression function.

Same example using bit positions: Let your message be 6 bits at positions 654321, the padding be 0, and the compression function takes a 4-bit length input. You first feed 6543 to the compression function, finally you feed 2100 to the compression function.

As you can see, the initialization vector is rather irrelevant at this stage where you're feeding the message to the compression function. All that's done is splitting up your message into appropriately sized pieces, and using padding at the end (final block) to fill up what's missing.

Nota Bene: You only asked about a specific part of SHA-256, but I nevertheless would like to point out that (when talking about SHA-256 and alike cryptographically secure hashes) the final block doesn't only contain padding but also includes the length of the input message to avoid length extension attacks. In case the message happens to fit the compression function input length and/or doesn't leave enough room to append the input message length, an additional piece (containing nothing but padding | length of the input message) is fed to the compression function.

If this last note confuses you, you might want to check the “Length padding example” at Wikipedia’s article about the “Merkle–Damgård construction”, or maybe even read the complete article offered there as it practically covers all points mentioned here… and more.


Prove Vigenere cipher isn't perfectly secret

One way to approach this is to look at the decryption process; the plaintext is a function of the ciphertext and the key.  The conditional probability says you know the ciphertext (entropy 0), you don't know the key (entropy $n \log_2 26$); what's the entropy of the decrypted plaintext (which is a function of those two)?  How does that compare to the entropy of an arbitrary plaintext of length $2n$?


How do applications set up secure communications through an untrusted middleman?

There is no way to establish a shared key with a man in the middle attack and no trusted third party.

With a trusted third party, they can validate public keys so that the man in the middle can't send his.


where should private and public keys be stored?

You should keep the private key as safe as possible. How safe depends on the security requirements and risk assessment. A key store, such as a PKCS#12 key store or Java key store enables you to store a key protected by - usually - a password. This is obviously more secure than storing it as plaintext at the same location.

It is possible to mitigate the risk of storing in plain by using e.g. a thumb drive as storage device, and only use the storage instead.

Another form of key store may be present on a device such as a TPM, a HSM or smart card. Such devices usually protect against dictionary and brute force attacks by minimizing the attack surface - e.g. by blocking after a maximum incorrect log in attempts.

A key store may contain a certificate chains for private keys of the user, but it may also store trusted certificates. Trusted (root) certificates are for instance used to create TLS connections from your browser to websites. TLS can also be configured to use client authentication; in that case the key store contains both the private key + certificate chain and trusted certificates.

If a key store just contains certificates then it is usually called a trust store instead.

Use a key store if you can, especially those provided by the runtime system. A runtime system can often make use of lower level security mechanisms and provide a higher level of trust than mere applications can.

Note that some API's such as Microsoft .NET  act as if private keys are part of a certificate. They are not; although the public and private keys are part of one key pair, the private key and certificate are distinct. In Java the (E)JKS key stored contain a private key and certificate chain per key entry but they are retrieved separately.

These key stores are not really generic, they have been build for X509 compatible PKI (as used in browsers).


Is there a way to do single key-pair asymmetric encryption?

Yes, RSA is an example of a cryptosystem where this is possible. The message is encrypted using the recipient's public key only and even the sender could not decrypt it.

However, in the comments you mention that you would like to minimize storage requirements. RSA would require e.g. 2048 bits for just the message. In comparison, with ECIES sending a one-time key with the message you are looking at a minimum of about 512 bits for a one AES block message, 256-bit curve and 128-bit MAC.

So it is not really wasteful to do it like CodesInChaos suggested.


Is there any semantic difference between predicate encryption and functional encryption?

PE is a subclass of FE.

This (from the other answer) is correct.

Also, from my understanding, your analogy is correct. PE returns the plaintext if the predicate evaluates to true. FE, on the other hand, returns a function of the plaintext.

We can say that PE is a subclass of FE, since we can use FE to implement PE. Just use the identity function.

Your example of $f$ being a machine learning function is an example of something that FE can do that PE cannot.


ASCII input to HMAC weaker than raw bytes?

In one sense, no, encoding should not have an impact on security of HMAC.

On the other hand, it could have an application dependent impact.

Consider the following. '26' and 26 have the same HMAC. Now, assume your code receives a message, M, and an HMAC, MAC, and then does something like this

if HMAC(M, private_key) == MAC:
  if isinstance(M, basestring):
    grant_admin_privileges()
  else:
    grant_non_admin_privileges()
else:
  raise Exception('Bad HMAC')

Well, now obviously you are in trouble.


Impacts of not using RSA exponent of 65537

Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to 8.5 times). If using a proper padding scheme, the choice of $e$ is not known to make a security difference; but for many less than perfect padding schemes that have been (or are still) used, high values of $e$ (compared to the number of bits in the public modulus $n$) are generally safer.

$e=65537$ is a common compromise between being high, and increasing the cost of raising to the $e$-th power: any higher odd $e$ cost at least one more multiplication (or squaring), which is true for odd exponents of the form $2^k+1$. Also, $e=65537$ is prime, which slightly simplify generating a prime $p$ suitable as RSA modulus, implying $\gcd(p-1,e)=1$, which reduce to $p\not\equiv 1\pmod e$ for prime $e$. Only the Fermat primes $3,5,17,257,65537$ have both properties, and all are common choices of $e$. It is conjectured that there are no other Fermat prime; and if there was any, it would we unusably huge.

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used; these attacks tend to be more likely or devastating with much smaller $e$. Using $e=3$ would otherwise be attractive, since raising to the power $e=3$ cost 1 squaring and 1 multiplication, to be compared to 16 squaring and 1 multiplication when raising to the power $e=65537=2^{16}+1$.

For example, RSA with $e=65537$ has a security advantage over $e=3$ when:

Sending a message naively encrypted as $\mathtt{ciphertext}=\mathtt{plaintext}^e\bmod n$; the greater $e$ makes it more likely that $\log_2(\mathtt{plaintext})\gg \log_2(n)/e$ (which is necessary for security).
Sending the same message encrypted to $k$ recipients using the same padding (including any deterministic padding independent of $n$); the greater $e$ makes it less likely that $k\ge e$  (which allows a break).
Signing messages chosen by the adversary with a bad signature scheme. For example, with the scheme of the (withdrawn) ISO/IEC 9796 standard (described in HAC section 11.3.5), the adversary could obtain a forged signature from only 1 legitimate signature if $e=3$, but needs 3 legitimate signatures for $e=65537$; trust me on that one. The security advantage of $e=65537$ is wider for attacks against scheme 1 of the (current) ISO/IEC 9796-2.

For more explanations and examples of the risk of the combination of questionable message padding and low $e$, see section 4 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.

There is no known technical imperative not to use $e=3$ when using a sound message padding scheme, such as RSAES-OAEP or RSASSA-PSS from PKCS#1, or scheme 2 or 3 from ISO/IEC 9796-2. However, it still makes sense to use $e=65537$:

The only known drawbacks are the performance loss (by a factor like 8), and the risk of leaving a bug in the key generator when a prime $p\equiv 1\pmod{65537}$ is hit; and when performance matters, there is an even better choice than $e=3$, with provable security (but more complex and uncommon).
Some attacks on less than perfect RSA schemes that are (or have been) in wide use are significantly harder than with $e=3$ (as discussed above).
$e=65537$ has become an industry standard (I have yet to find any RSA hardware of software that does not allow it), and is prescribed by some certification authorities.


The main modern standard RSA-based signature scheme is RSASSA-PSS in PKCS#1 v2, also standardized as IETF RFC 8017 (v2.2, obsoletes v2.1 in RFC 3447).  This is a variant of PSS proposed and analyzed by Bellare and Rogaway in 1996.

Beware: RSASSA-PSS as standardized by RSA, Inc., in the early 2000s, around the same time as Dual_EC_DRBG,* is vulnerable to collisions in the underlying hash function by virtue of using $H(r \mathbin\Vert H(m))$, instead of $H(r \mathbin\Vert m)$, which would have required of $H$ the much more modest security property (enhanced) target collision resistance.  This vulnerability to collisions led to a technique for practical HTTPS certificate forgery by academics, and to a different technique for certificate forgery used in an international incident of industrial sabotage by the United States and Israel against Iran.

If you need to get code running right now and for some reason you need to use RSA, that's the practical answer.  If you need to get code running right now but you don't actually need to use RSA, use Ed25519 instead—except for verification speed, it is an all-around faster, safer, and compacter signature scheme.

If you are studying existing code or an existing protocol that was not designed by a competent cryptographer, and you are wondering whether it uses a state-of-the-art signature scheme, you should expect it to use either RSASSA-PSS or PKCS#1 v1.5 signature.  If it doesn't, your eyebrows should be raised and whoever designed it has some justifyin' to do.

If you are intellectually absorbed by the wonders of the world of cryptography, or if like me you're a bone-eating vulture who likes blathering at strangers on the internet about things you've learned, then you should also know about full-domain hash, which was discarded essentially for political reasons among cryptographers but is easy to implement and instantiate with modern XOFs like SHAKE256, and Rabin–Williams signatures, which are more efficient with a tighter security reduction.  But make sure you know what you're trying to achieve before you go down that rabbit hole!

* I have no evidence to support a connection here, but coincidences like these are remarkably good at playing evidence in games of charades at parties.


suitable programming language for cryptography algorithms

You can call C from Java. You can call C libraries from just about anything.

Java isn't suitable for some cryptographic applications because you can't guard against garbage collector attacks, not because it's slow. It's not particularly slow. C does have a byte type, it's called "char". Object Pascal (Delphi) isn't a systems programming language, and so shouldn't be used to implement a crypto library.

Finally, do not implement your own cryptographic algorithms. Use an existing library.


A Question about Irreducible Polynomials

In the page $104$ you can see:
$$F_{2^8}=\frac{Z_2[x]}{x^8+x^4+x^3+x+1}.$$
this means that irreducible polynomial that generate the $F_{2^8}$ is $x^8+x^4+x^3+x+1$. so, in multiplications, you should note that $x^8=-x^4-x^3-x-1=x^4+x^3+x+1$. Therefore $x^{8+i}=x^8\cdot x^i=x^{4+i}+x^{3+i}+x^{1+i}+x^i$.


Difference between special honest verifier zero-knowledge and zero-knowledge property

"Can we say $\pi$ satisfies SHVZK?"

Yes you can. As any proof system which satisfies ZK property, also achieves SHVZK.

Regard to "My doubt is In SHVZK, simulator produces accepting transcript where as in ZK property there is no condition about acceptance of transcript generated by simulator."

Note that in the definition of ZK, it is mentioned that "Let $(P,V)$ be an interactive proof system". A proof system should be complete, meaning that a honest prover always convinces honest verifier, which implies that the proof should be acceptable. So, even if in the definition of ZK, clearly is not mentioned that the proof should be acceptable, but similar to the SHVZK proof, a simulated ZK proof should be acceptable by verifier.


Encryption and decryption using multiple different keys

It seems that the similar problem was discussed here. The general approach was to encrypt the file with a random key and then encrypt copies of this key with users' keys.

However, if you'd like really different keys, check @ddddavidee's answer.


Does PBKDF2 reveal any knowledge about the salt?

No, the adversary won't learn anything about the salt, if the salt is a cryptographic random of sufficient length.

A PBKDF such as PBKDF2 is generally build up from keyed one-way-functions (PRF's) such as HMAC's. That means that you cannot retrieve any of the inputs given the output. It does mean that if the inputs when put together can be guessed or brute forced that the input can be verified to be correct.

A secret salt is commonly called a pepper which acts as a secret key. The security provided by the pepper is comparable to a secret key of the same length.

A pepper can be concatenated with a real salt to create a new salt input parameter. The real salt can be stored together with the output of PBKDF2 or the ciphertext to avoid that identical pepper & password combinations can be identified.


What is the Advantages and Disadvantages of digital signatures over HMAC?

Digital signatures provide non-repudiation, which is one of the basic principles of information security, and HMACs do not (since the key in HMAC is known both to the sender and the receiver).

And then of course the points you mentioned also apply.


How can you produce visual cryptography?

Actually, it's fairly simple:

Generate an image with random pixelation; that is, each pixel is either black or white with probability 1/2.  We'll call this image 1.
Exclusive-or image 1 with the target to generate image 2; so that a pixel image 2 will be white if the pixels in image 1 and the target are the same (both with or both black), and black if they differ.

Now, you combine the two images by overlaying them; what this effectively does is an AND function, in the sense that a pixel in the combined image will be white only if both image 1 and image 2 are white.

Now, if we have an area of pixels in the target image which are black, then when we combine those images, that area will be black as well.  That's because, of any pixel in that area, either the pixel in image 1 will be black, or the pixel in image 2 will be black.

In contrast, if we have an area of pixels in the target image which are white, then when we combine those images, that area will be gray (likely consist of half white and half black pixels).  Any pixels that happen to be black in image 1 will, of course, be black; any pixels that happen to be white in image 1 will also be white in image 2; as image 1 was random, this results in a gray area.


Similarly, just send the identity element $\mathcal{O}$ as the public key.
Alice must be a fool to not validate the public key to fall into this trap. The first rule is to check that $P \neq \mathcal{O}$

Update per user's comment

How can i find the identity element of curve 25519?

The identity of some curves like Curve25519 is the point of infinity ( represented as $\mathcal{O} \text { or } \infty$) and this can't be represented in the affine coordinates. We need to use projective coordinate systems.
We took the Curve25519 equation $$y^2 = x^3 + 486662 x^2 + x$$ and convert it into homogeneous equation $$Y^2 Z - X^3 - 486662 X^2 Z - X Z^2$$
Now the points are triple $(X:Y:Z)$ where actually a point now represent a line $(\lambda X:\lambda Y: \lambda Z)$
The point at infinity is $(0:1:0)$ and this cannot be treated as an affine point.
Any affine point $(x,y)$ can be turned into homogenous by $(x:y:1)$ and any homogenous point other than the infinity $(X:Y:Z)$ can be turned back with $(X/Z,Y/Z)$.


Period, correlation and auto-correlation of non-linear feedback shift registers based sequences

The reason such generators are used is to avoid the Berlekamp Massey attack by introducing high linear complexity. However, even though there are many publications on these, the theory is far from complete.

One line of research is finding NLFSRs that generate de Bruijn sequences, this goes back to the 1970s.

For your specific question, there is an almost tailor made solution in terms of autocorrelations. The GMW sequences (Gordon Mills Welch) are nonlinear with high linear complexity and autocorrelation same as m-sequences. They are constructed by using an intermediate field and a power function as a permutation of the intermediate field. So instead of $$s(t)=tr^n_1(\alpha^t)$$ as in m-sequences take $n=km,$ with $k\geq 2$ an integer and consider the sequence
$$s(t)=tr^n_m([tr^m_1(\alpha^t)]^u)$$
which is your basic GMW sequence, provided $gcd(2^n-1,u)=1$ so that the power map is a permutation.

Cross correlations are a bit harder to control, depending on how many sequences you want, but there are some results in the third reference which may make it easier (beyond experimentation).

The Spread Spectrum Handbook covers GMW sequences from an engineering point of view. J-S. No generalized GMW designs, Klapper et al introduced Generalized GMW sequences, etc. The talk slides by Helleseth here are a good point to start in terms of general background.

Some references:

R. A. Scholtz and L. R. Welch, GMW Sequences, IEEE Trans. on Inform. Theory, 30(3):548-553, 1984

H. Fredricksen. A Survey of Full Length Nonlinear Shift Register Cycle Algorithms. SIAM Review, 24(2):195–221, 1982.

Li, Hu and Zeng, A Criterion for Determining the Crosscorrelation of Binary
Sequences from GMW Constructions, IEEE International Workshop on Signal Design and Applications.


Can a deck of cards be used as a practical source of cryptographic randomness?

You're asking about a composition of two things:

Choosing a key—or perhaps passphrase—uniformly among $52!$ possibilities by shuffling a deck.  Although the key is not a uniform random bit string, it is uniform random in another space.
Expanding the key $k$ into a large effectively uniform random pad by computing $x_0 = \operatorname{SHA512}(k)$, $x_1 = \operatorname{SHA512}(\operatorname{trunc}(x_0))$, $x_2 = \operatorname{SHA512}(\operatorname{trunc}(x_1))$, etc., and returning $x_0 \mathbin\| x_1 \mathbin\| x_2 \mathbin\| \cdots$.

In the random process of part (1), if you do a good job shuffling then it's a reasonable way to choose a key from a weird space.

But in the deterministic procedure of part (2), it's trivially breakable—i.e., the procedure is not a good pseudorandom generator—because given $x_0$, or any $x_i$, I can perfectly predict the entire remainder of the output.

However, there's other possibilities:

$\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \cdots$, where the numbers $0, 1, 2, \dots$ are uniquely encoded in fixed width.
$\operatorname{AES}_{k'}(0) \mathbin\| \operatorname{AES}_{k'}(1) \mathbin\| \operatorname{AES}_{k'}(2) \mathbin\| \cdots$, where $k' = \operatorname{SHA512}(k)$.
In general, you could feed a hash $H(k)$ of $k$ to any pseudorandom generator $G$ to get an arbitrarily long effectively uniform random pad, where $H$ is a random oracle or reasonable to model as such like SHA512.  $G$ can be AES in CTR mode, or can be a Keccak duplex, or anything else that has PRG security.

For practical use, the standard way to do things is:

Use a random process—like shuffling a deck of cards and transcribing the order—to arrive at a secret string; the process need not have uniform distribution as long as it has high min-entropy.
Use a standard key derivation function—like HKDF-SHA256—to convert the maybe-nonuniform but high-min-entropy secret string input, together with an optional salt that is unique per user, into a family of effectively uniform keys, labeled by their purpose so that you can use the same secret string input for multiple cryptosystems.
Use standard cryptosystems—like X25519, AES-GCM, HMAC-SHA256—with the resulting keys confident that they are effectively uniformly distributed, in accordance with the security contracts of the cryptosystems.


Is creating an authentication-key (mac) from the encryption password a vulnerability?

It is possible to create both an encryption key and authentication key from a password securely.

It is very likely that an attacker knows part of the plaintext most of the time. That makes it very possible to verify correct guesses of the password, even without verifying an authentication tag (MAC). This is especially true if there are multiple messages to test.

So although it is perfectly possible to verify a MAC key over purely random messages and impossible to do the same for encryption keys, the addition of a MAC should not make much of a difference for structured messages.

For passwords brute forcing can certainly be used, but slightly more advanced techniques such as dictionary attacks may also be used. Usually some form of key strengthening is used to derive master key material. That master key material can then be used to derive an encryption and MAC key.

These keys can be made cryptographically independent from each other. But that doesn't matter much since finding the password is the easiest form of attack and finding the password will of course allow an attacker to calculate both keys.


Is this hand cipher any more secure than the Vigenère cipher?

Given that the permutation is fixed and the key step is independent of the permutation you can reduce this to an ordinary text-substitution cipher.

If the key is as long as the input you have a weak one-time pad, because the per letter change is limited to 10 instead of 26.

However if the key is short then you have a Vigenère cipher (if you "decode" with $key=0$ then it is exactly a Vigenère cipher).

In essence you use 2 transformations: a character scramble ($P$  $P'$) and a "xor" ($X+$ and $X-$).

Your algorithm is $text1=X+(P(text_0),key)$for each phase.

However this is equivalent to $text1= P(X+(text_0,P'(key)))$.

Then the next fase is $text_2= P(X+(P(X+(text_0,P'(key))),P'(key)))$ which can be rewritten to $text2 = P(P(X+(X+(text0,P'(key) ), P'(P'(key))))$ and so on.

Given that P is easily reversible you can extract $X+(text, X+(P'(key), P'(P'(key)) )$.


$p-1$ is certainly a weak private key, in that it forces the shared secret to be a constant value as:

$a^{p-1} \bmod p = 1$

(This is known as Fermat's Little Theorem; no relation to Fermat's Last Theorem)

Hence, if either side uses $p-1$ as there private key, then both sides would arrive at the value of 1, and that's not great for security.


Noisiest RF band for random number generation

This is not likely to be a good method to generate random numbers -- at least not on its own, without significant additional analysis.  You need a source of random numbers that is not only noisy, but also unpredictable to an adversary.  It's not clear that radio will meet that need.  If you listen on a FM band, an adversary who is nearby can also listen on the same FM frequency and will likely see something very similar to what you see, so will have a huge leg up in predicting the numbers you generated.

Bottom line: don't try to roll your own random-number source.  It's better to use a time-tested scheme, like a crypto-strength hardware RNG, or /dev/urandom, or a similar crypto-strength scheme.


Yes, the IV is the same in both encryption and decryption for all modes that use an IV.  And yes, the decrypter must have access to the IV to decrypt the ciphertext.  The IV is not a secret.

The only caveat is that for CBC mode the IV must be unpredictable to an attacker whose data is being encrypted by another party.  Once the attacker has presented the data to be encrypted that IV need no longer be secret.


Offline authenticated encryption for pub/sub

You need to sign your messages and then encrypt them (sign-then-encrypt). The signature generation is performed using the private key from the publisher (sender) and the encryption is performed using the public key from the subscriber (receiver). The decryption is performed using the private key of the receiver and the signature verification is performed by the public key of the sender. The private keys remain private, the public keys need to be trusted.

  only publisher can create messages

Anybody can create messages, they are just bytes after all. Only the publisher should be able to create messages accepted by the subscriber.

  publisher & subscriber can both read messages and authenticate the publisher

Encrypt not just for the subscriber but also for the publisher and you should be fine.

  offline message transfer

Sure thing, but note that you may still have all the problems of a transport protocol. For instance, you could be vulnerable to padding oracle attacks if you encrypt using CBC mode.

  messages can't be read by non-participants

Only the subscribers (receivers) and publisher would have the corresponding private keys, so yeah.

  subscribers can be mobile platforms (Android, iPhone), i.e. less powerful processors

Neither of the schemes here would be troublesome for relatively low powered devices (if you can call the latest sets of smart phones "low powered" with 64 bit operations, hardware crypto accellerators and over 2 GHz clock speeds for the top and midrange models).

  messages lifetime target is 15 years

15 years is a long, long time in crypto. But if you use 512 / 512 bit curves and 256 bit symmetric cryptography (256 bit AES, for instance) then your message should be secure for a long time, unless crypto-analysis using quantum computing takes off on a large scale.

  messages are small, a few dozen bytes

An ECDSA signature at 512 bits is already 128 bytes minimum, and an ephemeral public key (needed for ECIES) would take around 64 bytes. A few dozen bytes seems a very small amount of available message space.

  I know that RSA can do this by encrypting a message specific key using a private key and decrypting using the public key (waving hands over some details here)

No, it cannot. The public key should be considered public.


Are there any quantum-resistant symmetric encryption schemes?

Yes; virtually all of them. Quantum computers give a quadratic speedup on a general search problems (so key lengths need to double), but I don't know of any symmetric schemes in actual use for which quantum computation gives a bigger speedup.


Pseudorandom functions: how are functions stored?

For the definition of pseudorandomness, the family $F$ of functions can be any set of functions at all. But typically we take it to be a set where each function can be described by a rather short key/seed, and where one can efficiently compute the function output given the input (and the key). This is because we want the family $F$ to represent functions that we can randomly choose from and use in real life.

For example, $F$ could be the set of functions AES$_k$, taken over all 128-bit strings $k$ (where AES$_k$ denotes the AES block cipher with key $k$).  Notice that there are "only" $2^{128}$ functions in this family, which is much less than the number of functions mapping 128 bits to 128 bits (which is $(2^{128})^{2^{128}}$).


Is establishing a secret key possible given this characteristic primitive?

During startup (and perhaps in regular intervals) I can exchange several messages between two trusted devices knowing for certain that the messages were sent by that trusted device (due to device-specific characteristic voltage spikes on the network).
Is this sufficient to establish a shared secret or key?

Should be; during start-up, have each device select a random signature public key, and broadcast it (and have every other device remember the public keys that they can validate came from a specific device).
Assuming that honest device A knows honest device B's public key (and knows that it is, in fact, B's key), and B knows A's public key, then it becomes easy; for example, A can generate a Diffie-Hellman key share, sign it with his private signature key, and send it to B; B also picks a DH key share, and sends a signed copy to A.  A and B validate the signatures they received, and then compute the shared secret.
No third device can recover the shared secret based on the published key shares, signatures and public keys.  In addition, because the key shares are signed, no one can modify them without one of the signature verification steps giving an error.
Now, I suspect that doing the above may be a bit more than what you personally want to take on; however it is most assuredly a solvable problem.


Yes (guessing you are doing the cypher challenge?)

The "Beaufort Decoder" is a really good decoding tool (saves you time), then trial and error keywords. Also, the "Vigenère cracking tool can be used to find the length of the keyword. Paste the texts you're decoding; the number of the column(s) with the most x's is the length of the keyword.


What is the difference between ECDSA and EdDSA?

Partially covered by does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448? but to add a little, rfc8032 describes EdDSA's advantages as:

  EdDSA provides high performance on a variety of platforms;
  The use of a unique random number for each signature is not
     required;
  It is more resilient to side-channel attacks;
  EdDSA uses small public keys (32 or 57 bytes) and signatures (64
     or 114 bytes) for Ed25519 and Ed448, respectively;
  The formulas are "complete", i.e., they are valid for all points
     on the curve, with no exceptions.  This obviates the need for
     EdDSA to perform expensive point validation on untrusted public
     values; and
  EdDSA provides collision resilience, meaning that hash-function
     collisions do not break this system (only holds for PureEdDSA).

ECDSA also has small sizes (4) though not exactly the same ones -- and (all? most?) applications use ASN.1 which is variable size and a little more complicated, although the algorithm itself doesn't require that. ECDSA also has good performance (1), although Bernstein et al argue that EdDSA's use of Edwards form makes it easier to get good performance and side-channel resistance (3) and robustness (5) at the same time. EdDSA also uses a different verification equation (pointed out in the link above) that AFAICS is a little easier to check.

Standardized ECDSA does require random per message and fails catastrophically if it repeats for different messages (2); rfc6979 by our very own bear proposes a fix for this but has not been widely adopted, at least not yet. (6) just means the EdDSA standard allows omitting the message hash, which the ECDSA standard officially doesn't but in practice people do anyway, so I consider this difference spurious.

For some more on the differences caused/enabled by Edwards form, see:
Elliptic Curves of different forms
What are the differences between the elliptic curve equations?
What is the curve type of SECP256K1?

There's also the general effect of EdDSA being newer, which has both real advantages (learn from and adapt to field experience, optimize for modern systems and implementation methods) and spurious ones (more fashionable and gives the impression of being 'in with the cool kids'). Plus there's the effect of Bernstein not being the US government, which some people just distrust and/or dislike, for reasons that are mostly out of scope here.