The start of the long journey eastwards: Train at Yaroslavl Station 

This is Moscow. You are being pushed around. The tunnels of Stalin's Metro are heaving. The sleazy hoardings are glinting. Policemen in long coats pace the platforms. Leather-jacketed immigrants from the Caucasus push towards the exits. Young women in furs adjust their iPods. 

Below the surface, the symbols of Bolshevism are as ubiquitous, as present and ignored as those of royalty in England. To remove every hammer and sickle in Russia would be impossible. It could take a century. 

Old women are on their knees begging on the sides of the escalator. They look like survivors. Because they are. Survivors of collectivisation, of the Nazi invasion, of totalitarianism and the economic collapse of the 1990s. You are trying to leave the station. Then you see it. 

"Stalin reared us on loyalty to the people. He inspired us to labour and heroism." The gilt slogan was painstakingly removed during the de-Stalinisation drives of the late 1950s. Now it is back. The kiosks on the street hawk the tabloids. Simple news. What Prime Minister Vladimir Putin has done, what President Dmitry Medvedev has said. Putin says the purges were in the past and Russians have nothing "to be ashamed of", Medvedev says more memorials should be erected to their victims and they "should never be forgotten." The history wars have come to Russia.

The Kremlin is trying to build a superpower. It needs a simple story. It wants the record straight. So it has set up a "History Commission" to clear things up. Human rights activists say a History Commission without historians is a Soviet-style absurdity. The superstate seems to be drifting towards accepting Stalinism. New textbooks downplay Stalin's murderousness. Then, confusingly, the drive of the superstate shifted gear. Alexander Solzhenitsyn's Gulag Archipelago was suddenly placed on the school curriculum. I phoned the pro-Kremlin politician Sergei Markov, who sits on the Commission, to ask him to explain why it seemed the state hasn't made up its mind.

"There are lots of debates in our party, United Russia. Debates about the economy and debates about the past." He paused. "Regarding Stalinism, there are some things we are very proud of, like victory in the war, whilst other things we are very ashamed of." Then he added with the pedagogic charm of the authoritarian, "How do we explain this difficult history...to the people?" 

Russia has a population of 140 million — just a third larger than Germany — and a Muslim population of roughly 14 per cent, a few points higher than France. What makes Russia different is Siberia, "the jewel in the crown of the Russian Empire", as the historian Dominic Lieven describes it. Her riches lie there but more importantly so does her sense of self and the darkest side of Russia's history. There I hoped I could find out what Russians really feel about their past.