Russian investigators combing two subway stations attacked by female suicide bombers think Chechen rebels may have been behind the rush-hour strike that killed dozens of people.

"Our preliminary assessment is that this act of terror was committed by a terrorist group from the North Caucasus region," said Alexander Bortnikov of the Federal Security Service, in reference to the investigation at one of the blast sites.

"We consider this the most likely scenario, based on investigations conducted at the site of the blast," Bortnikov said. "Fragments of the suicide bombers' body found at the blast, according to preliminary findings, indicate that the bombers were from the North Caucasus region."

Prime Minister Vladimir Putin said the "terrorists" responsible for the Moscow subway attacks Monday "will be destroyed."

"I am sure that law enforcement agencies will do everything to find and punish the criminals," said Putin, who called for helping the families of the victims and bolstering transportation safety.

"We are providing Moscow metro with additional CCTV cameras. Today's events show we should not only continue this work but to make it more effective. Changes in legislation may be necessary."

The two explosions that rocked the subway stations in central Moscow during rush hour killed at least 38 people and wounded more than 60 others -- actions that spawned widespread public outrage.

"It's disgusting," said one eyewitness. "I don't know who did it and what they wanted. Life is so short. How could people commit such terrible acts?"

Although the Chechen rebels have yet to claim responsibility, Bortnikov's statement is a strong implication that Chechen rebels fighting for independence were behind the strike.

Thousands have been killed and 500,000 Chechen people have been displaced in the Chechen rebels almost 20-year conflict with Moscow. The area is located in the North Caucasus region of Russian between the Black and Caspian seas.

The first blast occurred at 7:56 a.m. local time at Lubyanka subway station, killing at least 23 people and wounding 18, the Ministry of Emergency Situations reported on its Web site.

The Lubyanka station is near the Kremlin and Federal Security Service headquarters.

Another blast happened about 40 minutes later at Park Kultury station, on the same train line. The ministry reported 12 dead in the second explosion, with 20 more wounded. Both stations reopened at about 5 p.m. Moscow time (1400 GMT), the Russian Emergencies Ministry said.

Three Moscow hospitals were treating the wounded, the ministry said.

Yulia Shapovalova with Russia Today TV was at the second station at the time of the blast.

"The staff members started urgently evacuating people, so that meant they probably knew about the first blast at the Lubyanka station," she said. "All the people -- a huge crowd of people -- slowly started to move. ... As soon as I got upstairs, I heard the blast."

"It was a terrorist act carried out by the female suicide bombers," said Moscow Mayor Yury Luzhkov, in reference to the first and most lethal explosion, citing the Federal Security Service. "They were specifically timed -- for ... the train was nearing the station -- to make the most damage."

Both stations reopened around 5 p.m. Moscow time, according to Veronica Molskaya from the Press Service of the Russian Emergencies Ministry.

In the city of St. Petersburg, three metro stations were shut as the result of a bomb scare.

Millions of commuters use the Moscow metro system every day. An estimated 500,000 people were riding trains throughout the capital at the time of the attacks. It was unclear when the system would return to normal service and the incident generated fear among commuters.

"I feel scared," one woman said on TV. "I have to walk to get to work because there is no way I'm going by Metro."

The attacks in Moscow reverberated across the globe.

U.S. President Barack Obama condemned the "outrageous acts" and passed along his condolences. "The American people stand united with the people of Russia in opposition to violent extremism and heinous terrorist attacks that demonstrate such disregard for human life," Obama said.

Secretary of State Hillary Clinton said she will offer her condolences to Russian Foreign Minister Sergey Lavrov on Monday in Ottawa, Canada -- where the Group of Eight foreign ministers are meeting to plan for the June G8 meeting in Canada.

"This brutal assault on innocent civilians is another reminder that terrorism is a threat to peace-loving people everywhere and must be met with unwavering resolve," she said.

"Together with our G8 partners, we will discuss how to further strengthen international counter terrorism coordination and cooperation."

New York Police Department Deputy Commissioner Paul Browne said police are stepping up security in the New York City subway system.

In Washington, Metro, the operator of the city's transit system, said it is expanding security in light of the Moscow attacks. Coincidentally, it had a terror drill this past weekend and is holding another one on Monday.

British Prime Minister Gordon Brown said he was "appalled" by the incident and sent condolences to Russian President Dmitry Medvedev, according to Britain's Press Association news service.

Interpol, the international police agency, condemned the attacks and offered help to Russian authorities in the investigation.

Interpol's executive director of police services, Jean-Michel Louboutin, called the actions "despicable and senseless attacks targeting the public."

CNN's Matthew Chance, Paul Courson and Eddie Demarche contributed to this report.