Cryptanalysis of XOR cipher with repeated key phrase

The first thing you should do is estimate the key length.  While you may be able to do this using Kasiski examination, in this modern era of computers I very much recommend instead using the index of coindicence, which you can compute very easily, e.g. with this Python program:

import sys
msg = sys.stdin.read()   # read ciphertext from standard input

for step in range(1, 50):
    match = total = 0
    for i in range(len(msg)):
        for j in range(i + step, len(msg), step):
            total += 1
            if msg[i] == msg[j]: match += 1

    ioc = float(match) / float(total)

    # output the IoC as a percentage, and plot it as an ASCII bar chart
    print("%3d%7.2f%% %s" % (step, 100*ioc, "#" * int(0.5 + 500*ioc)))

(Actually, the ioc value this code computes is the raw ratio of matching pairs to all byte pairs a multiple of step bytes apart; unlike the Wikipedia definition I linked to above, it doesn't multiply it by the size of the alphabet.  For simply comparing IoC values between different key lengths, this difference doesn't matter.)

For a quick test, I encrypted your question text (length = 628 bytes) by XORing it with the repeated string This is the key. (length = 16 bytes), and then ran the code above on it, and got the following output:

  1   2.39% ############
  2   2.49% ############
  3   2.38% ############
  4   3.45% #################
  5   2.35% ############
  6   2.55% #############
  7   2.28% ###########
  8   4.77% ########################
  9   2.41% ############
 10   2.40% ############
 11   2.28% ###########
 12   3.52% ##################
 13   2.34% ############
 14   2.26% ###########
 15   2.32% ############
 16   7.30% #####################################
 17   2.51% #############
 18   2.58% #############
 19   2.22% ###########
 20   3.26% ################
 21   2.24% ###########
 22   2.22% ###########
 23   2.43% ############
 24   4.82% ########################
 25   2.05% ##########
 26   2.35% ############
 27   2.40% ############
 28   3.06% ###############
 29   2.20% ###########
 30   2.33% ############
 31   2.15% ###########
 32   7.21% ####################################
 33   2.17% ###########
 34   2.39% ############
 35   1.97% ##########
 36   3.58% ##################
 37   2.07% ##########
 38   2.25% ###########
 39   1.98% ##########
 40   4.44% ######################
 41   2.09% ##########
 42   2.26% ###########
 43   2.06% ##########
 44   3.19% ################
 45   2.41% ############
 46   2.16% ###########
 47   2.16% ###########
 48   7.38% #####################################
 49   2.13% ###########

Looking at the output, you can clearly see the peaks in the IoC at multiples of the key length (16 bytes), as well as lower peaks at multiples of 4 and 8 (which evenly divide the key length).

Now that you've determined the key length, you're basically left with the task of solving 16 (or however many characters your key has) single-byte XOR ciphers, one for each key byte.

There are several ways to do that; for example, you could simply split the ciphertext into 16 columns and apply standard frequency analysis to each column:

Try to decrypt each column with every possible byte.
Compute the number of times each byte appears in the result.
Select the key byte that yields a distribution most similar to natural English letter frequencies according to some statistical distance measure.

In fact, we can do better than that: since we know that each of the columns is sampled from the same plaintext, and thus presumably has approximately the same plaintext byte distribution, we can pick any two columns, run a frequency analysis on both, and output the byte that, when XORed with one of the columns, makes its byte frequency distribution most similar (by some measure such as the Battacharyya coefficient) to the other one.

This will not directly give us the key bytes, but it does give us a very good guess about their pairwise XOR, without requiring any prior knowledge of the underlying plaintext byte frequency.  Knowing the pairwise XORs of the key bytes, we can then reduce the problem to that of guessing any one of the actual key bytes, which is very easy.

Computing the most likely XOR between each pair of key bytes also gives us a nice built-in consistency check: the XOR values $x_{ij}$ should satisfy the consistency relation $x_{ik} = x_{ij} \oplus x_{jk}$ for all $i$, $j$, $k$; if they do not, that's a sign that (at least) one of the values must be wrong, and it might be worth trying one of the other likely values.

(I ran this test on the same example ciphertext as above, and it guessed all but one of the pairwise XORs between the key bytes correctly.  Spotting the single mistake was easy due to the failed consistency check.)

For the particular case where the key and/or the plaintext are (mostly) ASCII text, it may be quicker to exploit the bit structure of ASCII, and particularly the following facts:

Ordinary ASCII uses only 7 bits per character, so the eighth bit will always be zero in plain ASCII text.  (If there are any bytes in the ciphertext with the eighth bit set, it implies that either the plaintext and/or the key contains some non-ASCII bytes — possibly UTF-8 or one of the ISO Latin charsets.)
All ASCII letters have the seventh bit set, while spaces and numbers and (most) punctuation has it unset.
The sixth bit is set for lowercase letters and unset for uppercase letters.  The ASCII space character only has the sixth bit set, and so XORing a letter with a space merely flips the case of the letter!
All ASCII bytes with both the sixth and the seventh bit unset are unprintable control characters; the only ones likely to appear in normal text are the line feed (LF = 0xA), tab (0x9) and possibly the carriage return (CR = 0xD, normally always followed by a line feed).
Numbers have the seventh bit unset, and the fifth and sixth bit set.

In particular, this implies that:

If one of the ciphertext columns contains only null bytes and letters, and if most of the letters are uppercase, then it's fairly safe to guess that the corresponding key byte is a space (or possibly a punctuation mark).
Conversely, if a column contains mostly control characters and a few uppercase letters, with most of the letters being the same, then the corresponding plaintext byte is probably a lowercase letter (and probably the lowercase version of the most common uppercase letter in the column).
Finally, if a column contains mostly numbers and punctuation, with a few lowercase letters, then the corresponding plaintext byte is probably an uppercase letter (and probably the uppercase version of the most common lowercase letter in the column).

For example, I took the example ciphertext I got by encrypting your question with the 16-byte key This is the key. and split it into 16 separate files each containing one column.  Here are hex dumps of all these files:

Column 0:
0000000: 1974 7420 3720 203d 2726 2c3f 2674 203b  .tt 7  ='&,?&t ;
0000010: 2174 3335 313c 313a 3735 2c3b 2739 2d3a  !t351<1:75,;'9-:
0000020: 2031 3523 303c 2631                       15#0<&1
Column 1:
0000000: 111c 0b48 1a1a 1f06 1c11 1c0d 0d18 1a0e  ...H............
0000010: 1c01 4805 1a48 090f 0118 4848 1b48 1b0d  ..H..H....HH.H..
0000020: 001a 0c01 1b01 0d0c                      ........
Column 2:
0000000: 4906 001e 100c 0049 1b19 4710 1901 0049  I......I..G....I
0000010: 4907 1d00 0406 0449 1919 3700 000f 0049  I......I..7....I
0000020: 0045 491d 4707 0847                      .EI.G..G
Column 3:
0000000: 1253 0316 0312 0007 1607 5353 1601 161e  .S........SS....
0000010: 0010 1b1d 1a15 5f04 1b16 5307 1101 0004  ......_...S.....
0000020: 0053 1e1b 5307 0779                      .S..S..y
Column 4:
0000000: 5343 4800 544d 4545 4100 7753 4141 4445  SCH.TMEEA.wSAADE
0000010: 554c 4541 4e00 0048 4541 5800 4c45 0048  ULEAN..HEAX.LE.H
0000020: 0069 5500 6153 4c                        .iU.aSL
Column 5:
0000000: 1a1b 0c02 0c49 4911 041d 0c1d 1d1a 491d  .....II.......I.
0000010: 0a1c 491d 0c1d 080c 1b1b 4904 0c18 0808  ..I.......I.....
0000020: 0a49 0a1d 0749 10                        .I...I.
Column 6:
0000000: 1a0a 011d 1710 2b07 5a1c 5301 1616 121b  ......+.Z.S.....
0000010: 1017 381a 531b 1d01 535f 4e1a 5306 1d07  ..8.S...S_N.S...
0000020: 121b 1b1b 0a04 53                        ......S
Column 7:
0000000: 4750 004f 0049 6f00 0c00 4b45 440e 004f  GP.O.Io...KED..O
0000010: 4545 414f 5445 4445 5400 0047 5445 4400  EEAOTEDET..GTED.
0000020: 5341 0045 004f 41                        SA.E.OA
Column 8:
0000000: 1a00 0003 0304 2615 5404 1a15 5454 0210  ......&.T...TT..
0000010: 0754 071a 1c54 5454 1116 441c 1b1a 540c  .T...TTT..D...T.
0000020: 1102 0707 1c01 04                        .......
Column 9:
0000000: 0509 0d48 0100 4806 0904 0705 2d21 091b  ...H..H.....-!..
0000010: 1b09 0148 0d03 0901 100d 441c 480b 0c48  ...H......D.H..H
0000020: 460d 1d0d 0d04 18                        F......
Column 10:
0000000: 000b 1d12 1100 0a01 0b04 1245 0b45 1745  ...........E.E.E
0000010: 4b15 1611 4500 0b0b 1106 4545 151c 000c  K...E.....EE....
0000020: 4545 0645 0901 17                        EE.E...
Column 11:
0000000: 4e41 5441 4852 4600 4449 0049 4748 4957  NATAHRF.DI.IGHIW
0000010: 0050 4b4f 4c59 4100 0041 4142 4500 5453  .PKOLYA..AABE.TS
0000020: 684e 434d 5000 45                        hNCMP.E
Column 12:
0000000: 1f07 4b18 4b4b 4b00 4b05 1f18 070a 0e02  ..K.KKK.K.......
0000010: 3f07 024b 0e4b 071f 5b1e 050e 190a 0e4b  ?..K.K..[......K
0000020: 0404 0e0e 4b09 08                        ....K..
Column 13:
0000000: 451c 1145 044d 1500 0145 0d45 0c13 1111  E..E.M...E.E....
0000010: 0d1c 4501 0b16 1c0d 4216 0145 030b 170c  ..E.....B..E....
0000020: 1211 1611 0a00 0c                        .......
Column 14:
0000000: 1003 111c 591b 1500 1c0d 1c18 0a1c 0011  ....Y...........
0000010: 1c10 1c1c 1e0d 031c 0a1c 5909 1618 1417  ..........Y.....
0000020: 1c59 0a11 0b59 18                        .Y...Y.
Column 15:
0000000: 5d4b 4f40 5d47 4f0e 4d4b 0e0e 460e 0e41  ]KO@]GO.MK..F..A
0000010: 5740 565a 5a5c 470e 0e0e 5d41 5c42 470e  W@VZZ\G...]A\BG.
0000020: 5846 0e41 0e49 5a                        XF.A.IZ

You can clearly see that the columns corresponding to spaces (or the period at the end) in the key look completely different from the ones that correspond to letters.  The first column, corresponding to the uppercase T, has mostly punctuation and a few lowercase ts mixed in, while the columns corresponding to lowercase key letters contain mostly control characters plus some uppercase versions of the key letter (where the plaintext byte happened to be a space).

