The Boeing-737-500 owned by Russian flagship airline Aeroflot crashed in an unpopulated area at 3:15 a.m. (23:15 GMT) with 83 passengers including seven children and 21 foreigners on board, along with five crew members.
Prime Minister Vladimir Putin said in his message to the regional governor: "I ask you to convey a word of support and deep sympathy for those who lost what is dearest to them - their relatives and close ones."
"The government commission will do all it can to investigate the circumstances of this catastrophe, and to provide help to the families of those who died," Putin's message, quoted by the government press service, said.
The Kremlin earlier said President Dmitry Medvedev had sent a condolence message to the bereaved families.
The Perm Territory's emergencies ministry department has published a list of those killed in the crash, which includes Col. Gen. Gennady Troshev, 61, a former commander of the North Caucasus Military District.
The youngest of those on the passenger list is a nine-year-old girl, Yana Kuznetsova.
Aeroflot announced on Sunday it has severed ties with its subsidiary that owned the plane.
"A decision has been taken to completely sever cooperation with our subsidiary Aeroflot-Nord. All future flights will be carried out by our companies separately," Aeroflot CEO Valery Okulov told reporters at Sheremetevo Airport in Moscow.
Aeroflot earlier said Flight 821 was carrying "foreign citizens including nine from Azerbaijan, five from Ukraine, and one from each of France, Switzerland, Latvia, the United States, Germany, Turkey and Italy."
The airline pledged in a statement to pay bereaved families up to 2 million rubles ($80,000) in compensation per victim.
Investigator Vladimir Markin told RIA Novosti the plane crashed into a ravine, and that part of the trans-Siberian rail line between Perm and Yekaterinburg was damaged. He said technical failure was the most likely cause of the crash.
Russian Transportation Minister Igor Levitin, who is heading a government commission investigating the catastrophe, told RIA Novosti that the plane's black boxes had been handed over to experts.
"The flight data recorders have been found, and handed over to the Interstate Aviation Committee [of 12 ex-Soviet states], which will decode it," he said.
News channel Vesti-24 has shown footage of the plane wreckage strewn over a large wooded area.
An eyewitness described to the channel how the plane had caught fire while still airborne and had hurtled downwards "like a falling comet."
The disaster is the worst since Pulkovo Flight 612, which crashed in eastern Ukraine on August 22, 2006 en route from the Black Sea to St. Petersburg, killing all 160 passengers and 10 crew.
