Hello There, Is there an optimal choice for the first s ? I have tried random values (but I am sure there is a better choice) for a few hours, with no luck. Any hint ? Thanks

I started with the value s = ceiling(N / 3B) ( B being defined in the paper as 2^(8 * (k-2)) ). This is the same value as is recommended in Step 2.a of the paper.

I arrive at a valid solution but it is 14 hex characters, and a bunch of 0's padded on the right. They are not ASCII characters and this doesn't resemble a valid padded message. Any thoughts? I wouldn't think a valid solution would be found by accident.

That doesn't sound quite right, you can email us with the specifics if you like. Otherwise I'm not sure there's much I can recommend beside double checking you implemented the algorithm, as described in the paper, correctly

I rewrote basically the exact same algorithm on a python 2.7 machine and got the correct answer. The python 3 version seems to give an incorrect answer. In any case I got it, thanks.

It may have to do with the fact that python 2 will round down to the nearest integer when you divide two integers. Python 3 will actually give you back a float when you divide two integers (use // in 3 to get the behavior of / in 2). In any case, congrats on solving the problem!

Is it expected that the oracle returns 0 on the original ciphertext?

The oracle should be returning a 1 on the given ciphertext, since I've confirmed by factorizing the modulus it's PCKS15 padded. Seems like either the example code from this does not work in python3 or the problem is busted now.

For those who are trying to do this problem offline, I've written a function for Python3 that you can use instead. If the creators are bummed about me posting the private exponent, y'all can hmu and have me remove the post.

def is_padded(cnum):
    #first we decode it on our end
    d = <staff note: redacted>
    N = 0x4c81390477e071a7a9afd85eeb93f3596cf69fb8e7fadf422f22c68891586611af5e74aa8b4df9a585486898f632ae63
    pt = pow(cnum, d, N)
    #next, convert to bytes
    plaintext = pt.to_bytes(96//2, 'big')
    #finally, confirm it's PCKS formatted
    hasHeader = plaintext[0] == 0 and plaintext[1] == 2
    hasDivider = 0 not in plaintext[2:10] and 0 in plaintext[10:]
    return hasHeader and hasDivider

I've edited the above post to redact the private exponent. There was a period where the oracle was flaky, I've made some fixes and confirmed all the oracles are again able to provide responses that allow solving without knowing any secret material.