There's also a subtle but noticeable difference between the columns where the key byte is a space and the last one where it's a period: while both contain a lot of uppercase letters and some control characters, the last column also contains a bunch of punctuation (particularly @, [, \, ], ^ and _, which have the same sixth and seventh bits as uppercase letters in ASCII), and the control characters are mostly 0x0E (. = 0x2E, XORed with space = 0x20) rather than nulls.


Rule 30 Cellular Automaton for Cryptography

… I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure?

No. Cellular automata rules are not cryptographically secure; not even close.

Rule30 works somewhat like an LFSR… it's a cellular automata rule (think: finite state machine) having alike problems with repeating patterns (even though with different, expanding repetition — in contrast to how LFSR work), typical finite state machine behaviour, and rather short loops of repetition.

Visualizing Rule30 and the likes can show this in an more "in your face" way — where it becomes rather obvious why you wouldn't want to use "cellular automata" for things like cryptography.

Meanwhile (since the 80s) cryptographic engineering has better building blocks than those "old goodies". For similar reasons, more modern crypto algos stopped using LFSR combining constructions.

Sure… you could use Rule30 in cipher algo design - but the drawbacks and problems of working around cellular automata issues will make the whole algo more suspicable to attacks. This again will make the whole algo less optimal from a resource and certainly from a speed point of view.

Differently stated: just because you could, doesn't mean it makes sense. Especially, since things like Rule30 don't help adding security to your algo as they're not cryptographicall secure by nature… and making cellular automata rules cryptographically secure is comparable with making an LFSR cryptographically secure. It can be done, but the problems will always tend to outweight the gains from choosing such a component for cryptographic engineering purposes.

For example: when we look at the several stream cipher designs based on cellular automata since the 80s, it shows that — most of the time — even a rather simple attack with a SAT solver is already more efficient than a brute force attack. That means most of them are theoretically broken the day they are published (while practical breaks are waiting atround the corner). Especially when looking at cellular automata, such SAT solver attacks are merely the tip of an iceberg which tends to be full of problems includng timing attacks, etc.


derangements and permutations in cryptography

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$.

It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements).

