# TMSR-RSA spec, extremely early draft

**I. As far as extant literature** is concerned, Werner Koch is a malevolent imbecile whose shameless parents should nevertheless fucking apologize. Everyone else^{i} "involved" in "crypto" to date is not far behind, from Zimmerman^{ii} onwards.

**II. The RSA key** shall be a 4096 bit^{iii} entity produced out of two 2048 bit primes^{iv}. The key will be stored as a N, e, C structure, where N is the public modulus, e the chosen exponent, and C a comment field *of unspecified length*. Key fingerprints will be calculated over this structure through a yet-to-be-specified hash function.^{v}

**III. The RSA exponent** will be a 4096 bit integer at the option of the user. In principle the user can input any 4096 bit prime, but one of two types are recommended : either the FULL style^{vi} or else the RNG style^{vii}.

**IV. RSA padding** will be provided through Keccak-OAEP^{viii}. Messages longer than 2048 bits will be packeted into 2048 bit chunks. There will be no symmetrical cyphers involved at any point. Signatures will be based on the same padding.

**IV. RSA implementation** will work in constant time and constant space ; the canonical implementation will be written in Ada. Work is ongoing towards a FFA-based approach.

**V. Alternative ciphers.** Cramer-Shoup.

- See the logs re useless antecessors, I won't rehash here. Not so much as a fucking constant - time exp they produced, these useless fucktards that aren't anything else. [↩]
- Years prior to the reveal, "Zimmerman" responded to an email encrypted to his key by stating (in plain text) that he "decades ago" lost the corresponding key. 'Nuff said. [↩]
- For about a year I strongly supported eccentric length key. I gave up on the idea recently, because the arguments against as presented satisfied me -- and when reason speaks emotion'd better shut the fuck up.
The user will not get any say in the matter. 2048 keys are too short. 8192 keys are too long. Keys of a length that's not a power of two are no good. RSA keys are 4096 bits and that's the end of the story. [↩]

