You should be able to solve this.

Data is pasted here for convenience:

01101011 01101100 01010101 11001010 00011001
01101000 10111101 10111010 01100110 01101111
11100001 01011000 00101100 11011110 10000100
01001001 01010000 00110110 10011111 01001100
01101100 10100110 11010101 00111110 01110111
00000100 00000000 01111100 00010101

Data in base 10:
107 108 85 202 25 104 189 186 102 111 225 88 44 222 132 73 80 54 159 76 108 166 213 62 119 4 0 124 21
Lehmer is a mathematician. In 1932 he made mechanical seiving machines, probably unrelated. Also made a random number generator so it probably means that (was used to make the cypher key)
A 32 bit repeating stream cypher key? No idea what MP is.

pic is a plot of data as 1-256, first graph is in order, second graph is re-ordered (to put all the values together by their modulo 4 position). brown and yellow lines are the ascii intervals which have upper/lowercase letters.
if i keep trying I'll try to solve for the key values so that it makes something approaching english text, maybe with some probability heuristic with letter frequencies or something. assuming the key is 4 bytes and each byte is applied in turn.

You're on the right track. To give you a hint, MP stands for Mersenne Prime. Cracking this specific generator should be doable in O(2^64), E[X] = 2^63, however, I'm nice so it's not going to take that long. You are correct in the assumption that the key/seed is 4 bytes (32 bits).

Well I tested the repeating key idea, no combination (additive) produces anything that isn't garbled (testing each key byte individually) but maybe if I used a bitwise xor. more likely it's not repeating but generated by key. might test if I have time.

indeed, it is not a repeating key. the structure seems to mimic that of a stream cipher, which implies a continual stream of data is used to encrypt and an operation (typically a XOR) is what actually obtains the ciphertext.

I programmed it to check a xor key of the mersenne primes written in base 10 starting at the tail end.
The I realised this is stupid because the key clearly wasn't ascii within a range of 10 since that would produce cyphertext within a narrow ascii range (assuming the plaintext was ascii with a narrowish range)

>>16677059 (OP)
nah, fuck you

>>16679961
The key is indeed not ASCII within a range of 10. The key is a bitstream resulting from a Lehmer Generator with a modulus equivalent to a Mersenne Prime. Inversion thereof is a studied topic. Specifically, inversion of the generating Lehmer Generator requires no further than linear algebra - the parameters are well-chosen. I've tried to clarify as much as I can without giving it away.

>>16679966
mad cause bad, this guy never encountered linear algebra before

>>16680049
Sorry meant to add "will try something tomorrow when I have time", I wasn't asking for a hint

>>16677222
>MP stands for Mersenne Prime.
I MEAN OBVIOUSLY
What else could it stand for?

This is like the meme about women sending hints and signals

>>16680049
>The key is indeed not ASCII within a range of 10. The key is a bitstream resulting from a Lehmer Generator with a modulus equivalent to a Mersenne Prime. Inversion thereof is a studied topic. Specifically, inversion of the generating Lehmer Generator requires no further than linear algebra - the parameters are well-chosen. I've tried to clarify as much as I can without giving it away.
You literally have the entire methodology away

This is so stupid there would be no way to decide this except brute force until it looks like text by using tens of thousands of different encryption algorithm possibilities

The sample is way too slow to know what method was used or if it even contains any information, it could be random for all we know, statistical analysis can also be easily countered by just imputing a statistically random text

>>16680276
i think that's the point, program something to brute force it
i will when i get time. also yeah, spoiler tags on the thing would be good, i read it but i deliberately didn't pay attention so I'm going to pretend I don't know and just google to see what mr lehmer did with mersenne primes
you also assume that it's natural language (probably english) and get the program to look for keys that turn out something that looks like words

>>16680335
>program something to brute force it
I’m pretty sure I could make something undeciphrable

>short sample
>no clues
>no known vulnerabilities
>text looks statistically random
>obscure and convoluted encryption method with many different steps to encryption

Here can you decrypt this message?
01101

I used a real procedural systematic algorithm to encrypt it, I’m not cheating, it is reversible if you know the code, it’s a simple encryption method too, it doesn’t use prime numbers or anything like that