It holds that $N(n,0)=\text{}!n=\begin{cases}
1                            &\text{if }n=0\\
\lfloor{{n!+1}\over e}\rfloor&\text{if }n>0\\
\end{cases}$
(that's the number of derangements of $n$ elements).

The computation made of $N(11,5)$ as $5!\cdot\text{}!(11-5)=31,800$ in the question is wrong, as noted: this is less than $!11=14,684,570$, when it should be above (but still less than $11!=39,916,800$). Two mistakes have been made:

the $m=5$ things that can be assigned without constraint among $n=11$ can be so in $n!\over(n-m)!$ ways, not $m!$ ways; fixing that, we would get ${11!\over(11-5)!}\cdot\text{}!(11-5)=14,691,600$, which is more credible;
but after first assigning $m=5$ unconstrained things, the assignments for the $n-m=6$ other things depend on how we arranged the unconstrained things (if we assigned one of the unconstrained things to an initially constrained thing, the later becomes unconstrained); therefore, the above $14,691,600$ is significantly too low.

Taking a deep breath, we can see that $N(n,m)$ can be obtained as
$$\begin{cases}
1                                    &\text{if }n=0, m=0\\
0                                    &\text{if }n=1, m=0\\
n\cdot N(n-1,n-1)                    &\text{if }n>0, m=n\\
(n-1)\cdot N(n-1,1)                  &\text{if }n>1, m=0\\
m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m<n\\
\end{cases}$$
Justifications:

when $n=0, m=0$: there's a single method to map nothing; consistency with $0!=\text{}!0=1$.
when $n=1, m=0$: there's no permutation of one thing that does not map that thing to itself; consistency with $\text{}!1=0$.
when $n>0, m=n$: we assign an unconstrained thing to an unconstrained thing (thus in $n$ possible ways), leaving $n-1$ unconstrained things; that's the classic factorial recursion.
when $n>1, m=0$: we assign a constrained thing to a constrained thing other than itself (thus in $n-1$ possible ways), leaving $n-1$ things among which $1$ became unconstrained.
when $0<m<n$: we assign an unconstrained thing, either

to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m-1$ unconstrained;
to a constrained thing (thus in $n-m$ possible ways), leaving $n-1$ things among which $m$ unconstrained including the one that became unconstrained.

I get $N(13,6)=3,597,143,040$, and $N(11,5)\equiv67\pmod{97}$.

If we don't mind that $m=n+1$ creeps in, $N(n,m)$ can also be obtained as
$$\begin{cases}
(n-1)\cdot N(n-1,1)                  &\text{if }n>0, m=0\\
m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m\le n\\
1                                    &\text{otherwise}\\
\end{cases}$$
or as
$$\begin{cases}
n\cdot N(n-1,n-1)                      &\text{if }n>0, m=n\\
m\cdot N(n-1,m)+(n-m-1)\cdot N(n-1,m+1)&\text{if }0\le m<n\\
1                                      &\text{otherwise}\\
\end{cases}$$
Justification of the new relation when $0\le m<n$: we assign a constrained thing, either

to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m$ unconstrained;
to a constrained thing other than itself (thus in $n-m-1$ possible ways), leaving $n-1$ things among which $m+1$ unconstrained including the one that became unconstrained.

Based on intuition confirmed by numerical evidence that $m\mapsto N(n,m)$ is close to exponential between $m=0$ and $m=n$, I assert that
$$N(n,m)\approx n!\cdot e^{m/n-1}$$
This approximation is by excess when $m>0$. The error made is less than $4.0\%$ for $n\ge4$; less than $1.8\%$ for $n\ge8$; less than $1.0\%$ for $n\ge14$.

More rigourously stated:
$$\forall r\in\mathbb R, 0\le r\le1\implies\lim_{n\rightarrow\infty}{n!\cdot e^{r-1}\over N(n,\lfloor r\cdot n\rfloor)}=1$$


Is this a good entropy collector and whitening technique?

The entropy of a PRNG depends on the quality and amount of "true" random noise used to initialise the PRNG and how much bits the PRNG produces before being re-initialised. A fresh PRNG might be as high quality as your entropy collection above, albeit often a different source such as CPU heat.

The method you cite will not add entropy but will spread the entropy fairly evenly within each 256 bit SHA result (Step 3 can be dropped).

If you want to know the level of actual entropy, just save a lot of results from Step 2 and check with a test suite such as NIST's statistical tests.

The key concern you should focus on is not spreading the entropy (even a non-cryptographic hash like MurmerHash will suffice*) but improving the quality and bitrate of the random noise source.

* If the random source is truly random as it should be, a cryptographic hash isn't needed. If it isn't random, a cryptographic hash reduces inferring the signal in the noise.

EDIT

Regarding Step 1 - If you want stick with keyboard/mouse for random noise input, I suggest you use an approach similar to HotBits timing.

Only the difference between two or three timings (I forget which is used to cancel clock drift) are used to create a single bit of entropy; a mouse could use pixel travel distance per fixed interval.

As the timings aren't as random as beta decay, you'll need a NIST test suite or similar to decide on how many bits you need to collect for each SHA-256 hash. Hint: It will be much more than 256 bits.


Is it possible to construct an encryption scheme for which breaking is NP complete but there nearly always exists an efficient breaking algorithm

The Merkle–Hellman knapsack cryptosystem (Wikipedia article) is the canonical example of this.  It was designed to rely on the difficulty of the subset sum problem, which is NP-complete.  However, while NP-complete means, under the P ≠ NP hypothesis, that there is no polynomial-time algorithm to guarantee a solution for every input, that doesn't mean the legitimate user can efficiently generate keys or ciphertexts for which all polynomial-time algorithms to decrypt ciphertexts or recover keys will fail with nonnegligible probability.  And it turns out that the knapsack cryptosystem is easily breakable.

Now, it is not always the case that cryptosystems with relations to NP-complete or NP-hard problems are practically breakable.  For example, the McEliece cryptosystem (Wikipedia article), whose decryption is related to the NP-hard problem of decoding general linear codes, has withstood scrutiny of decades, and modern parametrizations are not known to be breakable even with a quantum computer.

For more about P = NP and crypto, see also an earlier post I wrote on the usefulness of asymptotic cost analyses versus concrete cost analyses.  The brief summary is that even if P = NP, that fact may nevertheless have no practical consequences for cryptography.


Generating passwords using Password-Based Key Derivation Function

Like I wrote in the comment, the method here is pretty similar. The differences:

Rather than deriving each site password directly from the password, I recommended deriving a single master secret using a password hash and then deriving the site passwords from that using another KDF.
You are truncating the PBKDF2 output to 64 bits.
You define the method of turning the hash into a password explicitly.

Regarding the first, using a single master secret allows you to derive it once and then quickly derive multiple site-specific passwords. (It also uses a known-unique salt, which is nice.) This is not necessary, but does mean you can perhaps use more iterations in some cases.
Truncating to 64 bits should be fine, but is not necessary if you can copy-paste a stronger one. (If your password is complex enough brute forcing the 64-bit hash or the derived password will be faster than attacking the master password.)
The last is problematic. As discussed in the comments to the question I linked above, each site has their own requirements on the password so any static algorithm like that is unlikely to work for all. That is not a security issue, however: as long as you do not drop information from the hash further, any method of encoding it as a password will be fine.

However I'm not sure about if it is OK to use a such simple salt. Like I once heard that salts should be unpredictable...

No, salts only have to be unique. However, if you ever need to change the site password (e.g. their database is stolen and they require new ones), you may need to add something to the site name. Also, theoretically someone else who used the same method could be using the same salt, allowing a faster attack. (Adding e.g. your email address could solve this.)

Other than the downsides I mentioned in the other question (quoted below) there is the question of which password hash to use. PBKDF2 is not exactly the state of the art and using e.g. scrypt might give you a larger advantage over potential adversaries.

If you go this route you are putting all your eggs in one basket. If you forget the master password, you lose all the derived ones. If someone guesses it, they can derive all the others.
You would probably be better off just using a password manager that prevents guessing attacks. Otherwise the master must be very strong. A password manager generates random site passwords that leak no information about the master.


Why does RSASSA-PSS produce different signature each time even if I use same salt and same message?

You aren't using the same salt.

The randomness is introduced with the salt: it is generated randomly. The input to the MGF is calculated from the hash and the salt. Thus, if you sign the same message twice, you get different signatures, because the salt is different each time. For the details, see PKCS#1 (RFC 8017) §9.1.1.

There are only two ways to use the same salt with any sane implementation of RSA-PSS.

If you choose a salt length of 0, then the salt is always the same, and PSS becomes deterministic.
If you can set the state of the RNG, using the same message with the same RNG state will result in the same signature.

Otherwise, if the salt length is $n$, there are $2^{8n}$ possible salts, and the probability that two given signatures would use the same salt is $2^{-8n}$, which is negligible (unless $n$ is very small, but in practice it isn't).

The default salt length is the length of the hash in most implementations. More precisely, most implementations use the maximum possible salt length, which is usually the hash length but can be shorter when using a large hash with a small key (the salt plus the hash plus two bytes must fit in the key size in bytes, so a 1024-bit key with SHA-512 only leaves room for a 30-byte salt). The general rationale is that if you wanted your signature to be deterministic, you'd use PKCS#1v1.5; and if you're going to use a salt, the cost of making it longer is negligible, so you might as well make it maximum-length.

On why you'd want a signature algorithm to be non-deterministic, see Why use randomness in digital signature algorithms? (which mostly covers RSA-PSS). On the salt length in RSA-PSS, see RSA-PSS salt size


How many hex digits do I need to compare when manually checking hash
  functions?

If you actually want the full security guarantees of the hash function to apply: all of them.

  I usually just look at the first/last 5 or 6 hex digits and call it
  good enough.

This effectively reduces the security of the hash function to that of one that only outputs 10-12 hex digits, a.k.a. 40-48 bit, for which we can easily find collisions in about $2^{24}$ evaluations which is easily doable.

  what are the chances of a "near collision"? E.g. only one or two hex
  digits are different.

As discussed in this answer the probability for at most $t$ bits difference between two hashes with $n$ bit output-length is $$p_t=\sum^t_{k=0}{n\choose k}2^{-n}$$ which means you need about $\sqrt{1/p_t}$ evaluations to come up with a desired near-collision. Strategies to finding these values can be found in this answer (including low-memory approaches).


Deviation from CCM specification - security impact?

The reason why $S_0$ is not used by the encryption is because it is already used by the final calculation of the authentication tag:

  The authentication value U is computed by encrypting T with the key
     stream block S_0 and truncating it to the desired length.

 U := T XOR first-M-bytes( S_0 )

So yeah, the protocol simply uses the leftover bits of the first block of the key stream. These should be unpredictable to the adversary, so I don't see any issue using them.

It obviously is slightly more efficient when it comes to the amount of block operations for some messages. This makes most sense for small messages on limited machines where the block operation takes more time than all the rest of the calculations and 16 byte alignment doesn't matter. If the messages are all of a specific size then it might remove one block operation for each message.

All in all, using bits from the keystream that are otherwise not used is fine. For me, I would wonder if it is worth deviating from a standard for it, but that isn't a question of security but of interoperability. You'd have to start by writing or adjusting an algorithm, so that in itself may be enough reason to discard it.

It of course also assumes that the tag size is smaller than 128 bits, and undercutting the tag size in itself is dangerous as well (although it doesn't have the same security implications as for e.g. GCM). If the tag size is 128 bits then the entire block is used and the scheme is just normal CCM again.


Is my XTEA encryption key safe if I publish my firmware both as plain text and encrypted?

What you are describing is called a known plaintext attack. Modern ciphers should be even secure if the adversary chooses the plaintext to encrypt. That would be called a chosen plaintext attack (CPA), and a cipher that protects against is called CPA-secure. Actually, it goes even a bit further than that: IND_CPA means that the ciphertext is indistinguishable from random even if the adversary choses the plaintext.

Basically you can publish any amount of pairs and still be secure. This of course isn't the case anymore if the cipher gets broken. The cipher is completely broken if a key can be retrieved by a CPA attack. Fortunately no such attack is known against XTEA. But note that there are no ciphers that can be proven to be secure.

However, XTEA is a block cipher. A block cipher isn't a generic cipher by itself. It needs a mode of operation to turn into a real cipher. This mode of operation should be initialized using an initialization vector. Without a unique or random initialization vector the ciphertext may leak information about the plaintext. For instance, if you would encrypt two different versions of the same firmware you could see where changes were made.


Public signature of challenges as authentication

What issues is there with this approach?

There are both theoretical and practical concerns with this kind of solution.
First, it is generally not seen as a good idea these days to just sign whatever the somebody else handed you, especially if you also use the signing key in other contexts. This is to prevent an attacker from sending you a "challenge" like "you, lurscher, authorize a wire transfer to me, SEJPM, with a value of 10k USD" and then me presenting this to your bank. There are ways to fix this problem though.
The more practical concerns though are usually more important in this context. Namely: Most servers simply don't have have a public key they are sure is associated with a given user. And if they do, how long do you think it will take until users start complaining or loosing their private keys? Using good old static authenticators (like passwords) is simpler. Additionally, from a server's perspective there is typically very little extra security gained from such an involved authentication strategy. You already assuming a secure channel after all and I can't think of a scenario right now where standard password transmission over HTTPS with server-side (basic) hashing would be significantly more secure than a public-key based solution (in a web context).
Outside of web contexts, yes, authenticating both parties with a public key is a viable strategy which is why TLS has built-in support to do so.


Short answer: no you can't, MD5 is not that broken.

Long answer: if you really need to do that, a laptop i5 is able to try 5 millions of MD5 hashes per second; on average you will have to try 2^32 ~ 4300 millions hashes, so that it will be a matter of minutes on any decent remotely-modern CPU.


Computing $g^y\bmod p$ from $g^{y^2}\bmod p$ if Diffie-Hellman is compromised?

Then is computing $g^z\bmod p$ from $g^{z^2}\bmod p$ doable in polynomial time?

If we assume that we know the order $q$ of $g$, and that it is prime, then yes, it is feasible.
Then, we can treat members of this subgroup as an abstract group, where each member is $g^a$ for some $a$.  Within this abstract group, we can perform multiplication with the Oracle, that is, given $g^a$ and $g^b$, we can compute $g^{ab \bmod q}$.  By extension, we can perform exponentiation in polynomial time, that is, given $g^a$ and an integer $c$, we can compute $g^{a^c \bmod q}$.  And, we can compute the additive inverse (given $g^a$, we can compute $g^{-a \bmod q}$)
We further have an equality operator on this group, that is, given $g^a$ and $g^b$, we can determine whether $a \equiv b \pmod q$).
These operations are sufficient to implement the Tonelli-Shanks algorithm within the abstract group; this allows us to compute square-roots in polynomial time [1], and specifically, given $g^{z^2}$, to recover the two square root elements $g^z$ and $g^{-z}$

[1]: Probabilistic polynomial time if $q \equiv 1 \pmod 4$; however the probabilistic step is to find a quadratic nonresidue, and that needs to be done only once for a specific group.


Can someone explain to me the concept of hashing versus the concept of encryption?

The important difference is that encryption is intended to be undone, hashing isn't. Let's say I have a secret password called "pass001." If encrypted, pass001 would be scrambled with a key to be something unrecognizable like "a8d89sI." Using the exact same key, "a8d89sI" can be reverted back to pass001. Hashing scrambles the secret password in much the same way, but there is no key involved and there is generally no way to turn the computed hash back into "pass001." Why might this be useful? Assume you stored password hashes in your database. If a hacker were to steal the contents, then he would be left with hashes that he can't do anything with. Not even the owner of the database can see the original password. When a user logs in, the password they enter is hashed on the spot and this hash is compared to the hash stored in the database to check if they put in the right password. If they did, both the calculated hashes should be the same. Hashes are used for many things, but in this case, it's just an extra layer of security.


That the left hand side implies the right hand side is easy, it follows from the following fact:

$$x\equiv y \mod{pq}\ \Leftrightarrow pq \mbox{ divides }x-y \Rightarrow p \mbox{ divides } x-y \mbox{ and } q \mbox{ divides }x-y$$

And so $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$

Now, the point here is argument can be "reversed" in the case that $p$ and $q$ are relatively primes (and actually they are since we are assuming that they are different, if they're not, we can't obtain the result), it is, if $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$, then p $\mbox{ divides } x-y$ and $q \mbox{ divides }x-y$, and as $p$ and $q$ are relatively prime (this is a well known theorem in number theory) we have that $pq$ divides $x-y$, thus $x\equiv y \mod{pq}$.

This is the general version of theorem I've wrote before:

Let $a,b,n\in \mathbb{Z}$ and suppose that $a$ divides $n$ and $b$ divides $n$, then $ab$ divides $n\cdot \mbox{gcd}(a,b)$. This, in the case that $a,b$ are relatively prime, gives the result i'm reffering to (because in that case $\mbox{gcd}(a,b)=1$).

Here's a small proof of this fact. Let $n=as$ and $n=bt$, write $\mbox{gcd}(a,b)=g$, we know that there exists $x,y$ integers such that $ax+by=g$ (see this post), then, multiplying this expression by $n$, we obtain $n(ax)+n(by)=ng$, replacing adequately, we have $(bt)(ax)+(as)(by)=ng$ and rearranging, we finally obtain $(ab)(xt+ys)=ng$ so $ab$ divides $ng=n\cdot \mbox{gcd}(a,b)$.


Are coprocessors (Intel Phi) a threat for modern key stretching functions?

The key idea of memory-hard functions like scrypt and Argon2, as I understand them, is to analyze the cost to the attacker in terms of a time-area product.  Time is how much time the attacker spends.  Area is how much silicon they use for the attack.  The attacker is going to allocate a given area, but once that amount is fixed:

More cores means less memory dedicated to each core;
More memory dedicated to each core means fewer cores.

This sort of analysis should still apply to the coprocessors you bring up.  Since they offer lots of memory per core, this must inevitably come at the cost of fewer cores than could otherwise be put in the same area of silicon.  But if the functions' time-area product cost analysis is correct, the attacker should be unable to gain an advantage this way; the speed each core gains from its generous memory allocation should come at a corresponding loss in parallelism.

Note in passing that:

Memory complexity implies time complexity (using memory requires time).  So algorithms that use a lot of memory are by necessity going to be (at least) proportionately slow.
Argon2 supports tuning the memory and time cost more or less independently.  I.e., for a given amount of memory, we can always raise the time cost further to thwart a high-memory but low-parallelism attacker.


Does AES encryption work like a padlock or like a safe?

Mode Dependency
Whether or not the order of AES encryptions matters depends on its mode of operation. I'll get to your case of GCM (Galois Counter Mode presently).
"Safe-like" modes
For modes such as ECB, CBC, or PFB where the plaintext contributes to the input for the actual primitive, then the order does matter.
"Padlock-like" modes
For some streaming modes such as CTR and OFB then the order does not matter as the XOR of streams of bits can be done in any order and so if the streams are independent of the plaintext things can be done in any order.
ETA: @fgrieu points out that such modes use an additional parameter known as an Initialisation Vector or IV and that I have implicitly assumed that these are not encrypted during the multiple encryption processes. This assumption is not consistent with implementations that simply pre-pend the IV to the ciphertext in the cryptogram, nor certain theoretical constructs. It would be more accurate to say that if $p$ is encrypted with key, IV pairs $(k_1,IV_1), (k_2,IV_2),\ldots, (k_n,IV_n)$ then the padlock property applies.
GCM Mode
Your case of GCM is interesting as it provides two cryptographic functions: confidentiality and authentication. The confidentiality part is unaffected by ordering as it is a stream like CTR that is independent of plaintext. Thus you can recover $p$ by decrypting in any order (assuming that no-one modifies any ciphertext outside of decryption). However, the authentication part does depend on the ordering and so the final decryptions and intermediate decryptions should throw up error warnings if they are done in anything other than the reverse order. Again we must specifically exclude the IVs used in GCM from encryption for the padlock property.
If you intend to ignore these authentication tags (which is always poor practice), you would be better served by using an unauthenticated method such as CTR and finding a suitable, non-integrated authentication scheme for your application. This will shorten the ciphertext as each GCM encryption adds its own authentication tag which lengthens the final message by $n$ blocks.
Additional Commentary
Generally speaking, applying multiple layers of encryption is not something that is recommended as meet-in-the-middle attacks means that the overall security is not additive. I suspect that you might be considering single-encryptor-group-decryptor scenarios and you might like to read up on ideas such as Shamir's Secret Sharing.


Recovery Passphrase Collission for BIP-39 and BIP-44

128-bit entropy simply means that we have $2^{128}$ different values to search, which is similar to 128-bit security. For a single target that is impossible since even the collaborative powers of Bitcoin Miners can reach $\approx 2^{92}$ in a year. Therefore one needs $2^{35}$ years to find the correct password. The iteration of PBKDF2 is 2048 so, we need to multiply $2^{35}$ with $2^{11}$ that makes $2^{46}$ years if we assume that SHA2d running time is equal to PBKDF2.
In the case of finding multi-password attack, with parallel versions of Oechslin's rainbow tables, the expected cost of finding a password from $t$ targets is $2^{128}/t$. Now assume that you have a billion of targets. Then, you will be able to find the first password much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This can be achievable with supercomputers.
Conclusion: Using 128-bit entropy is not secure in multi-target attack case. The users should concentrate on password settings with 256-bit entropy.

Note 1: The title includes the word collision, however, a collision has nothing to do with finding a password of a user. A collision is finding two pairs of passwords such that after PBKDF2 is applied the result will be the same. This has cost $2^{64}$ with 50% probability of success. The pre-image attack is the attack for passwords with a cost of $2^{128}$ is the setup of the question.
Note 2: A detailed entropy calculations of Bip39 in this answer.


Can I hash a secret key and used the hash as key ID?

I would do it a little differently so there is less of a relationship between the ID and the key

Encrypt a block of all 0s with the key; $X$ = $E_k(0_{128})$

Hash X; $H$ = SHA256$(X)$

Truncate the hash to 32 bits (8 hex characters)

Encrypting a block of 0s and truncating is generally how a key check value is generated, as block ciphers are designed to resist key recovery, the intermediate hash step is there for extra security, so you are not exposing a known ciphertext value.

I would not consider a direct key hash safe, some software may use that internally, and you do not want that exposed


How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$

Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$?
The necessary condition is that $k\mid n$ which means $n=km$ for some integer $m$.
Now Let $\bf A$ be $km \times km$ binary matrix. The first step is that to consider the matrix $\bf A$ as a block binary matrix as follows where ${\bf B}_{i,j}$, $1\leq i,j \leq m$ are $k \times k$ binary matrices.
$$
{\bf A}=
\left(
\begin{array}{c|c|c|c}
{\bf B}_{1,1} & {\bf B}_{1,2} & \cdots & {\bf B}_{1,m} \\ \hline
{\bf B}_{2,1} & {\bf B}_{2,2} & \cdots & {\bf B}_{2,m} \\\hline
\vdots & \vdots & \cdots & \vdots \\\hline
{\bf B}_{m,1} & {\bf B}_{m,2} & \cdots & {\bf B}_{m,m}
\end{array}
\right).
$$
Next, we should consider all square sub-matrices of the block matrix $\bf A$ and check that whether these sub-matrices are non-singular over $\mathbb{F}_2$? For example one of the square sub-matrices of $\bf A$ is as follows. The matrix $\bf C$ is an $2k \times 2k$ binary matrix and we should check its singularity over $\mathbb{F}_2$.
$$
{\bf C}=
\left(
\begin{array}{}
{\bf B}_{1,1} & {\bf B}_{1,2} \\
{\bf B}_{2,1} & {\bf B}_{2,2}.
\end{array}
\right).
$$
Note that if all square sub matrices of the block matrix $\bf A$ are non-singular over $\mathbb{F}_2$, then we say $\bf A$ is an MDS matrix over $k$-bit inputs or $k$-bit words.
Maybe you ask this question: Is $\bf A$ an MDS matrix over $\mathbb{F}_{2^k}$ for some irreducible polynomial of degree $k$ over $\mathbb{F}_2$? The answer is yes when $\bf A$ is obtained from an $m \times m$ matrix such as $\bf M$ provided that the entries of $\bf M$ belong to $\mathbb{F}_{2^k}$. Let me make an example to learn it more clearly.
Consider the following $4\times 4$ matrix where the entries of $\bf M$ belong $\mathbb{F}_{2^8}$ such that this finite field is constructed from the irreducible polynomial $f(x)={x}^{8}+{x}^{4}+{x}^{3}+x+1$  over $\mathbb{F}_2$ (some users of this forum maybe say it is the MDS matrix of AES, but imagine we do not know this fact and we want to check it!).
$$
\scriptsize{
 {\bf M}=
 \left(
 \begin {array}{cccc}
 \alpha&\alpha+1&1&1\\
 1&\alpha&\alpha+1&1\\
 1&1&\alpha&\alpha+1\\
 \alpha+1&1&1&\alpha
 \end {array}
 \right).}
$$
Now we obtain a $8 \times 8$ binary matrix such that its characteristic polynomial over $\mathbb{F}_2$ is equal to $f(x)$ such as the following one
$$
\scriptsize{
{\bf N}=
 \left(
 \begin {array}{cccccccc}
 0&0&0&0&0&1&0&0\\
 0&0&0&0&1&0&0&0\\
 0&0&0&0&0&0&1&0\\
 1&0&0&0&0&0&1&0\\
 0&1&0&0&0&0&0&1\\
 0&1&0&0&0&0&0&0\\
 0&0&0&1&0&0&0&0\\
 1&0&1&0&0&0&0&0
 \end {array}
 \right).}
$$
Next, by applying $\bf N$ we transform $\bf M$ to a $32 \times 32$ binary matrix, denoted $\bf A$, as follows. Let the $(i,j)$ entry of $\bf M$ be $\sum_{i=0}^{7}b_i\alpha^i$ where $b_i$'s are binary numbers. Now the $(i,j)$ entry of the block matrix $\bf A$ is equal to $\sum_{i=0}^{7}b_i{\bf N}^i$ in modulo 2. Therefore, the block matrix $\bf A$ is given by
$$
\scriptsize{
\left(
 \begin {array}{cccccccc|cccccccc|cccccccc|cccccccc}
 0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\
 0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\
 0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0\\
 1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0\\
 0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0\\
 0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\
 0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0\\
 1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline
 1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0\\
 0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0\\
 0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0\\
 0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0\\
 0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0\\
 0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\
 0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0\\
 0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline
 1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0\\
 0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0\\
 0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0\\
 0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0\\
 0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1\\
 0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0\\
 0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0\\
 0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1\\ \hline
 1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\
 0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\
 0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0\\
 1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0\\
 0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1\\
 0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0\\
 0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0\\
 1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0
\end {array}
\right).}
$$
The final step is that we check the singularity of all square sub-matrices of the block matrix $\bf A$ over $\mathbb{F}_2$ (the number of these sub-matrices are ${2n\choose n}-1$, for example for AES is 69).
Maybe you ask this question what is the advantages of this scenario. One answer is that the computation over $\mathbb{F}_2$ is more faster than the finite fields.
I hope you find this answer helpful.


Can TLS be used simply to exchange keys using the handshake protocol?

1 - Handshake protocol: uses public-key cryptography (ECDH, DH) to establish a shared secret between the client and server.

The handshake protocol is also used to establish a cipher suite, some configuration parameters and (usually) to perform entity authentication, amongst others.

So, can I simply complete the handshake protocol and then drop the connection?

The shared secret is only used to establish the session keys and might be destroyed after they've been established.
If you drop the connection the shared key should be destroyed by the implementation as well.
The session keys are TLS specific, and they are often not available from an TLS API for that reason.

So you could use part of the TLS handshake to establish a shared secret, but you'd go outside protocol specs if you use the session keys for anything else. If you use a TLS implementation you'd probably need to alter it to get to the right key material.
In your case it might be better to simply lift the relevant bits from the protocol and use that to define your own. Of course that would go against not using DIY cryptography, but I guess you've gone over that dangerous threshold already...


Does RSA padding have to be unpredictable if the payload is?

From what I understand, you consider a scenario in which a fixed, random-looking message $M$ is sent to multiple recipients, encrypted using RSA with some padding (this is called the "broadcast RSA" setting).

Moreover, you consider affine paddings, in the sense that you apply the RSA function to an element of $\mathbb{Z}_N$ of the form $a_i M + b_i$ for some values $a_i, b_i$ depending on the recipient which may be known in part or in full by the adversary (in fact, we even have $a_i = 1$ in the cases you consider, but that doesn't really matter).

In that case, expanding a bit on fgrieu's answer:

No, it is not OK to use a public deterministic padding that depends on the recipient, even if the padded message is as long as the modulus. This type of padding is broken in the broadcast setting by a generalization due to Håstad of the simple CRT attack alluded to by fgrieu.
For the same reason, a predictable padding function will not do, nor indeed any affine padding where the values $a_i, b_i$ are known by the adversary.
Even using such a padding where the $b_i$'s are randomized can be dangerous. For example, a padding of the form $R_i \| M$ (with $R_i$ chosen at random for each recipient and long enough so that the padded message is as long as the modulus) can be attacked in the broadcast setting if $M$ is relatively long: see this paper (the attack is admittedly rather theoretical, but still).
This survey on RSA attacks by Boneh is over 10 years old already, but always good reading (you're especially interested in §4).

Generally speaking, I wouldn't recommend using an affine or polynomial padding function for any new application except for interoperability reasons; and I would especially advise against using a custom affine padding that "looks strong enough" (unless you want to make cryptanalysts happy by providing them with a fresh new target :-).

A better idea (which is essentially what Thomas Pornin suggested in the earlier discussion) is using RSA-KEM (RFC 5990): for each recipient, pick a random element $R_i$ in $\mathbb{Z}_N$, and send $C_i = R_i^e \mod N$ to the $i$-th recipient, together with the encryption of $M$ (with your favorite block cipher) under a key derived from $R_i$.

Other options include paddings like RSA-OAEP (part of PKCS#1 v2.1).


Curve parameter for hyperelliptic curve cryptography?

There is no database of hyperelliptic curve parameters because their use is not sufficiently popular. This is because the topic is too new and the advantage of faster calculations doesn't outweigh the disadvantages of novelty and lack of reference implementations.

Another aspect is that with modern computers and algorithms, anyone seriously looking at implementing hyperelliptic curve cryptography can easily generate their own parameters. Contrast this with the early days of elliptic curve cryptography where finding (let's say) a twist-secure prime-order curve of a decent size was a significant computational task.

As soon as hyperelliptic cryptography becomes popular then there will be databases of parameters to ensure interoperability between different implementations. However, I don't anticipate this will happen for a long time because groups of points on elliptic curves are a sufficiently good improvement over groups of integers for cryptographic purposes.

The slides you link to and their paper on the eprint archive are excellent and you should be able to use their parameters with some confidence.


Why is it that in DSA, the order of the subgroup, $q$, is chosen such that it divides $p - 1$?

As was noted in the comments the reason for $q$ having to divide $p-1$ is Lagrange's theorem:

  Lagrange's theorem [...], states that
  for any finite group $G$, the order (number of elements) of every
  subgroup $H$ of $G$ divides the order of $G$.

In the case of DSA we are working in subgroups of $\mathbb F_p$ (which has order $p-1$). By Lagrange's theorem every subgroup has to have an order $q$ such that $q$ divides $p-1$.


Successful Cryptanalysis Research/Attacks on Zero-Knowledge Proofs?

For most symmetric cryptosystems, such as AES, the best way to study their security is to design various types of attacks, and to analyze the resistance of the primitive to these attacks. With zero-knowledge proofs, things are in general a bit different:

Zero-knowledge proofs are, in some sense, a "higher level" primitive, which means that they can be (and are, in general) constructed from other primitives.
Unlike symmetric cryptosystems, where the number of "standard primitives" is relatively small, there are hundreds of proposals for zero-knowledge proofs. This means that getting confidence in their security using cryptanalysis would require designing attacks for hundreds of different, non-standardized (and not much used in practice) primitives. That would be kind of a waste of effort.

For the above reasons, the usual (and best) approach to study the security of zero-knowledge proofs is through provable security. Usually, this is done by reducing the security properties of the zero-knowledge proof to the underlying lower level primitive it was built from. This way, cryptanalysts can simply focus on this underlying primitive to give us confidence in the security of the proof. Roughly, the zero-knowledge proofs we know of belong to four categories:

Some have unconditional security. This means that we can prove that they satisfy completeness, soundness, and zero-knowledge, without making any assumption. This is the case e.g. for the standard proof for graph isomorphism, or for the famous Schnorr protocol for knowledge of a discrete logarithm (which only satisfies honest-verifier zero-knowledge). For these proofs, no cryptanalysis is needed.
Some can be reduced to generic assumptions. For examples, the general solution to zero-knowledge proofs for NP from the seminal paper of Goldwasser, Micali, and Rackoff, can be based on any one-way function. This means, in particular, that we can build a proof for any NP statement, whose security (here, soundness is unconditional and zero-knowledge is computational, but we can also get the reverse) would reduce to the assumption that AES is secure. Hence, we can use all cryptanalytic efforts on AES (or SHA3, or any symmetric primitive you can think of) to our advantage when constructing a ZK proof.
Some proofs reduce to specific, well known assumptions. This is usually the case for more "advanced" zero-knowledge proofs. For example, Jen Groth's sublinear zero-knowledge arguments, which allow to prove statements from linear algebra with communication $O(\sqrt{N})$ ($N$ is the size of the statement), is secure under the discrete logarithm assumption. This means that cryptanalytic efforts can focus on algorithms for solving the discrete logarithms, if we want to study the security of these protocols.
Finally, some recent zero-knowledge proofs have more ad-hoc underlying assumptions. This is in general the case of zk-SNARKs, where we give up the reduction to standard and well-known assumptions, in exchange for extreme efficiency (i.e., the proof is non-interactive and of constant size). For these "extreme" proofs, it would make sense to have a specific cryptanalytic research, but as the area is still very young, there are not much results in this direction at the moment.


Preimage resistance hash in digital signature

I'm having a hard time parsing your question.

If C can compute pre-images on $H$, then he can forge digital signatures from Bob. All C needs is one signature from Bob.

Bob signs message $m$, the signature is $S={H(m)}^d\bmod n$. All C needs to do is find an $m'$ where $H(m)=H(m')$. The forged message and signature will be $m'$ and the original $S$.


That would be literally $P(a, b)$, for some multivariate polynomial $P(X,Y)$.

Of course, in that case, $P(a,b)\leq |P(a, b)|\leq Q(a, b)$ for some polynomial $Q$, where all coefficients of $Q$ are positive, and then $Q(a, b)\leq Q(\max(a,b), \max(a, b))=R(\max(a,b))$ for some univariate polynomial $R$, where $R(X)=Q(X,X)$.

Conversely, $R(\max(a,b))$ for some polynomial $R$ with nonnegative coefficients is bounded by $R(a+b)$, so this is $P(a,b)$ where $P(X,Y)=R(X+Y)$.


Can you make a hash out of a stream cipher?

A Pseudo Random Generator (PRG) and a hash function are both Pseudo Random Functions (PRFs), but they have different security considerations. (At least, historically they do. Moving forward some of them may be more closely aligned.) Due to this, building a hash from an existing PRG designed under older security constraints probably isn't a good idea for the intuitive construction of using the plaintext as the key to the PRG and the PRG output as the hash. See this nice summary: Why stream ciphers shouldn’t be used for hashing.


What you're looking for is hard-to-factor numbers where no one knows the factorization.

One approach to do this is to use the larger numbers in the RSA Factoring Challenge.  These are composite numbers selected by RSA Laboratories, in an attempt to encourage research on factorization methods.  As such, they went to great lengths to make sure that no one knew the factorization (including destroying the PC that generated the factors afterwards).

While the smaller numbers on the list have been factored, the larger ones (including RSA2048) have not.

I believe that this would address the problem you are attempting to solve.


Upper bounds on difference of RSA primes

Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| \le \frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.

Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^{\frac12}$.


Primitive polynomials and irreducible polynomials?

The definition of a primitive polynomial $P$ is that it is an irreducible polynomial with an extra condition, which is that $X$ is a generator of the whole group of non-zero polynomials modulo $P$.

To clarify things:

We consider a finite field $K$ (for instance, $K$ may be the integers modulo a given prime $q$). $K[X]$ is the ring of polynomials with coefficients in $K$. Each polynomial has a degree, which is the largest index of non-zero coefficient; for instance, $X^2+1$ has degree $2$. By convention, we will say that the zero polynomial ($P = 0$) has degree $-1$; other constant polynomials ($P = a$ for some constant $a \neq 0$) have degree $0$.

We can define an Euclidean division of polynomials, in which, given two polynomials $A$ and $B$, such that $B$ is not zero, one can find two polynomials $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ is strictly less than the degree of $B$. Moreover, this decomposition is unique: for given $A$ and $B$, there is a unique pair $(Q,R)$ that works. The remainder $R$ is also known as "$A$ modulo $B$". If $R = 0$, then $A$ is said to be a multiple of $B$.

An irreducible polynomial $P$ is one such that it is the multiple of no other polynomial whose degree is less than the degree of $P$, but more than $0$. For instance, over field $\mathbb{Z}_2$, the polynomial $X^2+X+1$ is irreducible; but $X^2+X$ is not, since it is the product of $X$ with $X+1$. (Note that irreducibility depends on the base field; $X^2+1$ is irreducible in $\mathbb{R}[X]$, not in $\mathbb{C}[X]$.)

Given a polynomial $P$ of degree $n > 0$, we can consider $K[X]/P$, which is the ring of polynomials modulo $P$: after all additions or multiplications, we reduce the result modulo $P$. This defines a ring structure, and contains all polynomials of $K[X]$ whose degree is strictly lower than the degree of $P$ (i.e. polynomials of degree $0$ to $n-1$, inclusive). If $K$ contains $q$ elements, then $K[X]/P$ contains $q^n$ elements.

It so happens that, when $P$ is irreducible, then $K[X]/P$ is itself a field. Non-zero polynomials in $K[X]/P$ are then a multiplicative group, of size $q^n-1$.

Consider, then, the subgroup generated by $X$ (the polynomial of degree $1$ whose coefficient of index $1$ is $1$, and coefficient of index $0$ is $0$). You take $X$, $X^2 \pmod P$, $X^3 \pmod P$, and so on. At one point, you will get back to $1$. The order of $X$ modulo $P$ is the smallest $k > 0$ such that $X^k = 1 \pmod P$. Since all these $X^j$ form a multiplicative group, it follows that $k$ is a divisor of $q^n-1$.

When $k$ is equal to $q^n-1$, then the polynomial $P$ is said to be primitive. This means that by computing the various $X^j$ modulo $P$, you end up covering all non-zero polynomials modulo $P$.

All primitive polynomials are irreducible, because we simply defined them that way: to be primitive, a polynomial must first be irreducible. However, not all irreducible polynomials are primitive. For instance, if we work with $K = \mathbb{Z}_2$ (the field with two elements, $0$ and $1$), then polynomial $P = X^8+X^4+X^3+X+1$ is irreducible, but not primitive (there are $255 = 2^8-1$ elements modulo $P$; but the subgroup generated by $X$ only contains $51$ of them).

Primitive polynomials are mostly relevant for linear feedback shift registers. It can be shown that the contents of a LFSR of size $n$ bits can be interpreted as a polynomial in $\mathbb{Z}_2[X]/P$ for a given polynomial $P$ of degree $n$, that depends on the positions of the feedback bits of the LFSR. Shifting the LFSR by $1$ bit then corresponds to multiplying the contents by $X$. Therefore, the period of the LFSR (number of shifts until reaching back the starting state) is maximal ($2^n-1$) only when $P$ is primitive.

LFSR are "old crypto", back from a time when that notion of period was felt to be really important (when you hear somebody talk of "the cryptoperiod", you know that he is doing cryptography from the 1960s, and he missed out the last 50 years of research in cryptography). Nowadays, LFSR and primitive polynomials are less relevant. Irreducible polynomials, however, are necessary to define field extensions. The degree-8 polynomial shown above, which is irreducible but not primitive, is used in the definition of the AES S-Box.


It is possible to view DSA/ECDSA as an identification scheme (like Schnorr) but with a different variant of Fiat-Shamir. This gives the intuition that you are perhaps looking for. I will include an excerpt from Intro to Modern Cryptography 2nd edition (Section 12.5.2) which gives this explanation:

Begin Excerpt -- Section 12.5.2 DSA and ECDSA

The Digital Signature Algorithm (DSA)
and Elliptic Curve Digital Signature Algorithm
(ECDSA) are based on the discrete-logarithm problem in different
classes of groups.
They have been around in some form since 1991, and
are both included in the current Digital Signature Standard (DSS)
issued by NIST.

Both schemes follow a common template and can be viewed as being constructed
from an underlying identification scheme
(see the previous section).
Let $ \mathbb{G}$ be a cyclic group of prime order $q$ with generator $g$.
Consider
the following identification scheme in which the prover's
private key is $x$ and public key is $( \mathbb{G}, q, g, y)$ with $y=g^x$:

The prover chooses uniform $k \in \mathbb{Z}_{q}^*$ and sends
$I:=g^k$.
The verifier chooses and sends uniform $\alpha, r \in \mathbb{Z}_{q}$ as the
challenge.
The prover sends $s:=[k^{-1} \cdot (\alpha+xr) \bmod q]$ as the
response.
The verifier accepts if $s\neq 0$ and $g^{\alpha s^{-1}} \!\cdot
    y^{r s^{-1}}=I$.

Note $s \neq 0$ unless $\alpha=-xr \bmod q$, which occurs with negligible
probability. Assuming $s \neq 0$, the inverse $s^{-1} \bmod q$ exists and
$$
g^{\alpha s^{-1}} \! \cdot y^{r s^{-1}}
 = g^{\alpha s^{-1}} \! \cdot g^{xrs^{-1}}
  = g^{(\alpha+xr) \cdot s^{-1}}
   = g^{(\alpha+xr) \cdot k \cdot (\alpha+xr)^{-1}} = I.
$$
We thus see that correctness holds with all but negligible probability.

One can show that this identification scheme is secure if the discrete-logarithm
problem is hard in the group. We merely sketch the argument, assuming
familiarity with the results of the previous section (i.e., Schnorr and identification schemes).
First of all, transcripts of honest executions can be simulated:
to do so, simply choose uniform $\alpha, r \in \mathbb{Z}_{q}$
and $s \in \mathbb{Z}_{q}^*$, and then set $I:=g^{\alpha s^{-1}} \!\cdot y^{r s^{-1}}$.
(This no longer gives a perfect simulation, but it is close enough.)
Moreover, if an attacker outputs an initial message $I$ for which it can give
correct responses $s_1, s_2 \in \mathbb{Z}_{q}^*$ to distinct challenges $(\alpha, r_1),
(\alpha, r_2)$ then
$$
g^{\alpha s_1^{-1}} \!\cdot y^{r_1 s_1^{-1}} = I = g^{\alpha s_2^{-1}} \!\cdot y^{r_2 s_2^{-1}},
$$
and so $g^{\alpha (s_1^{-1} - s_2^{-1})} = h^{r_1s_1^{-1} - r_2s_2^{-1}}$ and
$\log_g h$ can be computed as in the previous section. The same holds if the attacker
gives correct responses to
distinct challenges $(\alpha_1, r), (\alpha_2, r)$.

The DSA/ECDSA signature schemes are constructed by ``collapsing'' the above identification
scheme into a non-interactive algorithm run by the signer. In contrast
to the Fiat--Shamir transform, however, the transformation here is carried out
as follows:

Set $\alpha:=H(m)$, where $m$ is the message being signed and $H$ is
a cryptographic hash function.
Set $r:=F(I)$ for a (specified) function $F: \mathbb{G}\rightarrow
   \mathbb{Z}_{q}$. Here, $F$ is a ``simple'' function that is not
intended to  act like a random oracle.

The function $F$ depends on the group $ \mathbb{G}$, which in turn depends on the scheme.
In DSA,
$ \mathbb{G}$ is taken to be an order-$q$ subgroup of $\mathbb{Z}_{p}^*$, for $p$ prime, and
$F(I) =[I \bmod q]$.
In ECDSA, $ \mathbb{G}$ is an order-$q$ subgroup of
an elliptic-curve group $E({\mathbb Z}_p)$, for $p$ prime. (ECDSA also allows elliptic curves
over other fields.)
Any element of such a group can be represented as a pair
$(x, y) \in {\mathbb Z}_p \times {\mathbb Z}_p$. The function $F$
in this case is defined as $F((x,y)) = [x \bmod q]$.

DSA and ECDSA - abstractly:
Let $\cal G$ be a group -generator algorithm.

$\sf gen$: on input $1^n$, run ${\cal G}(1^n)$ to obtain $( \mathbb{G},
   q, g)$. Choose uniform $x \in \mathbb{Z}_{q}$ and set $y:=g^x$. The
public key is $(\mathbb{G}, q, g, y)$ and the private key is
$x$.

As part of key generation, two functions $H: \{0,1\}^* \rightarrow
   \mathbb{Z}_{q}$ and $F:  \mathbb{G}\rightarrow \mathbb{Z}_{q}$ are
specified, but we leave this implicit.
$\sf sign$: on input the private key $x$ and a message $m \in
   \{0,1\}^*$, choose uniform $k \in \mathbb{Z}_{q}^*$ and set
$r:=F(g^k)$. Then compute $s:= [k^{-1} \cdot (H(m) + xr) \bmod q]$.
(If $r=0$ or $s=0$ then start again with a fresh choice of $k$.)
Output the signature \mbox{$(r, s)$}.
$\sf vrfy$: on input a public key $(\mathbb{G}, q, g, y)$, a message
$m \in \{0,1\}^*$, and a signature $(r,s)$ with $r, s \neq 0 \bmod
   q$,  output 1 if  and only if  $$ r = F\left(g^{H(m) \cdot s^{-1}}
   y^{r \cdot s^{-1}}\right). $$

Assuming hardness of the discrete-logarithm problem,
DSA and ECDSA can be proven secure if $H$ and $F$ are modeled as random oracles.
As we have discussed above, however,
while the random-oracle model may be reasonable for $H$,
it is not an appropriate model for $F$. No proofs of security are known for the specific
choices of $F$ in the standard. Nevertheless, DSA and ECDSA
have been used and studied for decades without any attacks being found.

Proper generation of $k$.
The DSA/ECDSA schemes specify that the signer should choose a uniform $k \in \mathbb{Z}_{q}^*$
when computing a signature. Failure to choose $k$ properly (e.g., due
to poor random-number generation) can lead to catastrophic results.
For starters, if an attacker can predict the value of $k$ used to compute a
signature $(r, s)$ on a message $m$, then they can compute the signer's private key.
This is true because
$s = k^{-1} \cdot (H(m)+xr) \bmod q$, and if $k$ is known then the only unknown is the
private key $x$.

Even if $k$ is unpredictable, the attacker can compute the signer's private key
if the same $k$ is ever used to generate two different signatures. The
attacker can easily tell when this happens because then $r$ repeats as well.
Say $(r, s_1)$ and $(r, s_2)$ are signatures
on messages $m_1$ and $m_2$,
respectively. Then
\begin{eqnarray*}
s_1 & = & k^{-1} \cdot (H(m_1)+ x r) \bmod q \\
s_2 & = & k^{-1} \cdot (H(m_2) + x r) \bmod q.
\end{eqnarray*}
Subtracting gives $s_1-s_2 = k^{-1} \left(H(m_1)-H(m_2)\right) \bmod q$, from which $k$
can be computed; given $k$, the attacker can determine the private key $x$ as
in the previous paragraph.
This very attack was used by hackers to extract the master private key
from the Sony PlayStation (PS3) in 2010.


What effect does adding noise to a substitution cipher have?

I did some simulations and found that after adding noise, the common English letters (e, a, t, r, s, etc) still stuck out like sore thumbs. Knowing which characters represent these letters, and assuming the attacker knows we added noise, makes this only trivially harder than a straight substitution attack.

But that got me thinking, what if for each letter A-Z I choose some random amount of random numbers to represent that letter. Each random sequence must be uniquely identifiable when concatenated with any other value (I don't know an easy way to generate this kind of key but its possible to construct manually if your careful). For example I could choose the following values for A, B, and C:

A: 36 52 47
B: 36
C: 95 47

Given the string "36 52 47 95 47 95 47 36 52 46 36" we can tell that it represents the characters "ACCAB", but without knowing the key, frequency analysis wouldn't work (for example B shows up once in our plaintext, but its corresponding cipher text value 36 shows up three times).

I don't know if this type of cypheralphabet has a name, but I realized that on its own, it isn't that strong. We can look at the frequency of pairs of numbers in the ciphertext and determine what numbers are more likely part of the same character representation. If you can split the numbers up correctly, then this is the same as a standard substitution cipher.

But if we add noise to this weird random character length cipher alphabet, in the same way it was originally described, then there is no way I can see to determine which groups of numbers represent single characters, and basic frequency analysis doesn't work. What am I missing?


Discrete Logarithm Problem or just integer exponentiation problem?

As you can see in their abstract, they are assuming that "the
standard Computational Diffie-Hellman problem is intractable", thus this means that you may necessarily break their scheme by solving the Discrete Logarithm problem, since the Computational Diffie-Hellman (CDH) problem can be solved easily if the DLP can be solved.

The CDH problem is the following:
for $G$ a cyclic group of order $q$, with $g$ one of its generator, given $(g,g^a,g^b)$ with $a,b \in \{0, \ldots, q-1\}$ randomly chosen, one want to compute the value $g^{ab}$.

If computing discrete logs in $G$ were easy, then the CDH problem would be solved, since one would be able to compute:

$b$ by taking the discrete log of $g^b$;
$g^{ab}$ by exponentiation: $g^{ab} = (g^a)^b$

However, it is important to note that the CDH and DLP problem are not necessarily equivalent! Hence, it may be possible once to solve the CDH problem without being able to solve the DLP or it may also be possible that both will be proven equivalent some day, as Maurer already proved it to be true under certain conditions regarding the smoothness of integers in given intervals.

So, if you want to consider their scheme as being an instance of the DLP, you may, however it may be simpler than the DLP.

On the other hand, the problem you are stating, being given $c_1, g$, find $r$ for $c_1=g^r \mod p$ is an instance of the DLP.

So yes, you can reverse their public keys directly if the DLP is easy.


How can I introduce a new method of encryption to the world?

because I am an ordinary person, I have no facilities and the ability to introduce this algorithm

Typically people write a paper and submit it to a journal. If it's any good and indeed "has no similarity to any other existing algorithms", it will definitely cause a stir. Most methods that you and I can come up with, have been thought of and are either used in modern encryption or were discarded for good reasons.

  this algorithm may also have weaknesses that would question its validity

That's a good thing to acknowledge! I remember when I invented my first encryption algorithm: I thought it would be unbreakable as long as it remained closed source (it'd be licensed to banks and stuff). I was super naive as a kid :)

Note that my personal story ended with me putting it up on some forum for security experts and someone breaking it despite not having the algorithm.

  the website was created solely for testing this algorithm

On your website, I do not see the algorithm. How are we going to test and validate it?

  the algorithm will be publicly released if approved by experts in the field

If you really want to do it that way, you can find and pay said experts to vet your idea. I'd advise you to just post it publicly and see if anyone can pick it apart. Only if there are no glaringly obvious flaws, you might want to have some experts look at it. And actually, if it's indeed good and new, experts will probably be attracted by themselves.

  despite repeated attempts and correspondence with reputable technology websites

Wait, crypto experts typically do not reside on technology websites. You'll be wanting to contact consultants and show them green stuff that they can use to exchange for bread and cheese at local stores.

  nobody was willing to help me.

They might have recognized that you are at the wrong address, or if you weren't, they'll have gotten many requests from rookies that wanted to validate their neophyte algorithms. Many rookies go down this path of (1) self-inventing things that are stupid and (2) not knowing how to publish. Myself included. I'm not saying that you are a rookie, but it's just likely that you are and people will often not find it worth their time to look at.

Crypto is seen as a hard field because it is indeed hard to do properly. It's not something that comes to you while in the shower, but typically requires years of study. By then, you will have seen how others published their work, so you'll know how to publish. Also, others might have seen your name already if you've been active in the field, which also gives you more credibility to start with.

  Please guide me and help inform this.

Release the algorithm and ask some hacker friends to take a go at it for fun.

And optionally, write a paper and try to get a journal to publish it. This should get it reviewed by others from the field.

By the way, having a bounty (as it's called; it's not a bonus) is nice. It'll definitely attract people to look at it. Just be prepared to pay out!

It's a little off-topic (your question is "how to introduce to the world", not "is it secure"), but if I may comment on your video and challenge:

Looking at the video, you're not entering any password. From that I assume that the key material is either (1) hard-coded in the program, (2) written into the output file or (3) does not exist (i.e. the algorithm is the key material). In case of option 1, that's bad practice; option 2 means it's just not encryption (it's encoding); and option 3 means you've violated Kerckhoff's principle.

On the other hand, I'm happily surprised to see that your challenge file has good entropy. When turning the ascii decimals into binary, ent gives me 7.93 bits/byte (for 3099 bytes of binary; testing with 3099 bytes of /dev/urandom I get 7.94 bits per byte). It's at least of better quality than what I invented when I was younger :).


How can I convert numbers into prime numbers?

Thank you for your answers but I think I found a better method.

Take the hash of your input $h(x)$, preferably with random oracle approximation
Sample the interval $[2^kh(x), 2^k(h(x)+1)]$ and pick only primes, for each of them
Hash it with an universal hashing function $f$ until you find that $f(p)=h(x)$
Write to memory: $H(x)=p$

Done!

notes:

The random oracle makes collisions infeasible
Universal hashing gives high density of primes with high probability (there is a theorem out there but the principle is that, for a given prime, I have multiple hash outputs, so the probability that one of them is my input increases. See: Gennaro et al. - Secure hash-and-sign signatures without the Random Oracle, lemma 2)


Looking for a Non-textual hashing function

This is a pure encoding problem, as @kelalaka said. Take any reasonable hash algorithm like SHA-512. You have all qualities that you mentioned - not reversable, low probability of collisions, etc. What needs top be done, is to encode this hash into a picture.
To algorithm: look for instance at automatic generation of avatars at Stack Exchange to get one of possible simple ideas.
If you use SHA-512: The hash consists of 64 bytes. Consider it as a matrix of 8x8 elements, for each element define 256 values. These 256 values can be a combination of simple elements, e.g. 4 elements each having 4 states.


Why is RSA unsafe if N=pq can be factored?

Let's assume RSA works.
There is a person, who created the key. He chooses 2 primes, multiplied them, and publishes the modulus with another number he can choose almost freely (it has to be coprime to $(p-1)(q-1)$).
So if you give the attackers the factorization, what else is there, that the attackers does not know? There isn't anything.
There is not much to put formally. If the attackers knows all secret information, there can not be any security. What should it be based on? Unless we allow security to be based on magic fairy dust.


Families of public/private keys in elliptic curve cryptography

I would assume that all the operations are to be done in the elliptic curve group (viewed as a module over $\mathbb Z/k\mathbb Z$, where $k$ is the order of the group), so that addition is the group operation and multiplication is elliptic curve point multiplication.

That is to say, assume we have an elliptic curve $E$, equipped with the point addition operator $+$ so that $(E,+)$ is a group.  We can define a scalar multiplication operation on $E$ simply as $$n \cdot P = \underbrace{P+P+\dotsb+P}_{n \text{ times}},$$ where $n$ is an integer and $P$ is a point in $E$.
Let $G$ be a point in $E$ which generates a cyclic subgroup of $E$ of order $k$: that is, $k \cdot G = 0_E$ (and $0 < j < k \implies j \cdot G \ne 0_E$), where $0_E$ is the group identity of $(E,+)$.  All these are public parameters shared by all users of the group.

In ordinary ECDSA, we would choose a random private key $x \in \mathbb Z/k\mathbb Z$ (that is, a random integer such that $0 \le x < k$) and compute the public key $Q = x \cdot G$.

However, if we also had a function $H$ mapping integers to (pseudo)random values in $\mathbb Z/k\mathbb Z$, we could define a sequence of private keys and corresponding public keys as $$x_i = x + H(i)$$ $$Q_i = x_i \cdot G = Q + H(i) \cdot G$$ where the $+$ on  the first line stands for ordinary addition (modulo $k$) and the $+$ on the second line is elliptic curve point addition.  (A consequence of the way we defined scalar multiplication above is that addition distributes over it: $(a + b) \cdot P = a \cdot P + b \cdot P$.)

There are various ways in which we could define $H$.  For example, we could use a hash function as in your example, possibly with a salt $S$, or we could perhaps pick a block cipher $B$ and a random key $K$, and let $H(i) = E_K(i)$.  In fact, assuming that $H$ and $Q$ are indeed truly public, I'm not even sure that there's any reason not to just use $H(i)=i$.  (Indeed, I can't even prove off the top of my head that this scheme is secure for any $H$.)  But the salted hash certainly seems as good as any other choice for $H$.

Edit: I just noticed that you wrote:

  "Ideally, without the master public key, even given a number of public keys in the series, it would be impractical to determine any other public keys in the series or the master public key."

I'm not sure if you wanted that to be impractical with or without knowledge of $H$ and of the indices $i$ corresponding to the known public keys $Q_i$.

If with, we have a problem: anyone who knows $H$, $i$ and $Q_i$ can calculate $Q = Q_i + (k-H(i)) \cdot G$.

If $i$ and/or $H$ can be treated as secret, things get trickier.  Obviously, $H(i)=i$ is a bad choice in this case, since anyone who knows $Q_i$ could then calculate $Q_{i+j} = Q_i+j \cdot G$ for any $j$, but using a hash or a block cipher for $H$ would eliminate that simple weakness.

Also, regardless of $H$, someone who knows $Q_i$ and $Q_j$ can calculate $Q_i - Q_j = (H(i)-H(j)) \cdot G$; but I'm not sure what, if any, good that would do them, assuming that $H(i) - H(j)$ is not likely to equal $H(k)$ for any valid index $k$.

Anyway, it would be helpful to know just what parties are supposed to be involved in this scheme and what they're supposed to know.  In my original answer, I'd been implicitly assuming that the public keys were, well, public and known to everybody.  If that's not supposed to be the case, that could complicate things a lot.


Are RSA or ECC vulnerable to an attack where the same (unknown) plaintext is encrypted with multiple public keys?

RSA is vulnerable to this attack if an insecure padding scheme is used. Still unsure about elliptic curve cryptography.


It does not break Bob's deniability since MAC keys are symmetric. Bob still has plausible deniability as Alice could have just as easily forged any message she claims was from Bob.

Also, remember that OTR uses malleable encryption (a stream cipher mode) and has a forgeability property, which makes deniability even easier for Bob.


Do Message Digests protect public cryptography from replay attacks?

No, a MAC only prevents an attacker from modifying the message.  On its own, it does nothing to stop the attacker from resending a valid message unchanged.

To stop such replay attacks, your message have to include some contextual information that will make an originally valid message invalid if replayed.  For example, if your messages each have a sequential message number, you could simply reject any messages with the same or lower number than the highest-numbered valid message you've received so far.

(Of course, you also should be prepared to deal with the possibility that legitimate messages may be lost or arrive out of order, either due to active attacks or simply due to unreliable communications.  One option could be to use a non-cryptographic transport layer such as TCP to take care of message ordering and retransmission, and only use crypto on the application layer to verify that the data stream received over TCP has not been tampered with.  Another option would be to implement your own message transport protocol, e.g. using a sliding window approach to deal with accidental message reordering.)

What a MAC (computed over the entire message, including metadata) can do is protect these message numbers (and other relevant metadata) from tampering, so that an attacker can't simply change the message number on their replayed messages, or e.g. copy the message number from one valid message to another.


Why are RSA keys encoded with ASN.1 for TLS?

Think about this, say my public key is

9821347676528476512348612390874073765227653408545634205496835 (note this is not a valid public key, just randomish typing).

What does that mean? Big or little endian? Hex or decimal? Specifically for RSA, where is $e$, where is $N$? What is this public key authorized to do (encrypt, sign, etc)? Who has signed this key? To whom is the key linked?

While a public RSA key is "just a number" there are a lot of reasons to encode the key in a standard way so that every computer everywhere knows how to understand it, what it is authorized to do, who it belongs to, etc.


Should HMAC-SHA3 be preferred over H(C(k,M))?

HMAC does not provide an obvious security improvement over the KMAC construction, which is optimal for Keccak based functions. HMAC is designed to create a secret initialization vector or IV for Merkle-Damgård type hash functions, KMAC does the same for sponge based hash functions but much more efficiently. HMAC also needs to deal with the length extension property

KMAC extends the key to the block size and prepends it to the message. I believe this will be standardized (if it has not already) as the default MAC construction for SHA-3. Because it extends the key to the block size, an F iteration is performed over the key prior to message absorption, creating a secret keyed state.

This is the basic sponge MAC construction discussed during the Keccak design phase, and in later discussion of both Keccak and SHA-3. There needs to be some kind of encoding or padding to effectively separate keys of different sizes, but this is not discussed in those documents; the $C$ function you mention would perform such separation. KMAC as discussed during the August 2014 SHA-3 workshop shortly after the publication of FIPS 202 uses the "keypack" function to pad the key and encode the byte-length of the key block as an 8-bit value, using a minimum of 9 additional bits beyond the length of the key: $\operatorname{Keypack}(K, l) = \operatorname{enc}(l /8) | K | 1 0 ^{l-\operatorname{len}(K)-9}$ where $l$ is the block size.

The "block size" of SHA-3 is at least 576 bits for all variants, meaning a 512-bit key can key the state with only one additional iteration of $f$. Additionally, since there is no block or bit counters, a device with low computational resources but enough memory can simply keep the keyed state as its default state for MAC computations and suffer no performance hit when compared to plain hashing.

Update: Since this answer was originally written, NIST has published SP 800-185 standardizing KMAC and a few other useful Keccak-derived constructions.


Why does the ZUC need an initial vector?

The initial vector is also known as an initialisation vector (IV). As mentioned by Mr Smet in the comments, it allows a user key to remain constant, yet the cipher text to be unique for every transmission even if the plain text is also constant.  So simply put, sending "Hello Mr. Feng" with the same key over and over will result in unique cipher texts. This feature disguises that you're sending the same message and helps resists crypt-analysis.

Strictly put, the cipher text will still be generated correctly if you didn't use an IV, it's just more secure to do so.  Your ZUC document just assumes that implementors know what an IV is. There's more detail at the Wiki entry and at What is the main difference between a key, an IV and a nonce?

There are strict rules for generating the IV that you can easily look up, such as uniqueness and randomness.


Why does key generation take an input $1^k$, and how do I represent it in practice?

The $1^k$ is a formalism that's only there to make the theoreticians happy.  You can safely ignore it.  When you actually implement the cryptosystem, you don't try to pass the string $1^k$; instead, you pass $k$, the security parameter (a representation of how much cryptographic strength is desired from the key generation algorithm).

I wish I could leave it at that, because this is nothing deep: it's just something stupid and not important in any fundamental, conceptual sense.  However at this point you're probably going to be saying "huh?", so I suppose I have to explain.

Why is it there?  For totally stupid reasons.  Its only purpose is to help remind theoreticians that key generation should be efficient: its running time should be polynomial in the security parameter.

In more detail, we want the security of our cryptosystems to be parametrizable (totally reasonable so far): for instance, if you want 80-bit security, you should be able to pick the parameter $k=80$ and get corresponding security.  Theoreticians also want to impose the requirement that all of the cryptographic operations are pretty efficient (still pretty reasonable): increasing the security parameter doesn't slow down the crypto too much.  Some theoreticians work in the context where performance is measured in asymptotic complexity (somewhat unreasonable in practice, but we can let that one go as it is still useful and understandable).  So, they formalize the requirement that crypto operations be efficient by requiring that the asymptotic running time of all crypto operations (key generation, encryption, decryption) be polynomial in the the security parameter.

Are you following so far?  So far, nothing is totally unreasonable -- but get ready, here comes the silly part.  Our standard notion in complexity theory of what it means for an algorithm to be efficient is that the algorithm's running time is a polynomial in the length of the input to the algorithm.  The theoreticians want their formalization to fit within this standard complexity-theoretic framework.  Therefore, they formalize the requirement that crypto operations run in polynomial time by passing a special dummy padding string as input to the operations whose length is given by the security parameter.  Why pass the dummy string?  Well, those operations are going to completely ignore the dummy string, so passing this extra useless string seems completely pointless.  It is pointless from a practical perspective, but from a theoretician's perspective, it lets them require that the cryptographic operations have a running time that is asymptotically polynomial in the length of their inputs -- and it will follow automatically that their running time is asymptotically polynomial in the security parameter (because they artificially ensured that the length of the inputs is the same as the security parameter).  This makes the theoreticians happy.

Like I said, it's stupid and pointless and exists only to make the theoreticians happy.  When it comes time to implement the cryptosystem, ignore it.

P.S. Perhaps I should reveal at this point that I have a bit of a theoretician in me, and sometimes it makes me happy too -- but I still realize how silly it will look to someone who cares more about using crypto than about proving theorems in complexity theory.


Variant of Schnorr Protocol (Difference pair of response and verification)

response $s=c(x+r)$, verify $g^s=(yt)^c$

This one doesn't work; a lying prover can chose $t = y^{-1}g^n$, for an arbitrary $n$.  Then, when the challenger responds with a $c$, the lying prover can respond with $s = nc$, satisfying the relationship.

The other two are good; the second is the standard Schnorr, and the first is standard Schnorr proof of the inverse relationship, that is, if you're proving the knowledge of $y^{x'} = g$ (which is equivalent to knowledge of $g^x = y$)


Having more than two prime factors is supported by the PKCS#1 standard. This is called a "multi-prime" key.

On the plus side, this may offer some performance improvement. The Chinese Remainder Theorem still applies (see for instance in section 5.1.2, the description accommodates more than two primes). For instance, if you have a 1536-bit modulus which is the product of three 512-bit primes, then the CRT replaces one 1536-bit exponentiation with three 512-bit exponentiations which are, individually, 27 times faster (assuming a classic cubic modular exponentiation algorithm), for a total speedup of 9, compared to the usual 4 with two factors. More generally, with $k$ factors, the expected CRT speedup is in about $k^2$.

On the negative side, using too small factors may weaken the modulus. The best known factorization algorithms have a cost which depends on the modulus size, not on the size of the individual factors, so using more smaller factors should have no impact... unless the factors are small enough to enter the range of the feasible with ECM: that algorithm has a cost which depends (mostly) on the size of the smallest factor. For normal, bi-prime RSA modulus, ECM is not competitive with GNFS; but if you make your factors too small, this can lower your security.

Bottom-line is that, for usual sizes, three or four primes should be tolerable and offer a nice performance boost, but don't go beyond that. Public-key operations are not impacted in any way. Note also that other somewhat related cryptosystems (e.g. Rabin) might not accept a multi-prime modulus.


Pollard's $(p - 1)$ factorization method runtime

The $p-1$ method finds factors $p$ of an odd $n$ for which $p-1$ divides only (powers of) primes smaller than some user-selected bound $B$. It does this by computing
$$
\gcd(2^M - 1, n),
$$
where $M = \mathrm{lcm}([1, 2, \dots, B]) = 2^{\lfloor \log_2 B \rfloor}\cdot 3^{\lfloor \log_3 B \rfloor} \dots$. Note that the exponentiation $2^M - 1$ can (and should!) be performed modulo $n$. We can split the computation into three steps:

Find the primes up to $B$. Using the sieve of Eratosthenes, this takes time $O(B \log \log B)$. This only needs to be (pre)computed once, regardless of which $n$ we're factoring.
Compute $2^M - 1 \bmod n$. Instead of computing $M$ explicitly, one may opt to exponentiate $2$ by $2^{\lfloor \log_2 B \rfloor}$, then by $3^{\lfloor \log_3 B \rfloor}$, etc. Each exponent has $O(\log_2 B)$ bits, and there are approximately $B / \log B$ primes, by the prime number theorem. This gives us an exponent of $B / \log B \cdot \log_2 B = B / \log 2$ bits, which leads to $O(B)$ multiplications modulo $n$ using binary exponentiation.
A final GCD of integers at most $n$ sized, which costs at most $\log n$ multiplications of $n$-sized integers.

Unless $B$ is very small, the cost will be dominated by the second step, which has complexity $O(B \cdot \log n \cdot \log \log n)$ using fast multiplication, or $O(B \cdot (\log n)^2)$ using schoolbook multiplication. Wikipedia's bound appears to be the complexity of the variant which uses $M = B! = O(2^{B \log B})$ as the exponent, instead of $M = \mathrm{lcm}([1, 2, \dots, B])$.


Is the MD5 algorithm only useful for bytes, rather than bits?

If I wanted to write an MD5 implementation that also accepts files, does the bit/byte distinction become important?

No, a byte implementation is fine. In modern OSes, hashing from a file, pipe, string (whatever the encoding) is hashing bytes.
The only times I made and used an implementation of a hash with bit support was to make or check test vectors. But I can imagine a few use cases that would require bit support

hashing the expression as a minimum number of bits of an integer (per some specified endianness), for an hypothetical algorithm specifying that.
one wants a few variants of MD5, and obtains these by appending a suffix shorter than a byte to a bytestring fed to MD5. For 15-byte messages that makes a computational saving compared to appending a whole byte (one internal padded message block of 32 bytes rather than two), plus avoids trivial collisions with regular MD5.


How to use Frobenius for finding Square Roots in $GF(2^m)$

No, the relation you have noticed does not work in general, and it is easy to find counterexamples. For example using the two following representations of $\mathbf F_8$.

In $\mathbf F_2[X]/(X^3+X^2+1)$, the square root of (the coset of) $X$ is $X^2+X+1$, whereas in $\mathbf F_2[X]/(X^3+X+1)$ it is $X^2+X$.


How can I study the math behind cryptography?

Speaking from my own experience, Nigel Smart's book Cryptography: An introduction is a good place to start. I would say that you can read and understand it without any prior knowledge of cryptography at all. It is also free.


I am not sure why you think that "homomorphic schemes and big integers are not a very efficient combination". In most homomorphic public-key cryptosystem, the message space is very large. For example, the Paillier cryptosystem (probably one of the most used for secure voting) has a plaintext space size of $2^{2048}$ with current security parameters. This allows for elections with a million voters and a hundred candidates. Moreover, the plaintext space of Paillier can be increased if necessary (interestingly, it can even be increased "on-the-fly" if the plaintext space size seems too short, without having to ask the voters to re-vote). With $4096$ bits, you can support twice more candidates, or a billion of voters.


What's the preferable encryption for large data and files in terms of speed and security other than AES?

Based on your comments I have a feeling that may be you don't really understand what a huge number of combinations a 256-bit key means. At the first glance 256 bit is "just" 16 bytes. But look at it closer. With 256 bits we can encode $2^{256} = 10^{77}$ numbers. It is 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 numbers.
Still too theoretical? You may get better feeling if you run a simple Python script:
i = 0
while i < 100000000000000000000000000000000000000000000000000000000000000000000000000000: # 2^256 ~= 10^77
    if (i % 100000000 == 0):
        print i
    i = i + 1

Every second, on weaker CPUs may be every 10 seconds, you will see a 9-digit number. In 1 day you will see the numbers are 10-digits. In 100 days you will see 12-digit numbers. In 3 years you will see 13-digit numbers. If you pay for 1 000 computers for 30 years, then you will get 16-digit numbers. Still extremely far from 77-digit numbers.
This script is very simple and fast. But brute-forcing of AES will be much slower. For every key candidate one would need to decrypt some considerable peace of data, then analyze if decrypted data mean anything like document, image, video.
Be realistic. Estimate how much money would an attacker obtain if your files are brute-forced and if they can sell your files to somebody. Will they get \$1 000, \$1 000 000? Nobody will brute-force your AES password (except checking against dictionary with typical weak passwords and their variations, which is very quick). If your secrets are worth \$1 000 000, then it may be much cheaper to pay hackers $500 000 to break into your system, read your passwords or install key loggers; or install spy cameras in your home, your car etc. and thus get your passwords; or steal your key if you have hardware token.
TLDR: AES with 256-bit key is more than sufficient.


Are there any well-known examples of SHA-256 collisions?

No, there is not any known SHA-256 collision. Publication of one, or of a remotely feasible method to obtain one, would be considered major.

It is next to impossible that two distinct strings with the same SHA-256 have been computed so far. The most visible such computation is in bitcoin mining. By summing this data giving history of SHA256d hash rate (that's two SHA-256), I get that by end of April 2018 that had made 289.7 SHA-256, with the exponent growing roughly by 2 per year for the last few years. My computations, and opinion that they represent the bulk of SHA-256 made, have not been challenged there. Extending to 291 to account for other cryptocurrencies and (perhaps coverts) password search activity, odds are about 1 against 2256+1-91-91 = 275 that a collision occurred (see Birthday problem for cryptographic hashing).

For the purpose of illustrating collisions, perhaps make an example with SHA-256 restricted to its first 64 bits (16 hexadecimal characters instead of 64), and explain that each 2 bits added doubles the expected number of hashes before a collision occurs.