- Primality testing,
**as well as everything else**, will be implemented correctly, as opposed to imperialy. This point fractally and endlessly repeats itself throughout, because everything the pantsuits to is retarded on all levels, recursively. Nevertheless, it won't be repeated here. [↩] - The requirements for this role are a) no blocks and b) unlimited size input. The current candidates for this role are either keccak or mpfhf. [↩]
- Something like say 1111111111111111111111111111111111111111111111111111111111000101, or more generally speaking 2
^{64}- 59, 83, 95, 179, 189, 257, 279, 323, 353, 363 etc [↩] - 1100111110111010111111000100100010011101001010001000100100011001 , or generally speaking anything with ~half the bits set (that's also a prime number, obviously).
As Stan aptly puts it,

No moar 'we heathens have faster RSA because mother dropped us as babies and our RSAtron does different work on different hamming weights'

Word. [↩]

- To pad : 1. Produce M00 by adding 0s on the right of message M until M00 reaches 2048 bits in lenght ; 2. Generate R, 2048 bits of entropy ; 3. Calculate X = M00 xor hash(R) ; 4. Calculate Y = R xor hash(X). The padded message M is X + Y.
To de-pad : 1. Calculate R as Y xor hash(X) ; 2. Calculate M00 as X xor hash(R) ; 3. Remove 0padding.

The hash function is yet to be specified. It should be a non-block 2048 to 2048 bit hash function (conceivably, can also use two). [↩]

Wednesday, 16 August 2017

MPFHF dun go with constant-time-constant-space...

Wednesday, 16 August 2017

I thought we were happy with "at every juncture calculate both the 1 and the 0, throw away one of the two" approach to fix that problem ?

Wednesday, 16 August 2017

Meanwhille, tis gone.

Friday, 18 August 2017

So UDP has a "unfragmented packet" limit of 512 bytes. To use UDP for gossipd, would you use keys of only 2048 bits (256 bytes) or only have a message of 256 bytes with 256 bytes padding, or use the whole 512 bytes for a message and 512 bytes for padding and have a possibly fragmented packet, or send the message in one udp packet and the padding in another?

Friday, 18 August 2017

> or send the message in one udp packet and the padding in another?

This is fucking precious lol.

But you have a point, last footnote should have quited 2048 not 4096 bits for padding m00 so that 256 bytes of message are OAEP'd and the resulting 512 byte padded message is encrypted in each packet.

Friday, 15 September 2017

IIUC, for RSA encryption the message must be smaller than the modulus.

So if we pad our message to get a 4096 bit message for encryption, and we have a 4096 bit modulus, how do we ensure that the message is smaller than the modulus?

Friday, 15 September 2017

There's two approaches, one's to chunk it the other's to add a symmetric encryption layer in between (then you just rsa the key, and so it always fits). The republic favours the former over the latter.

Saturday, 16 September 2017

I don't think you undrstood the question I am asking. I get the idea of breaking a long message into chunks, I am talking about a single chunk here. After doing OAEP, you have some 4096 bit number. Some of those numbers are less than the modulus, and so are fine, but what do you do with the ones that are greater than the modulus?

Monday, 6 November 2017

Footnote vii reads "(that's also a prime number, obviously)." regarding the public exponent. Does TMSR spec require the public exponent to be prime itself? Isn't it enough if it's co-prime with (p-1)(q-1)? (and obv between 1 and (p-1)(q-1) ).

Monday, 6 November 2017

Coprime works, yes, if the coprimality test is cheaper than the primality test. Is it ?

Monday, 6 November 2017

The coprimality test is GCD and in fact considerably cheaper than any reasonable primality test.

That being said, I quite dislike the notion of ever using a composite public exponent -- it makes certain types of attack cheaper, while ( at least in FFA-land ) getting nothing useful in return.

Monday, 6 November 2017

If we permit merely coprime exponents randomly generated, about half will be even numbers.

Monday, 6 November 2017

I know of no persuasive reason to permit composite pub-exponents at all.

Why give the enemy the advantage of getting to use CRT?

Monday, 6 November 2017

The persuasive reason, such as it is, is cheapness.

It's not clear how we'd calculate the supposed weakness using a coprime but composite large exponent would induce.

Monday, 6 November 2017

The "cheapness" of composite-pub-exp does not exist for you when using a nonleaking (i.e. fixed-spacetime, FFA) rsatron.

It does however make life easier for the enemy, who is using, e.g., a 'superencryption' brute-force (against a rsa scheme where padding failed -- and a provably-unfailing padding is not known.)

A composite pub-exp is arguably exactly the same item, cryptologically, as taking the smallest prime factor of it and using ~that~ as the pub-exp.

Monday, 6 November 2017

> The "cheapness" of composite-pub-exp does not exist for you

It does, in that you don't have to test for it. See above.

> A composite pub-exp is arguably exactly the same item, cryptologically, as taking the smallest prime factor of it

I suspect this is correct, in which case it entirely doesn't matter whether the 4096 bit exponent is composite or not, the odds of the largest prime in it being 65537 or smaller literally 0.

Monday, 6 November 2017

> the odds of the largest prime in it being 65537 or smaller literally 0

Umm, try this yourself ?

Or see the cached phuctor liquishit keys. It's a ~1, not 0.

Monday, 6 November 2017

My quote discussed the largest prime ; on re-read you were talking about the smallest prime. This makes no sense to me ; are you proposing that exponent 131074 reduces to exponent 2 somehow and you'll be able to apply eg Coppersmith ? I'd like to see this drawn out.

Other than this conversation, it is brought to my attention that eg https://pdfs.semanticscholar.org/42c9/10ed955236438a5f8d51f1e7f235e9c1f565.pdf : there's an implicit weaknes in very large public exponents (in that they force very small private exponents and private exponents smaller than N 0.292 are known to not be safe).

Monday, 6 November 2017

> exponent 131074 reduces to exponent 2 somehow

Aha

> I'd like to see this drawn out

I'ma put this in the conveyor.

> very large public exponents ... they force very small private exponents

How ?!

Monday, 6 November 2017

http://btcbase.org/log/2017-11-02#1732060 is correct by the way, Windows CryptoAPI can't handle exponents larger than 32 bit.

Monday, 6 November 2017

@

Stanislav DatskovskiyWiener's attack, what. Looks for a continued fraction approximation of e/N, lists all the candidates and then tries them all.@

TPHeh.Monday, 6 November 2017

Q was, how does large public exponent force the use of a small private exponent ?

Monday, 6 November 2017

Afaik the GPG remnant we're using computes d as the N-symmetric of e. Doesn't it ?

Monday, 6 November 2017

In RSA (incl. Koch's) d = e^-1 mod phi , but this op is not an integer reciprocation! -- it is a ~modular~ multiplicative inverse, and does not have the "large e forces small d" behaviour. Try it by hand.

Tuesday, 7 November 2017

Nevertheless, provided a large e GPG does in fact* produce a small d.

* To the degree anything meaningful can be said about GPG behaviour in general ; at some point it actually produced random 16 bit exponents for instance, until that feature being taken out in favour of using 65537 in the usual retrospectively-suspicious manner.

Tuesday, 7 November 2017

Did you try it ?

Tuesday, 7 November 2017

Not yet.

Tuesday, 7 November 2017

Minigame tech dept reports that out of 978 assays 0 produced d < n

^{0.5. }So I take it you're right.

Tuesday, 13 February 2018

At Keccak-OAEP the scheme reads:

"1. Produce M00 by adding 0s on the right of message M until M00 reaches 2048 bits in lenght"

How many 0s though? If it's a variable number of 0s depending on how many bits M happens to have, it's impossible to trim them back at the end (since M might have some 0s at the end itself).

Tuesday, 13 February 2018

I think the way this is actually done irl is repeat the last block (byte) of the message, then add the zeroes.

Wednesday, 14 February 2018

Some sort of in-band solution like that, if memory serves, indeed. "Null-terminated strings" etcetera.

Wednesday, 14 February 2018

Myeah, it is a form of inband such as 0x00||0x02||pseudo-random-non-zero-octets||0x00||M

Rummaging through GnuPG 1.10 code yielded mainly the usual headaches as the padding itself is a sort of kraken split in 10 files or so, not something that can be clearly pointed out or extracted or followed, why would it be.

Overall: I don't like this approach at all.