But the cypher method is so absurd it’s impossible to decipher it. I’m pretty sure. I don’t even know if a longer sample would make it easier

>>16680344
yes but it's presented as a puzzle, it's literally even "you should be able to solve this", the implication is that you CAN crack/force it
I could make an impossible cypher too (even just use an OTP, easy and uncrackable)

>>16680269
modulating prime

>>16680276
there's a way to decode this particular type of cipher with no more than 4 outputs, technically. 5 makes it even better, and there are more than 5 here. Brute force is certainly a valid option though.

The type of algorithm and methodology are hinted at. It's the only way to make puzzles like this interesting, unfortunately. The alternative of enciphering with something significantly more advanced (but known/open) unfortunately drastically limits the amount of people capable of cracking it.

>>16680348
>presented as
Presentations are more unreliable than reliable in my experience.
I assume it is a fruitless time tax until proven otherwise.

>>16677059 (OP)
*HQDXNKTRISPYMOVAFEGCZL.B

TVEH*OPKFCDXNPS*DZANIZM.HFVYPKCPEZ.FXAVSZEKQYSBKH*OT*KCNP*IAISVZKZSYHTGSKMDKNYLCNRPV.AVZOKQEY.HTFHTDBKKAYZBAXSACCIQCHVBKN*PEQFDZAQSMZCIKHHC.B*KNGCBEXPSBFSAXLPCKOHVGKNGCXPPNRQC

01001110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01100111 01101001 01110110 01100101 00100000 01111001 01101111 01110101 00100000 01110101 01110000 00101100 00100000 01101110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01101100 01100101 01110100 00100000 01111001 01101111 01110101 00100000 01100100 01101111 01110111 01101110 00001010 01001110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01110010 01110101 01101110 00100000 01100001 01110010 01101111 01110101 01101110 01100100 00100000 01100001 01101110 01100100 00100000 01100100 01100101 01110011 01100101 01110010 01110100 00100000 01111001 01101111 01110101 00001010 01001110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01101101 01100001 01101011 01100101 00100000 01111001 01101111 01110101 00100000 01100011 01110010 01111001 00101100 00100000 01101110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01110011 01100001 01111001 00100000 01100111 01101111 01101111 01100100 01100010 01111001 01100101 00001010 01001110 01100101 01110110 01100101 01110010 00100000 01100111 01101111 01101110 01101110 01100001 00100000 01110100 01100101 01101100 01101100 00100000 01100001 00100000 01101100 01101001 01100101 00100000 01100001 01101110 01100100 00100000 01101000 01110101 01110010 01110100 00100000 01111001 01101111 01110101

I wrote code to brute force a lehmer-rng keystream, with all a values 1 to 400k, exponents 1 to 64 and seeds 1 to 100 (all permutations thereof). Higher exponents are probably the way to go but I'd need to rig up some DIY maths functions.

