Strictly speaking, shift and xor alone will not net you a secure cipher, seeing that those are both linear GF(2) operations. You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc.

But on the subject of extremely simple constructions, you can compose many random permutations of a particular form---state[i] = state[i] xor F(state[j], state[k]), where state[i] is the ith bit of the state and F is a randomly chosen boolean function--- and obtain something asymptotically secure [1].

[1] https://arxiv.org/abs/math/0411098

I'm a little over my skis on this (I'm not a cryptographer) but for the underlying insight on why this works, I think you can start with the idea of iterated ciphers --- the design argument that a very simple function that is repeated (in "rounds") with an a key that has been expanded to fit those rounds (the "key schedule") "outperforms" --- gains adequate security with less computation --- a sufficiently complicated function. Once you have that idea, it seems natural to find the simplest and most efficient round function.

Past that: I spent a long time blowing off block cipher cryptanalysis (I'm pretty much exclusively interested in crypto bugs that will actually let me own up a system, and you are essentially never going to cryptanalyze a block cipher for a vulnerability research project) but a lot of block cipher design clicked for me once I took the time to work through linear and differential cryptanalysis.

So I guess my point here would be: if you're blown away that you can get such durably effective security --- so much so that 3DES is still in some ways resilient in 2021 --- well, (1) you should be and (2) Aleks' post here is I think probably a really good way to understand why this stuff works.

Also, 128 bit numbers are just very big. :)