>>16683372
very warm, like actually unfortunately close. I will say bigint methods are outside the scope of the challenge (although are fun in and of themselves and should be explored if you haven't already).

>>16677059 (OP)

if you assume eight zero as start signal and assume utf-16 there is two characters to look at

01111100 x 01111100 -1
00010101 x 00010101 -1

jokes on you

Rick rolled

Is it "Welcome to Future Gadget Lab!"

hint: check the top bit of each ciphertext byte, it’s literally the rng’s odd/even bit. once you grab those, you can backtrack the seed.

>>16683627
currently building basically my own library to support large integers ... shit's slow.
I never used chatgpt to code but I asked it to write some tests for a subtraction operator.
>5 - 5 = 5 [PASS]
think I won't use chatgpt for coding

>>16684064
LOL, bitwise subtraction is right to left computable, and doable in O(n). I think Hacker's Delight mentions right to left computability in the beginning and there's all sorts of manuals for the algorithm otherwise

>>16684007
nope, good guess tho lol

final hint: the cleartext is a link. This *should* reveal more than enough structure to break this efficiently

>>16677059 (OP)
>>16685975
This is an interesting thread, so will it just die unsolved?

>>16687331
Hope not. I intend to solve it but at the moment I have to spend this week for exams. It would be so easy from here except I suspect theres some error in my bigint code and I don't have time to hunt it down
code here if anybody wants it https://files.catbox.moe/l3rve4.zip (written in freebasic)

>>16680344
>Here can you decrypt this message?
>01101
42

>>16687331
in all honesty, it's a somewhat harsh problem that's a bit reliant on luck rather than skill. plus it's not computationally trivial to brute force the full spectrum - really, depending on your skills and rig, it can take anywhere from about two hours to just under 3 days by my own estimations. I have some ideas for other fun crypto challenges that i think will be a bit more interesting mathematically and not as punishing time wise. Hopefully with all the hints somebody gets it though!

>>16687331
It must be solved, it will be solved.

>>16683372
>>16683627
am i an idiot because i heard bigint methods were outside the scope of the challenge and went to build one anyway
now I don't have time until wednesday to debug them and maybe it turns out i should've been running with 32 bit ints in the lehmer generator anyway (i used 64 thinking the results come out equivalent but I'm not sure this is true -- the 128 bit generator gives different answers (modulo 256) and that's why I think it has some bugs)

>>16693047
not an idiot, just easily distracted lol, BigInt is fun and a worthwhile challenge, but it def isn't required here.

bump mostly but I've got the code ready (basically just pulled the bigint stuff out)
will check both not-offset and offset seeds (the first value is always the seed so it makes sense to ignore it) (searching both is easy)

make predictions for what the link is:
rickroll
scam site to grab ip
some grooming discord

>>16695423
>the groomers are rolling their own crypto
never been more joever

So far have searched:
32 bit 0-indexed
>a 1-1000, x0 1 to 999888
>a 1-50000, x0 1 to 5500
32 bit 1-indexed:
>a 1-100, x0 1-100
for all m exponents (prime m) in [1,31]

annoyingly it turns out that 32 bit and 64 bit arithmetic (128 also) give divergent answers for lehmer generators, even if given the exact same input. Since I realised this I've thought the challenge probably uses 32 bit lehmers, so I've focussed on them. Whether to offset the first X0 value or not seems reasonable either way, so I'm testing both.

01000010 01000101 00100000 01010011 01010101 01010010 01000101 00100000 01010100 01001111 00100000 01000100 01010010 01001001 01001110 01001011 00100000 01011001 01001111 01010101 01010010 00100000 01001111 01010110 01000001 01001100 01010100 01001001 01001110 01000101

>>16684198
El. Psy. Congree.

>>16677059 (OP)
klUhfoX,IP6Ll>w|

0x6B k
0x6C l
0x55 U
0x68 h
0x66 f
0x6F o
0x58 X
0x2C ,
0x49 I
0x50 P
0x36 6
0x4C L
0x6C l
0x3E >
0x77 w
0x7C |
0x15 (non-printable)

>>16677059 (OP)
yes

You CAN solve this one, right anon?
discord gg/ktsD385e48

Say, what language was the original encryption done with?
I ask because I have set up my code with 32 bit arithmetic, and given some ambiguity, it could be signed, unsigned, and use the first value or not (the first value being the pure "a" term, so disregarding it makes a lot of sense for encryption)
But all of this goes out the window if the initial problem was done in say, Python, or with a calculator or something, because the arithmetic handles overflow completely differently as Xk increases. This is why 64 bit and 32 bit code gives the same answers for a few terms, then diverges as the 32 bit overflows earlier. Python (I presume many other possible tools too) handles numbers very differently, and will make them variable length or automagically switch to floating point or whatever, so it will give totally divergent results.

I gave it a decent try, used all the clues and ChatGPTed the basic bruteforcing in C++ multithreaded code (I verified it and it's correct). It will still need O(2^64) which is just a bit too much. Not worth it since maybe I got something wrong and then the whole scan is a waste.
Esp. I have doubts about this hint:
>check the top bit of each ciphertext byte, it’s literally the rng’s odd/even bit
If it's a simple XOR with the bits 0-7 of the state, then bit7 of CT (which is 0 in PT) should correspond to bit7 of the state. But odd/even bit is bit0. This casts doubt on the whole understanding of the procedure, both mine and potentially OP's.

>>16695423
kek